BS-24. Search in a 2D Matrix - I | Binary Search of 2D

[@takeUforward]

Please watch our new video on the same topic: kzbin.info/www/bejne/gIm4ZXShm9lqr80

[@AbhishekSharma-ip4df]

bhaiya..kya approach..kya intuition..kya energy..explain krne ka tareeka..legit sb awsm hota h aapka..u make us feel dsa🔥🔥

[@prachigoyal2510]

A huge thanks Striver for putting all these efforts 🙏

[@debanjanghosal618]

I solved this problem on my own using a slightly different approach: My intuition was since each row in the matrix is sorted in ascending order and the first element of each row is greater than the last element of the previous row, the matrix can be treated as a sorted 2D grid. Starting from the top-right corner is effective because: - If the current element is greater than the target, moving left in the row helps since all elements to the left are smaller. - If the current element is less than the target, moving down to the next row is logical, as all elements below will be larger. - If the current element is equal to the target, we return true. This approach efficiently narrows down the search space by using the properties of the sorted matrix. This approach's time complexity will be O(m+n), which is slightly worse than the optimal solution of O(log(m*n)). This approach can also be used to solve the problem of finding the row with max 1's.

[@bhushanambhore8378]

That's a nice approach. I solved it by this approach like, I applied binary search on row which eliminates unnecessary rows that doesnt contains target element, this results to a row which may or may not contain target element and applied again binary search on columns of resultant row which i eventually find out or may be not target elem is present. This take TC: O(Log M + Log N) which is equal to O(Log M*N)

[@t3ch_r4id]

Write staircase search algo works for this problem ✌🏻👍🏻

[@Ajayvir1953]

@@t3ch_r4id staircase search algo is not optimal though

[@princebhanushali6255]

Best DSA questions and approaches among all the DSA tutorials on KZbin. Big thankss❤❤

[@sairam3351]

You are excellent teacher bro,no professor comes close, 💖

[@harshhwardhanrai3716]

at 10:15 I literally started searching for the intuition for it but thanks for explaining it :)

[@KashafZia-d7p]

watched multiple videos of this question but only this video cleared my concept.Hats off

[@Gagansharma3002]

Bhai babbar ke to bus hype h asli udham to tumne machai h student ke learning me❤

[@muditsinghal6042]

I did log m + log n basically the same, by doing bs first on first column and then on that row, it was more intuitive following your playlist, but i did think of this method but got stuck in how to convert 2D to 1D, loved the progess i made, thank you so much

[@siddharthgowd825]

log(m)+log(n) = log(m*n) both are same :)

[@ictfan-ly8gh]

Yes . But the method video has ess code​@@siddharthgowd825

[@SachinSharma-k4s]

your teachin style are amazing bhai

[@chiragsharma8905]

