BS-27. Median in a Row Wise Sorted Matrix
HTML-код
- Опубликовано: 26 авг 2024
- 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/take...
0:00 Introduction of Course
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🙌.
tereko uske job chodne ya na chodne se kya farak pdta hai
@@22gauravkumar70 Hes appreciating his hardwork, nothing else. Managing both and providing this quality education is just extra ordinary dedication and spirit
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
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 🙇♂️
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 . 😊💌❤
Thank you very much🙏awesome content and please make videos on strings , waiting for them😂
yes
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.
with this i think my intuition became better for using BS in various types of questions
Thanks RAJ sir
Finally completed Binary search playlist. This series is Amazing!!! In depth explanations, diverse problems, and great logic building!👏👏👏
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
15 element hi hai dhyan se gin
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😢
agle saal aeega wo wala playlist
@@cdnggk6455 really or kidding?
why?@@cdnggk6455
Strings me kya pdna h? vo toh question practice krte-krte hi aayega.
@@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...🙂
Please try to upload a video daily Placements already started and yours videos are really helpful
Finally completed the playlist. Thank you striver !
Bhaiya can you make next playlist on *greedy algorithms*. No one in youtube is having a proper videos on it.
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...❤
New video means more knowledge. This consistency is amazing.Understood
Had to watch twice to understand this master approach. It's some insane stuff which I could never thought. Just one question how bhaiya? how?
completed BIinary Search playlist on 12/05/24... Explanation and Content was awesome ....
Its crazy I am unable to solve the problem on my own until I watch the logic. I hope I improve this.
Successfully Completed one complete Playlist 😃Thanks so much Striver 😉💌
Sorry, watched the video couple of times but didn'y understood the thought process, can you help please....
Eagerly waiting for strings❤❤
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++
Thalaivar. Striver ka hukum.
aranthamaintharaja
Completed the playlist..! As usual.. OP Striver.. Keep rocking man... Eagerly waiting for your more playlists
Striver please upload videos on strings and linked list of A2Z dsa course i am eagerly waiting PLEASE
understood! and finally completed this binary search playlist. Did learn a lot!!! Thanks Striver....
Thanks a lot striver , I was able to crack amazon interview through your series.
Happy to share that i was able to solve brute but couldnt do the optimal
🙂
I really like your way of teaching
Keep uploading!!!
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?
Even I have the same doubt. Lemme know if you get that.
++ Is there some kind of proof for the same? Please let me know once you get it.
@@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."
See if some element in not present and it has
if (smallEqual
please keep uploading bhaiya this series at least 1 video a day.. ThankYOu ❤
Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
PLEASE BRING STRINGS PLAYLIST SOON !!!!!
bro plz upload strings and linked list
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
Understood!!! Please make a playlist of strings as well,Thankyou.
when will you upload String videos?
best playlist. Understood everything!
bhai strings ki playlist laado ! will be of great help!!!
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.
have you got your issue resolved yet or not
because I'm thinking the same thing for half hour
I also thought the same.
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 man.. Completed this playlist also, Great teacherr🤩
thanks for the wonderful series..
sir can you tell when are you going to upload the next videos as we are waiting from 1 month now?
How can we be sure low+mid/2 belongs to the matrix
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.
@@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 ?
UNDERSTOOD;
we can assign low = matrix[0][0] and high = matrix[n-1][m-1]
thanks a lot striver
i dont understand
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))*
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))
Brother you are god for me 💖
Damn this guy is top notch!
New question from binary search
just try for 1 2 3 4 5 for better clarity why always returning low as answer.
Understood
when he says: "it is the easiest thing to do, trust me", I am like: Really?👀 because I have no idea how to do that. 😣
Understood, thank you.
Very nice explanation
you are my role model
understood
thanks bhaiya
gfg k 4 hzar a course kharid kar striver ki playlist se padh rahi hu🥲❤
same 😂
brother there is no 6 in that matrix from where are you taking this 6 that you have written in the 1D array
nice explanation 👍
Understood🙃
Mission Accomplished sir ji
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.
Also the final answer/code for this problem isn't available in the description. Can you please look into it?
Bro! Escape the matrix
Godlike
Ab video ni ayegi??😢
Aapne bola tha daily ayegi ab
Loved it ❤
Thank you 🙂
Understood✅🔥🔥
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...
Bhai humari bhi yahi doubt h ! Ki ye khdse aana toh impossible lagtah
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
bhai striver ne poori complete karwa diya hai kya dsa playlist? aur kya videos sequence mein hain?
tumko kitna fayda hua?
kitna padhe?
@@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
Thank you Bhaiya
I gotta say this one is super confusing.
Thanks
does anyone know, which companies have asked this question?
can anyone tell me, what software he is using for sketching in this video
Understood!!
Can't it be like O(logn * logn)
For max element -> O(logn) as well
???
Bhaiya ❤
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.🙏
No those videos are (Trees, DP and Graph) pretty new. And bhaiyaa will not be replacing those videos.
@@bishalkundu7592 is hsi playlist completely updated and complete? Are all the videos arranged in serial?
@@ultimatescience3842 what do u mean by hsi playlist?
@@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:)
Could you please tell me which tool you uses for teaching ?
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
Where can I get Java code?
understood.
Can you please teach us maths required for competitive programming.
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]
Striver I'm a final year student,now campus placements are going on so can you please tell when this course may finish...
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.
Which app do you use sir for notes?😊
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 ?
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.
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
Yes, in that case last index of second row should be the largest value
Eg [[1,2,3],[4,4,4]]
Just wow
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
Instead of k, take a variable named as count & initialise with ( n * m + 1 ) / 2, which is the middle element of the sequence when you arrange matrix in linear ascending order. Let’s say m = 3 and n = 5, then count = 8. It means 8th element is the middle element, i.e the median of the matrix. Now we are sure that there must be 7 elements on left side of the 8th Element & 7 elements on right side of 8th element.
Now when black box returns value which is less than count we sure that current mid can’t be the answer, but when black box returns value which is greater than or equal to count, it may or may not be the answer, so we store it in ans variable hoping it as answer.
changes I suggest for better understanding
cnt = (n + m)/2;
while ( L < R)
{
mid = (L + R)/2;
val = blackbox(mat, mid);
if ( val < cnt){
L = Mid + 1;
} else{
R = mid - 1;
ans = mid; // might be answer
}
Binary Search playlist done?
Yes
when can we expect next ?@@takeUforward