BS-27. Median in a Row Wise Sorted Matrix
Problem Link:
Notes/C++/Java/Python codes:
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
Пікірлер: 151
In era of every other YT FANG employers leaving their job and selling own courses, Striver is the only legend who's not giving up❤️ and managing both🙌.
@22gauravkumar70
17 күн бұрын
tereko uske job chodne ya na chodne se kya farak pdta hai
Thank you so much for your wonderful videos, Plz keep them coming 🙏
Your one line always keep me running positively, "Life bohot badi hai, dont give up easily, try try try again" .Thanks
Previously Studied Binary Search 9 months ago , now again done a broad revision from you , now concepts are more crystal and clear than before . Thanks Striver for your continuous effort to reform the IT Industry in India by teaching the new generations topmost Coding skills . God bless you . Will now revise both Graph and DP from you shortly . 😊💌❤
okay i have a doubt the mid that u calclated which is 7 is based on the above matrix but the below sorted array has 16 elements. this sort made of made the whole explanation confusing if anyone is reading this do u agree or did i miss something
@karamveeryadav8824
Ай бұрын
15 element hi hai dhyan se gin
yes, I am from python community didn't find any issue in the course. I think this course is one of the best course. I have taken purchased course also but this is one of the best course.
Finally completed Binary search playlist. This series is Amazing!!! In depth explanations, diverse problems, and great logic building!👏👏👏
with this i think my intuition became better for using BS in various types of questions Thanks RAJ sir
Finally completed the playlist. Thank you striver !
Aatma santusht ho gaya Striver bhaiya ye lecture dekh kar maaza ageya , Big thanks Bhaiya , love you, you are an inspiration for me !!!!!!!!!!!!!!!!
Eagerly waiting for Strings and LINKED LISTS😢
@cdnggk6455
10 ай бұрын
agle saal aeega wo wala playlist
@puneetnj1842
10 ай бұрын
@@cdnggk6455 really or kidding?
@Tam-wc2qm
10 ай бұрын
why?@@cdnggk6455
@zanies6288
10 ай бұрын
Strings me kya pdna h? vo toh question practice krte-krte hi aayega.
@iammysterious-ud9cf
10 ай бұрын
@@zanies6288Improving problem solving of Strings in a brute, better, optimal is much necessary for beginners of DSA.. I would like to remind that it's A TO Z BEGINNER COURSE...🙂
New video means more knowledge. This consistency is amazing.Understood
Completed the playlist..! As usual.. OP Striver.. Keep rocking man... Eagerly waiting for your more playlists
And Yes Reverse Polarity is also working here as *High pointing to an element that is greater than all the elements* and *Low pointing to the smallest element* If you dry run then low end up pointing to the answer. Thankyou soo much Striver..... I'm just soo damn grateful to you 🙇♂️
Striver u are really doing a good job and helping thousands of aspiring engineers like me ❤️❤️❤️❤️, please can you add low level design playlist .. like OOP design interviews in c++
I really like your way of teaching Keep uploading!!!
best playlist. Understood everything!
completed BIinary Search playlist on 12/05/24... Explanation and Content was awesome ....
understood! and finally completed this binary search playlist. Did learn a lot!!! Thanks Striver....
Please try to upload a video daily Placements already started and yours videos are really helpful
please keep uploading bhaiya this series at least 1 video a day.. ThankYOu ❤
thanks for the wonderful series..
Hey Striver, Thanks for the wonderful videos... I am unable to grasp the concept, maybe because its 4:50am and I have exhausted my daily quota of brain usage... Haha, will try this one later...❤
Eagerly waiting for strings❤❤
Bhaiya can you make next playlist on *greedy algorithms*. No one in youtube is having a proper videos on it.
Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Striver please upload videos on strings and linked list of A2Z dsa course i am eagerly waiting PLEASE
understood man.. Completed this playlist also, Great teacherr🤩
Doubt - what makes it sure that the answer will be present in the matrix? Like how can we say the answer we found will always be in the matrix?
@Peeeacee
6 ай бұрын
Even I have the same doubt. Lemme know if you get that.
@aletivardhan6679
5 ай бұрын
++ Is there some kind of proof for the same? Please let me know once you get it.
@kushagrajain9493
4 ай бұрын
@@aletivardhan6679 @palakkalsi8595 @Ajay-cv1zs , striver has replied on this issue on one of the comment, let me paste here, "this is why we keep moving low and high, and we don't stop. Its bound to stop at a number which is answer. Because if the numbers are [1,5, 6, 7, 11] It can never stop at 9 because 8,9,10 all of them will have same number of elements on left."
@priyanshuagarwal4334
2 ай бұрын
See if some element in not present and it has
Happy to share that i was able to solve brute but couldnt do the optimal
Its crazy I am unable to solve the problem on my own until I watch the logic. I hope I improve this.
Understood, thank you.
Loved it ❤
Understood!!! Please make a playlist of strings as well,Thankyou.
Very nice explanation
Sorry, watched the video couple of times but didn'y understood the thought process, can you help please....
you are my role model
sir can you tell when are you going to upload the next videos as we are waiting from 1 month now?
Thanks a lot striver , I was able to crack amazon interview through your series.
Brother you are god for me 💖
when will you upload String videos?
nice explanation 👍
Damn this guy is top notch!
Striver start sliding windows and greedy atleast provide a basics video😢 i solved the linked list fully now it was good but greedy and sliding windows looks like something big can you give a start
bro plz upload strings and linked list
Thank you very much🙏awesome content and please make videos on strings , waiting for them😂
Thalaivar. Striver ka hukum.
@bhubeshsr6281
10 ай бұрын
aranthamaintharaja
Understood🙃
Understood✅🔥🔥
Thank you 🙂
PLEASE BRING STRINGS PLAYLIST SOON !!!!!
Mission Accomplished sir ji
Thank you Bhaiya
Sir , Is it okay if the median answer that we are returning is not in the matrix . Because in some cases mid value (average of high & low) may be not present in the matrix , but numbers " lessequal " than this value are more than "req" , which satisfies the condition so it will be returned.
@user-ge9uh9vs9m
6 ай бұрын
have you got your issue resolved yet or not
@user-ge9uh9vs9m
6 ай бұрын
because I'm thinking the same thing for half hour
@aayush5474
Ай бұрын
I also thought the same.
@chetandatta9051
3 күн бұрын
See the idea lies here 1 1 1 3 3 3 9 9 9 Assume that these are elements when we make the matrix into 1D array. Number - Frequencey 1 frequency - 3 2 frequency - 3 3 frequency - 6 4 frequency - 6 5 frequency - 6 6 frequency - 6 7 frequency - 6 8 frequency - 6 9 frequency - 9 low = 1 and high=9 => mid = 5 => freq(5) =6 => move high = mid -1 = 4 low = 1 and high =4 => mid = 4 => freq(4) =6 => move high = mid -1 = 3 low = 1 and high =3 => mid = 2 => freq(2) =3 => move low= mid +1 = 3 low = 3 and high = 3 => mid = 3 => freq(3) =6 => move high = mid -1 = 2 low = 3 (holds on and loop break) You got the pattern. Low will point to the element which is always present in the list. It will always point to the first element which has same frequency of the all the elements present in that range. In our case 3, 4,5,6,7 all have same frequency 6 but ends up the first (3). 3 is present in the list. Hence low cannot point to a number which is not present in the list.
Understood!!
can anyone tell me, what software he is using for sketching in this video
Bhaiya ❤
bhai strings ki playlist laado ! will be of great help!!!
Could you please tell me which tool you uses for teaching ?
Understood
Can you please teach us maths required for competitive programming.
Thanks
understood
we can assign low = matrix[0][0] and high = matrix[n-1][m-1]
Just wow
New question from binary search
Which app do you use sir for notes?😊
does anyone know, which companies have asked this question?
How can we be sure low+mid/2 belongs to the matrix
@takeUforward
10 ай бұрын
this is why we keep moving low and high, and we don't stop. Its bound to stop at a number which is answer. Because if the numbers are [1,5, 6, 7, 11] It can never stop at 9 because 8,9,10 all of them will have same number of elements on left.
@learningstuff4578
18 күн бұрын
@@takeUforward What if array is [[1,2,3],[1,2,3],[1,2,3]] . In that case how will the req = (n*m)/2 will hold ?
Will this work if array is sorted Ina way that last index of first row is less than first index of second row and so on
@amaldevps2164
10 ай бұрын
Yes, in that case last index of second row should be the largest value Eg [[1,2,3],[4,4,4]]
Please make playlist on strings sir
Striver, here the code looks all great but how are we navigating the matrix here, I am very confused regarding that, the code is navigating as we have used an array, with all the number. But it is very different scenario in the matrix.
@mritunjaykumar947
8 ай бұрын
Also the final answer/code for this problem isn't available in the description. Can you please look into it?
Striver I'm a final year student,now campus placements are going on so can you please tell when this course may finish...
@zanies6288
10 ай бұрын
If you are final year student, don't waste on this course. This is for beginners and people who have a lot of time. Just read the articles on takeuforward solve some problems on leetcoee u will learn more in less time.
If you observe then after the first solution that was *n* * *m* *** *(n* *** *m* *** *log2(nm))* Instead of removing the -log(nm)- We can Optimize that instead of putting all the elements in an array we can sort the 2D Matrix itself and use the formula of total_column / index And this will work because the rows and cols will be odd everytime So the TC will be *(n* *** *m* *** *log2(nm))*
@771aryan
9 ай бұрын
The TC originally is n*m*log(2nm) because , you will use O(n*m) to traverse all elements in the 2d array, and then you will sort the n*m elements using inbuilt function, so TC will be O(n*m + n*m*log(2nm))
understood.
Bhaiya linked list aur string ki bhi videos aane wali hai kya? If yes then what will be the timeline so that usse ki hisab se preparation ki planning krte
@ultimatescience3842
10 ай бұрын
bhai striver ne poori complete karwa diya hai kya dsa playlist? aur kya videos sequence mein hain? tumko kitna fayda hua? kitna padhe?
@RAHULSINGH-cd6gl
8 ай бұрын
@@ultimatescience3842pura complete nhi hua hai........sequence mat Haan jaisa a-z DSA playlist me hai waise padhna start Karo bahut faida hoga......Maine personally padha hai islia bata sakta hu
Where can I get Java code?
brother there is no 6 in that matrix from where are you taking this 6 that you have written in the 1D array
Can't it be like O(logn * logn) For max element -> O(logn) as well ???
i dont understand
Ab video ni ayegi??😢 Aapne bola tha daily ayegi ab
Hi bhaiya can connect by some chance.recently i got call from scaler and they got very convincing as well as confusion. So I wanted to connect with you plz it Will be a big help.There is no problem in payment but plz guide me what should I do🙏
@VishalGupta-xw2rp
9 ай бұрын
Have faith in Striver and solve more questions, no need of anything else
Hey Striver, I have one doubt will you replace all the old videos(DP series, Binary Search Trees, Graphs and other videos) with new videos or will you continue with the old one, so that we can wait for new one or we can continue can you please give some clarification on this. By the way you videos are really helpful. Thanks for such free content.🙏
@bishalkundu7592
10 ай бұрын
No those videos are (Trees, DP and Graph) pretty new. And bhaiyaa will not be replacing those videos.
@ultimatescience3842
10 ай бұрын
@@bishalkundu7592 is hsi playlist completely updated and complete? Are all the videos arranged in serial?
@bishalkundu7592
10 ай бұрын
@@ultimatescience3842 what do u mean by hsi playlist?
@ultimatescience3842
10 ай бұрын
@@bishalkundu7592 sorry bro, I meant "His". Matlab poora complete hai dsa? aur agar playlist ko follow karein A to Z toh kya saare videos serial mein hain? Plus mai ekdom new hoon programming mein, abhi third year start hua. Mai c++ soch raha seekhne ko toh wo kaha se seekhun? c++ with dsa karne ki soch raha hoon. Please bro thoda detail mein bata dena:)
gfg k 4 hzar a course kharid kar striver ki playlist se padh rahi hu🥲❤
@saswatrath4646
3 ай бұрын
same 😂
Bro! Escape the matrix
What if the input arr is [[1,2,3],[1,2,3],[1,2,3]] . then (n * m) /2 will not hold. Can someone please clarify ?
@chetandatta9051
3 күн бұрын
it still holds because, 1 1 1, 2 2 2, 3 3 3 the median is 2. Irrespective of the input left and right of the median has (n*m)/2 these many elements.
Striver bhai sach sach batana iska optimal solution aapne bina solution dekhe apne aap soch liya tha kya ??? And other people also tell me this...because it seems to be impossible to think the optimal sol by myself...
@HarshKumar-hn8ss
8 ай бұрын
Bhai humari bhi yahi doubt h ! Ki ye khdse aana toh impossible lagtah
Binary Search playlist done?
@takeUforward
10 ай бұрын
Yes
@hat_awesome21
9 ай бұрын
when can we expect next ?@@takeUforward
BF approach. Public class solution { Public static int find median(int [][]matrix,int m,int n){ Array list list =new Array list (); for(int i=0;i
Can't we do this l=m*n/2. d=l/rows. R=l%rows+d. Ans=matrix[d][R]
I gotta say this one is super confusing.
just try for 1 2 3 4 5 for better clarity why always returning low as answer.
1st view 1st comment
Can someone verify whether the following code is flawless? (I couldn't verify more than running it with the test case in the video) (Python) import math mat = [[1, 3, 6], [2, 6, 9], [3, 6, 9]] rows = len(mat) cols = len(mat[0]) mini = math.inf maxi = -math.inf for i in range(len(mat)): mini = min(mini, mat[i][0]) maxi = max(maxi, mat[i][cols-1]) low = mini high = maxi required = (rows*cols) // 2 + 1 while low
Oky but, who knows that mid will be in our matrix, WHO KNOWS, what if the low is NOT an element in the matrix. This problem arised in my head because we are taking answer space from minimum to maximum element, but it isnt necessary that all the elements in our search space lies in the matrix
This is my simple and easy to understand O(log(2000) * R * log(C)) ~ O(11 * R * log(C)) code: int median(vector &matrix, int R, int C){ int l = 1, r = 2000; while(l
9:10
us
Mujhe ye median wale problem itne bekar lagti h 😢
you don't know most of the thing you are talking about!!