My code with slightly more intuitive approach(according to me). O(log(n)+log(m)). Finding correct row first, and then finding target in that row. class Solution { public boolean searchMatrix(int[][] mat, int target) { int m = mat.length; if(m==0) return false; int lo = 0; int hi = m-1; while(lo

[@saswatrath4646]

great bhai same as my approach

[@srujangajjala2658]

log n + log m = log nm so time complexity is still same

[@RajNamdev_19]

@@srujangajjala2658 thanks for reminding me log formula I just forgot about it

[@muditsinghal6042]

I did the same 😂😂

[@chiragsharma8905]

@@muditsinghal6042 nice

[@sujarahaman2475]

Such a great Explanation! Thank you!

[@jhanavikumari274]

you are definitely doing some sorcery out there like how can you make learning this interesting .

[@cinime]

Understood! Super wonderful explanation as always, thank you very very much!!

[@sandhyarajput1642]

I am doing my dsa in python but for the approach I need to see your vidios and convert the code into python If before starting python I I know about you definately I learn Java but Thank you so much from bottom of my heart for best explanation

[@hardikpatel352]

Understood! Such a great explanation as always, thank you very much for your effort!!

[@rising_star17]

legendary explanation

[@poonam-kamboj]

very nice and clearly explained , thanks for the good explanation!!

[@dayashankarlakhotia4943]

Optimal approach. Public class solution { static boolean Search in matrix( Array list mat,int target){ int m=mat.size(),n=mat.get(0).size (); int low=0, high =m*n -1; while (low

[@aswinsrikanth408]

A great explanation as a whole bruh

[@kaichang8186]

understood, thanks for the great video

[@mrminus8590]

Thanks for everything brother

[@ArpanChakraborty-do6yz]

done and dusted❤‍🔥❤‍🔥just awesome

[@ankanmalik409]

dada make a video on - Divide two integers without using multiplication, division and mod operator

[@culeforever5408]

understood 😇

[@piyushmahale9024]

❤❤❤❤

[@ShahNawaz-cx3pi]

One more solution can be , first try to find out the correct row from 0th column (element in 0th column

[@abhishek-u7c]

we can apply binary search on column=0 on all arrays to find greatest element less then target. which takes log(row) time. and apply binary search on that row which takes log(col) time. 🙂

[@Gokul-gkl]

we only going to perform binary search only if the target is present on that row, so it always takes O(n*logm) which is the very worst case where all rows have the chance to have the target literally means the starting(first element on row) will be less than the target and the end(last element) will be greater than the target, which push all the row to get executed but having only one possible chance, in that case it will be O(n*logm) otherwise it will defenately going to be lesser than that

[@harshitpatil6138]

Understoood✌✌👍👍

[@Gokul-gkl]

0:57 Apple ecosystem spotted 😮

[@YourCodeVerse]

Understood✅🔥🔥

[@iampatelajeet]

Thanks Bhaiya 💯❤

[@theyashsawarkar]

very very helpfull explaination

[@NazeerBashaShaik]

Understood, thank you.

[@md.imrankhan6912]

Thank You Mr Legend

[@arihantjammar8888]

understood

[@AdityaAgrawal-fi7np]

You are best ... agar mei eak devloper bana tho you too get the credit

[@AdityaAgrawal-fi7np]

Aur aaj se tume videos mei crome mei dekuga brave mei nahi.

[@DSASimplified-zs6ll]

Bhai tu hero hai​@@AdityaAgrawal-fi7np

[@ashishpradhan6250]

amazing..thanku

[@bhushanambhore8378]

I solved it by this approach like, I applied binary search on row which eliminates unnecessary rows that doesnt contains target element, this results to a row which may or may not contain target element and applied again binary search on columns of resultant row which i eventually find out or may be not target elem is present. This take TC: O(Log M + Log N) which is equal to O(Log M*N)

[@EC20022ELAKKIYAC]

Understood thank you

[@devkirandass7930]

Striver is the best...Feel like worshipping him🥰

[@SandeepM0ttan]

Try kunal kushwaha then

[@devkirandass7930]

@@SandeepM0ttanyeah I know him....idk but I felt like he is too arrogant ....and he teaches JAVA and I am into C++

[@aspiring_Sr.dev_Om]

@@SandeepM0ttan kunal kushwaha is on another level

[@SandeepM0ttan]

@@devkirandass7930 gotta Admit He is a Little Arrogant but he teaches good

[@SampathM-24]

super cool!!🔥

[@erytymyeah]

You go crazy love that dude

[@artifice_abhi]

but its not necessary that if my target lies within the range it will surely be there for eg if an array is: 3 6 7 8 and target is 5 so now I would apply binary search as it is within my range but actually its not present. And this can happen for the rows where every time target is within the range but not present there. So in worst case time complexity would be: N*log(M)

[@harshilpatel3205]

No brother time complexity in the worst case stays as 0(n) + 0(log2(m)) ... Because once we find the answer we are returning the answer so it'll never go through each row...

[@Learnprogramming-q7f]

Thank you Bhaiya

[@shawshak2148]

understood thanks

[@aradhyapandey1489]

bhaiya...kitna bhayankar padhate ho🙏

[@oyeshxrme]

understood bhaiya

[@senseiAree]

Understood ❤

[@sanketatmaram]

understood!

[@nikhilkumarjamwal5322]

It can also be done in O(n).

[@sayantanpoddar5428]

Understood.............Understood!!!!! G.O.A.T

[@pulamollavenkatreddy8162]

Can we do this O( log(n)+ log(m)) by eliminating rows

[@abhisheknag1929]

yes

[@rohitsai806]

log(m) + log(n) = log(m*n) as per logarithms.. So both time complexities are same

[@KartikeyTT]

tysm sir

[@Ajeetkumar-uo4hf]

Striver Energy OP !!

[@lakshmanprabhu6722]

Which is lesser time complexity, log(m) + log(n) , or log(m*n) ?

[@rohitsai806]

both are same... log a + log b = log ab

[@hareshnayak7302]

Understood,thanks striver for this amazing video.

[@yatintripathi5638]

Hey Striver , I somehow find this question and Median in a row-wise sorted Matrix a bit similar , but my approach gets wrong when i try to flatten the matrix to find the median. Is my approach wrong towards the question?

[@harikakesharaju8799]

Same code u submitted is giving me TLE error for me sir

[@shashankgsharma0901]

Understood, but please take m x n instead of n x m, took i / m the whole time taking m x n, so got segmentation fault the entire time.

[@sarangkumarsingh7901]

Understood...............

[@abhinanda7049]

understood

[@graviton001]

Solved myself ❤

[@NARUTOUZUMAKI-bk4nx]

Understood

[@suryasaimaheswar8636]

understood :)

[@RituSingh-ne1mk]

Understood!

[@kundann_n9989]

Can we not do a binary srach on i to look for the row that contains the target the do binary search on that row to look for target?

[@ravitalaugh9017]

not working for [[1,1]]

[@umarfarooqshaik2504]

I think you may be divided with no.of rows instead of no.of cols, Do row= mid/x, col=mid%x; where x is no.of columns in a matrix (matrix[0].length)

[@ayushagarwal5271]

coded it down myself! thanks!!

[@cr00723]

cool

[@studyah]

bhaiya why did you take log of base 2?

[@saswatrath4646]

search space is reducing by half everytime we are doing mid = (low +high)/2. Anytime if you are reducing your working space by diving something your time complexity becomes log base to diviser. Had we been doing mid = (low + high)/5, just imagine it, our time complexity would have been log base 5. Hope it helps!

[@studyah]

@@saswatrath4646 thanks for explaining:) But I can't grasp why it happens...why the time complexity becomes log of base of the divisor

[@saswatrath4646]

@@studyah Search space is reducing from N to N/2 to N/4 to N/8 and so on.. why so ? bcz we are doing eliminating one half either left of right from the mid according to our situation. before you read any further 2^k means 2 raised to the power k. Here is the detailed explanation buddy. You can also write N, N/2, N/4, N/8..... as N/2^0 , N/2^1, N/2^2, N/2^3.....let's say it goes till 2/2^K. N/2^K = 1 hoga right ? kyuki last me 1 element == target hoga. Solve the equation, N = 2^k hog. Recall the formula of log and exponential or search it on google, if N = 2 ^ K then K = log base 2 of N. Now if you observer we are going from 1 to K right ? when we were at 1 we considered the whole array, when we were at k we comsidered only a single element. So, we moved from 1, 2, 3,...K. K number of iterations, now what is K that we found out above ? log base 2 of N. Time complexity will be O(k) =O(log base 2 of N) .

[@rushidesai2836]

Amazing solution

[@shloksharma-p7y]

bhaiya aap to ye optimal tak soch lete ho meri to bruteforce pe hi soch ruk jati hai iska kya karu abhi ek mahina ho chala phir bhi bruteforce tak hi logic ban raha hai

[@manikantachegu2182]

How about finding the row in which the element will be (by binary search ) and then applying binary search on the row can result in logn + logm crct me if im wrong because it worked for me in coding ninjas

[@apoorva5961]

😇

[@aniketdas4358]

why am i getting runtime error with this code bool find(vector &arr,int col,int target) { int lo=0; int hi=col-1; while(lotarget) { hi=mid-1; } else if(arr[mid]

[@saswatrath4646]

when u r asking out do mention type or name of the error, it wil assist the person trying to help u out.

[@saswatrath4646]

change col to mat[i].size() and row to mat.size(), and write the col inside the for loop before calling bool function it will work perfectly fine.

[@CodingJoySoul]

Please help Indians become candidate masters on codeforces.

[@deepakff7498]

peak intitution

[@mathsworldbysuraj6278]

i solved this in O(log n + log m)

[@nakulchauhan6713]

Your content and amount of effort is great. Huge respect for this course and you. But i feel you are not poking students to think, it appears as if you already know answer and here you are explaining it. Thought to process to come to a point should also be recorded. Lets say live solving DSA problems.

[@Fe-ironman]

You should watch this video only after going through the problems yourself

[@rahulhembram4519]

UnderStood

[@dayashankarlakhotia4943]

BF approach. Public class { static boolean search matrix (Array list mat,int target){ int m=mat.size(), n=mat.get(0).size (); for(int i=0;i

[@suryodhan3060]

actually you are keeping a lot of effort but unable to understand it 😭😭

[@cenacr007]

us

[@vcfirefox]

Why you have 728k subscribers but a monkey riding on cat will have 3 million subscribers.. god this is unfair

[@PrabhaKaran-36]

Understood❤

[@rajatshukla2605]

Understood!

[@KAMLESHSINGH-vr3bl]

understood

[@PrinceTripathi-j7u]

Understood

[@anshsaxena7297]

UnderStood

[@nayankhuman1043]

Understood ❤

[@chiragbansod8252]

understood

[@ganeshvhatkar9253]

Understood

[@anshsaxena7297]

UnderStood

[@shaiksoofi3741]

understood

[@abhishekprasad010]

Understood

[@arnabkundu1648]

understood

[@jasmeenjz]

Understood

[@shashankvashishtha4454]

understood