Binary Search in 2D Arrays

[@KunalKushwaha]

DSA + interview preparation playlist: kzbin.info/aero/PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ

[@AnkurKaushik-wx9zz]

why we didn't use Q1 approach in Q2?

[@nishasaini5886]

@@AnkurKaushik-wx9zz Q1: will take O(log row + log column) time, but Q2: will take the same as BS i.e., O(log n). It will reduce your time complexity

[@AkshatSinghal-o1z]

@@AnkurKaushik-wx9zz I had used Q1 approach in Q2 import java.util.Arrays; public class BinarySearch2D { public static void main(String[] args) { int[][] arr={{1,2},{6,7},{10,11}}; System.out.println((Arrays.toString(search(arr,10)))); } static int[] search(int[][] arr,int target){ int row=0; int col=arr[0].length-1; while(row=0){ if(arr[row][col]==target){ return new int[] {row,col}; } if(arr[row][col]

[@rwtNitin]

This course is the start of new era in indian education

[@Deep..86]

At 30:05 sir can you explain how kunal said that there is going to remain only 2 rows?

[@singletrackstatus1505]

​@@Deep..86 because of other half of the row .. the target is not there...

[@nirajangautam5919]

kunal : very simple stuff yeah cool me : ok ok and forgets after few seconds

[@OjasRawat-v6o]

was it for fun or ... 😕

[@pavan5524]

Lol, my college didn't even teach me binary search properly and this tutorial helped me learn it properly in 2D arrays as well.

[@siddharthsable7762]

watch the full series

[@pavan5524]

@@siddharthsable7762 huh?

[@siddharthsable7762]

@@pavan5524 full playlist I meant

[@pavan5524]

@@siddharthsable7762 oh, I am watching the full playlist.

[@avez0151]

In which year/semester they will teach us in college?

[@KaisarAnvar]

Just finished solidifying my understanding of binary search in the 4 hour video. Now I'm ready for THIS one. Feels great to know that what I'm learning ACTUALLY makes sense. BIG THANKS to you for your time and countless effort

[@khursheedreshi213]

This is definitely the best content on KZbin without any doubt. I have gone through a lot of content but this type of explanation I could find nowhere. Thanks a lot Kunal you are just awesome. Keep doing the good work.

[@KunalKushwaha]

Great to hear!

[@Deep..86]

At 30:05 sir can you explain how kunal said that there is going to remain only 2 rows?

[@ushakiran8549]

@@Deep..86 when we ignore either the rows above of the element, as the target, is > than the element we are on, or rows below the element as the target < than the element we are on, we only remain with 2 rows to search for.

[@howdyaniket4262]

Rather than checking in the mid column, if you check in the last column, you'll end up with just one row with the potential answer. Then apply BS just once in that particular row Code: static int[] search2(int[][] arr, int target) { int n = arr.length, m = arr[0].length; // apply BS on the last column, this way we can reduce the no of rows in which // we want to apply BS to just 1. int lb = 0, ub = n - 1, mid; while (lb < ub) { mid = lb + (ub - lb) / 2; if (arr[mid][m - 1] < target) { lb = mid + 1; } else if (arr[mid][m - 1] > target) { ub = mid; } else { return new int[] { mid, m - 1 }; } } // here lb == rb int ind = binarySearch(arr[lb], target); if (ind != -1) return new int[] { lb, ind }; return new int[] { -1, -1 }; }

[@fluxcy2396]

Great find man! Would you be kind enough to tell me what's the complexity of this code? Is it still O(logN) or O(logN+logM) with one binary search inside the other?

[@kanishkakaushik2862]

First binary search will be to find potential row in which our target may exist and the second binary search will be to find the target under our potential row. So, we are using two binary search. Hence, out time complexity will be O(logN + logM).

[@all-in-Recipes]

Excellent!

[@ipizza9941]

great solution. idk why kunal made it so much more complex than it needs to be lol

[@ishanvyas2178]

I also had the same doubt and did the solution myself. Glad i am not wrong lol

[@VaibhavGiri-m6f]

Great work kunal, at 18:46 The loop should go as r= 0 by this we'll get to reach the last element 50 at index (3,3) , but with r

[@akashtripathi9976]

So proud of you bro... Just posting the relevant stuffs for actual growth Nothing bullshits like roadmap to this and that....or resume or what to do in college...you have actually created the path for everything One just needs to walk over it and boom! Magic happens

[@t3dclutcher971]

I subscribed this channel today.. 😊 And you just crazy man... Clearing the mess spreaded by some the Indian bros. You sorted my life to success. Thnks a lot 🙌🏻🤩

[@KunalKushwaha]

Thanks for the sub!

[@t3dclutcher971]

Thank you so much yaar. 😊 I'm Sumit Bute, you Will have a look at my profile on linkedin 🙌🏻🤩

[@t3dclutcher971]

@@Shubham-qk8fw mujhe ya kunal bhaiyya ko

[@Shubham-qk8fw]

@@t3dclutcher971 To Kunal bhaiya

[@mayank4823]

@@KunalKushwaha bhaiya plzz upload videos in hindi also I'm requesting you .🙏🙏

[@shresthajha3454]

I don't think any other course can even come anywhere near it! Such precise and elaborate teaching!😃 Thank you!!!

[@AmritaMinj-cy3uz]

It is the best free course in ever seen . This course improve my coding journey and today i am topper of my class in computer.thank you bhay very much ❤❤❤❤.

[@bharattharwani7591]

This is one of the best courses, I have seen so far. And the content is so interesting that I can't wait to watch more and more. Amazing course but the algorithm for sorted matrix can be simplified. Thanks again for sharing this amazing free course.

[@pratikkapadnis9653]

we can also do this problem in a different approach like while row < len(matrix ) check if target < matrix[row][-1] then call binary search for (matrix[row], target, start = 0, end=len(matrix[row]) - 1) if the condition is false then row += 1 in this way we can also search the element in the matrix or 2d array

[@adityabedi266]

When I first saw the theory of 2D binary search i understood the concepts but when i tried to implement the theory logic into code by myself without watching the video code part i thought I will be able to do it but got confused mid-way about how can i take the middle column and how to eliminate the unnecessary rows then i give up and watched again and after my problem got resolved after i tried to implementing the code by myself again by following the theory steps. Thanks Kunal-sir.

[@sheheryaryousaf3664]

Hi kunal! i'm your subscriber across the border. Your way of teaching is really amazing. i have learnt far more from your playlist so far than i did in 4 years of my degree. currently im preparing for placement interview and your DSA course has given me enough confidence that now if i complete this course, i can crack any interview... PS: you can literally teach complete CS degree to students 😂

[@vaibhavsinghal4493]

Now its my third year and i saw your playlist and start learning dsa Sir it will help

[@vishantjadhav2552]

are you placed brother

[@vedwolf05]

what are you doing rn bro..?

[@narayanrakhecha2376]

have watched it once just to end it now doing all the assignments as well wonderfull course thanks so much kunal love u

[@pradeepravikoti]

An in depth explanation, from the video we can learn that first check what are the cases and then try to build the logic from there. Thanks man Kunal I learned BinarySearch in detail from this videos.

[@rajeshdas2295]

Even I watched only half of the video due to have less time but couldn't help giving a thumbs up to this Video!!! Really Helpful !!!!!!!!! Awesome!!!!!!!!!!

[@payalshekhawat7563]

Can't believe this is available for free.....the content 🖤

[@shubhamgoswami8751]

Aab lag rha mai dsa bahut acche se sikh rha ..... thank you bro aese mast video dalne ke leye

[@rithinpaulthomas4170]

I've not come across Binary Search in 2D arrays that's amazing. Thank you for all of your informative content Kunal. I'll be sure to tell you when I get a job using the knowledge you've shared in this course :)

[@rebhuroy3713]

I will not say anything.. Rather than the video related questions... Only i will follow, your videos 🤐.. Thanks man you are a cham.. 🙏

[@KunalKushwaha]

It's my pleasure

[@neojunwei_8544]

i dont even need to see the code, just based on your explanation i get the idea and is able to implement it myself. You explain really well!

[@iamabhayagnihotri]

As a beginner i want to confess that i can't understand the concepts at first time but i never give up i continue to watch until I get ✌️✌️ At the end i understand the concepts ✌️

[@shqnz]

Could you please share your LinkedIn profile or whatsapp no. ... Let's connect and code together

[@shivvratraghuvanshi522]

Do you understand it now bro?

[@iamabhayagnihotri]

@@shivvratraghuvanshi522 Absolutly✌

[@shivvratraghuvanshi522]

@@iamabhayagnihotri can you help me it now?

[@shivvratraghuvanshi522]

@@iamabhayagnihotri I can't even able to understand basic concepts my Mind is getting Frustrated as I can see you have been through this phase so no one can tell me better!

[@priyankjakharia6798]

just completed question 1 and kunal, I have to say it was simply too genius.....

[@RajeshKR-q3y]

Finally I'm learning optimized coading by this man😍

[@ananddangwal8424]

Thanks KK 👍

[@ramit1411]

This is the way it should be taught! The approach rather than theory or what not!

[@HimanshuTalodhikar-j1x]

no doubt the way u r teaching is absolutely revolutionary ,but i was able to code a very much little code for binary search in 2d sorted matrix . Thanx for making my concepts sharpened and clear 😄🤩

[@salik619]

For anyone facing problem in Q1, c would be initialized as c = matrix[0].length - 1; Very helpful videos as always Kunal, this is a boon for me as it's placement season

[@ayushagarwala1197]

I think we have to update the coloumn like matrix[r].length-1 when we r doing r--. Otherwise it is showing index out of bound for searching any bigger element not present in sample space.

[@sachinpandeyatd]

thank you, I felt like he did mistake there, so I came in comments just to confirm it

[@ajayjb8727]

Hi Kunal if we give Array input as {{1},{2}} and target -25. It is giving Array is out of bound error,. This is because for the given array cmid will be 0. At line 59, code is breaking because we are trying to evaluate matrix[0][-1]. Because of negative index (-1) we are getting Array is out of bound error. The code will work fine if column size is >2. I think to solve this problem first check target >= matrix[rstart][0] && target

[@iambasera]

i just applied binary search to unsorted array just by modifying little and keeping the steps same this I am able to achieve because of doing homework from my own ❤ I am working hard on this course 🙏

[@HARSHKUMAR-g2d6u]

Its really very good and it not just provide information about the question but its tell us how to think how to see the question and see the hidden pattern in it and then solve it easily because all the question hidden the pattern to solve it very easy and this is the course which tell us how to see that's hidden pattern to solve it easily I want your ashirwaad ( HINDI ) sir to get success

[@ishanjain7288]

An easier approach to Q.2 is to search for the floor (greatest element smaller than/equal to target) of target in the first column, and then apply binary search at the row which contains the floor element.

[@ismailrocky7096]

Right

[@akhilbisht798]

hey can you share a link for that solution

[@akashsingh-pm8pj]

any link for this the code ?

[@ameennoushad7973]

@@akashsingh-pm8pj I don't have a particular link for the solution, what you can do is use floor(provided in first part of binary search question) in the first column, then in the floor value, use simple binary search top to bottom in that column.

[@akashsingh-pm8pj]

Thank you @ameen naushad for you kind reply .. I found some such a simple answer with 100ms faster ..🙏🙏

[@entity2.089]

I hv met kunal in person. He is an amazing guy.. it was kinda like a dream for me to see him

[@civa-ji]

Thats what i want...😭 I searched soo many KZbin channel .to clear my matrix concept... Finally kunal bhiaya le hi aaye... Thank u soo much bhaiya❤️❤️💌

[@shubhankarjena6639]

I am really feeling very interesting but I can't understand the 3rd half and 4th half, and literally I have searched through the web,and the thing is 😮😮no ene even trying to explain the 1% of the question. You r the best bro.

[@deepankarmishra0823]

Bro you are just simply brilliant..... proud of you bro ❤️

[@PranjalChalak]

KK is rocking in every tut!

[@Murugagivesmelots]

Such a great man....and i like the word that u told hey kunal.. thank you so much Kunal..keep rock

[@it36shrutitiwari72]

Hi Kunal bhaiya, this is just an awesome DSA playlist and has made me fall in love with DSA. For Q2. I think if we first apply binary search in last column to find out the row whose element is greater than or equal to the target, then simply apply binary search in the row if not found the value already while traversing in the column to find the row. Please do tell if this is correct or not.

[@ccihicvickscl4614]

Yeah it can also work but what happen when there will multiple rows whose last element is greater than target then you will have to apply bineary search in all of them

[@shivshankarbk6228]

Really enjoying this course so far !!

[@NoxThreads]

G.T.O.A.T Greatest Teacher of all time @Kunal Kushwaha

[@venkatasurendra3683]

hey kunal ! Actually I run the Q2 without even changing a little bit of Q1 code and it successfully given output man

[@amitgaikwad8002]

It will run but the time complexity of the second code is less. Also you can't use the second code for the first question

[@venkatasurendra3683]

@@amitgaikwad8002 👍👍😊

[@amitmahato4876]

Yeh first code runs on O(m+n)

[@meetsoni1938]

Last Question is tricky to explain but you do it very well👍👍

[@APK_22]

A very confident and cool coder 😵‍💫

[@pawanyadav4024]

I tried the code on my own after going through video , and i wrote it on my own like cheesewalk. Awesome explanantion

[@RajeevRanjan-zl8nw]

another simple binary search approach for Q2: public static boolean search(int[][] mat,int target){ int row = mat.length; int col = mat[0].length; int low=0; int high=row*col-1; while(lowtarget) high=mid-1; else low=mid+1; } return false; } Time complexity = O(log(row*col))

[@sahadevnai8040]

hello kunal sir . found best course on youtube ever. thank u so much providing this content free. and in this part I think in first question in search method C should be matrix[0].length -1. since your code will only work on square matrix only.

[@vaibhavchougule-vs6fs]

your lectures are amazing and understandable thank you for teaching sir ❤❤❤❤❤❤❤❤❤❤😍😍

[@soumodipbhattacharjee3610]

Why this course is so addictive🔥🔥🔥🔥

[@aryanparishwad24]

Never thought coding could be fun... credit goes to Kunal ❤

[@Handsome_Coding2060]

Hey, Kunal I didn't get the Q.2 in one go. Also this is first time its happening that I didn't get in one go cuz when u explain u explain un such a fashion that saamne wala will surely gonna understand in a single watch. Gonna watch it again.

[@sashankbhardwaj8221]

this is the best course I have come across👍👍🙏

[@pkjio3719]

slightly different way for Q2: after we got final 2 rows compare 2nd row first element with target if (target < first_element) : perform binary search on 1st row you will get the target else : perform binary search on 2nd row you will get the target because as both rows are sorted 2nd row 1st element will be middle element , so target will either be in 1st row or 2nd row

[@sakshampathak9019]

these are the best lectures on binary search

[@adarsh_endeavour]

Every sec is full of information.

[@samarkhan87]

Hello kunal I'm third year student ...I started watching your videos from 2-3 days it's amazing really helpful ....in 2nd year I started programming from one of the KZbin channel they said after completing their course I will crack all top companies easily but I was only able to solve hackerrank easy level questions...so I just want to ask that will you please make a video for internships because my college is not that much good I just want you to tell that where to apply and what normal requirment should be their..like open source video you make

[@samarkhan87]

I really just want to follow your guidance

[@Deep..86]

At 30:05 sir can you explain how kunal said that there is going to remain only 2 rows?

[@pixyfirms130]

Best Course on KZbin

[@ran_domwtf]

Finally The Rock is come back to Home ❤. The Rock == "Kunal Bhai"" 😉

[@sameerakhatoon9508]

@26:06 we need to apply binary search in mid col only but not middle row like kunal did, cuz it doesn't work the same, say our target is 9, here mid row would be 5, 6, 7, 8 doing binary search, we get 6 element, then we eliminate the cols before the column which has 6 i.e., 0th col, 9 get out of our search space and hence if rows are sorted strictly then we consider a mid col and vice-versa

[@kartikjain5167]

best explaination ever

[@shehbazkhan2661]

In the second question we don't have to search in the first and the fourth halves because the target is anyway > matrix[rstart][cmid] and < matrix[rstart+1][cmid]

[@trueresources3847]

see what if the 2 rows remaining are the first 2 rows and the element you have to find is the first element {0,0}?

[@naveenkumarm4511]

I wish mself after finishing solve the problem of every question like u solving, thankyou Kunal😍

[@kunalsoni5385]

In Second Question, I though that the second condition in the if is unnecessary, Because binary search by default will search for start and end. Also we can take rEnd instead of rStart+1 because both had same value. Correct me if I am wrong somewhere. Anyways the course is much informative and clarifying. Kudos to the legend Kunal

[@omar-ec5mm]

BRO,YOU ARE JUST AMAZING!

[@mohammedadnan2449]

The other approach for Q2 would be:- =>Once we get rowStart and rowEnd after applying binary search. => Apply binary search for rowStart, if element is found return the index => If element is not found Apply binary search for rowEnd, if element is found return the index if element is not found return [-1,-1] Complete code in mentioned below:- //Time Complexity logN+logN+LogN=3logN==>O(logN) private static int[] searchElementIn2DArray(int[][] arr, int search) { int column = (0 + arr.length - 1) / 2; int rowStart = 0, rowEnd = arr.length - 1; //log N while (rowStart < rowEnd && rowStart != rowEnd - 1 && rowEnd != rowStart + 1) { int mid = (rowStart + rowEnd) / 2; if (arr[mid][column] == search) return new int[]{mid, column}; else if (search > arr[mid][column]) rowStart = mid; else rowEnd = mid; } //log N int res[] = binarySearch(arr, search, 0, arr.length - 1, rowStart); if (Arrays.toString(res).contains("-1")) { //log N return binarySearch(arr, search, 0, arr.length - 1, rowEnd); } else return res; } public static int[] binarySearch(int[][] arr, int find, int l, int h, int rowStart) { while (l

[@UtkarshSinghP]

why can't we simply use problem 1 code for 2???it will work fine for that aswell

[@yashu1703]

​@@UtkarshSinghP bcz prblm 1 code has time complexity O(n) and prblm 2 code has O(log N)

[@Aniket_0314]

@@UtkarshSinghP time complexity in problem 1 was O(n) and in problem 2 is O(logn + logm) which is lesser than problem 1

[@WolverineYt007]

@@UtkarshSinghP yes we can use but time complexity of first code is O(n+m) but for the second approach time complexity is O(log(n*m)) .

[@WolverineYt007]

@@UtkarshSinghP btw i am also DSE at infosys 😅😅

[@randomcreations3195]

Bro, i will meet you one day. You are my inspiration.

[@infamous667]

Last question was just lit🔥🔥🔥

[@rajupadhyay3103]

Thanks Dil se❤❤❤❤❤

[@beastytsimnt98]

Bro you r god i could solve second one without seeing your solution ❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤

[@geetankarkarmakar378]

The best explanation so far !!

[@vickymishra6926]

Great video! I really like how you explain the thought process at each step. It helps me understand how to think while approaching such problems. Thanks a lot.

[@ravinpandey8]

Unbelievable dsa course i found and also i subscribed.

[@VIDHANTIWARI-ze6ih]

I feel lucky that i got this playlist as a beginner in dsa

[@nishaswarnkar8636]

You are brilliant and the way you explain the stuff is just awesome❣.

[@rahit2964]

accha Kunal , why are you doing so much hardwork only for us ,,,, you are not getting anything ,, lots of love🖤🖤

[@1nvariant]

Seemed pretty complex at first but after understanding the logic it all feels so simple now

[@Jashu-er7gs]

Thankss for this lecture kunnu ❤❤

[@isi24.8]

Amazing this playlist is actually for free .. Thank you Kunal for the effort and work you put into creating such good content. I appreciate it !!

[@ashleymao-xx6vf]

Thank you sir for video on this topic as I was having difficulty in this topic in the assignment given by you , :)

[@vivektiwari1102]

thankyou sir. this video make me a confidence to attempt a question

[@DURGASREECHOWDHARYKOMMINI]

lots of love ❤for your hard work and great explanation bro, thanks a lot, this series brings big change in me ❤❤

[@vijaykumarmahendran3454]

Video is excellent 😇 from start till now i following your video but I felt little josh you were down in this video i can sense that Binary search video really ultimate feel each and every second 🔥🧨

[@codevoid]

Another brilliant video, thank you for the hard word Kunal !

[@civa-ji]

Because of you only kunal bhaiya...i am doing great in dsa. When i started study in 2nd year, i was not found any source who teach me dsa. So i paused there.... Now i am in third year. And i am following your course❤️. May be i am late for dsa. But my heart say if i follow your dsa path. I will definitely good in dsa. Thank you soo much kunal bhaiya💌❤️

[@YashTrivedi-iq3ft]

how are you doing now bro ? placed ?

[@BhanuPrakash-nz2ui]

Solution to Q2. Approach: We are just checking the elements in last column if the element is greater than target then our target must be in that row. So we apply binary search to only that row. Code: static int[] matrixsearch(int[][] matrix,int target){ int row=0; int col=matrix.length-1; while(row=0){ if(matrix[row][col]==target){ return new int[]{row,col}; } else if(matrix[row][col]

[@HarishssHarishss]

while(row=0) i have doute in this line why we are taking this condition

[@mudassirkhan5036]

@@HarishssHarishss to not to overflow from the given bound

[@lathifashaik5521]

Can you please tell, What is the time complexity of the method?

[@konkonabanerjee2003]

Amazing explanation Kunal!

[@rajsumanth9]

Very good explanation like an expert 😊

[@nomadshubham3907]

Kunal: delivering top notch content 🔥 Meanwhile other faang youtubers:being jealous and creating controversies 🙄.

[@RameshPatel-xq4vd]

Plz sir complete this wonderful series ❤

[@chalamalasuryanagendra8706]

Great🔥

[@_cricketshortsdaily_]

Majaa Aara Hai Re Bhiduuuuuuuu! 😍💯💯💯

[@rakeshkumarmaurya8265]

You are the best brother. 👍

[@abrahamlincoln5724]

For Q.1, if the matrix provided is not a square matrix, then a little correction is needed. "c" should be equal to the length of the the subarray - 1. That is *int c = matrix[0].length - 1;*

[@vikaspanwar5194]

kunal sir, The questions you have done here, I knew them already. HOW? In the binary search video explanation, you explained it really well, coz of that i was able to cover these questions already. BIG THANKS

[@atkt9387]

lecture accha hai👍

[@anshikgupta2993]

I wish I could've found this channel when I was in first year of my college. 🙏

[@ryomensukuna9513]

Bhai channel ek mahine pehle hi bna h

[@anshikgupta2993]

@@ryomensukuna9513 yeah thats what was I asking, wish it was available from the start of my college