🚀 neetcode.io/ - A better way to prepare for Coding Interviews
@canete_code7 ай бұрын
God knows how many people have landed job thanks to this man. Thanks a lot Neetcode
@yt-user-993 жыл бұрын
No need to do multiple binary searches. Since it is sorted top to bottom, and left to right, you can basically treat the 2d matrix as a single array where left = 0 and right = height * width - 1. In each iteration just calculate the rows and columns as such: row = floor(mid / width), col = mid % width.
@chenjus3 жыл бұрын
this is also a convenient trick for golfing a nested for loop! slight tweak if you're using python, can do hard divide mid//width, so don't need the additional function call to math.floor.
@arminphulkar2 жыл бұрын
Yeah, playing with the indices itself makes things much easier!
@pranavsharma74792 жыл бұрын
bro if interview you forget the formula of conversion then ? also there are main issues in this approach, 1. m (rows) , n(cols) when you go mn it may cause overflow.
@prunesalad2 жыл бұрын
the multiple binary searches strategy should have better worst case perf. log m + log n vs log mn
@xenomagpie44842 жыл бұрын
@@prunesalad no, cause log m + log n = log mn
@parthbrahmbhatt26192 жыл бұрын
Felt like I was listening to Dora when he asked me, "Do you know an algorithm that can search a target value in a sorted array? **Brief pause** I know of one, called Binary Search"
@haymasunder26383 жыл бұрын
Very good explanation, But do we need to specify row=(top+bot)//2 again since once we break out of the first loop we already have the row to be searched with us
@NeetCode3 жыл бұрын
Good point, I think you are correct
@OMFGallusernamesgone2 жыл бұрын
I was so happy I solved this myself after doing the 2 Blind75 problems. I did it different/arguably easier: just do binary search and pretend the list is already concatenated, to get the mid value, write a decrypt function which is just row = idx % row_len, col = idx // row_len
@minciNashu2 жыл бұрын
both solutions are log mn
@vinprabhu6 ай бұрын
Log (m+n)
@ClassicalRaritiesChannel4 ай бұрын
Yep, this is the way. What's presented in the video is waay overcomplicated
@JyotiKumari-dg3oq3 жыл бұрын
Thanks, NeetCode for the amazing content. Your daily video inspires me a lot. Keep doing this amazing work.
@andreytamelo11832 жыл бұрын
For curious, imo there is a bit more intuitive and straightforward solution which exploits the property stated in the problem description: "The first integer of each row is greater than the last integer of the previous row.". It essentially gives us right to interpret the matrix as a regular single-dimension array via a simple index -> (row, column) translation math. (C#) public bool SearchMatrix(int[][] matrix, int target) { int left = 0; int rows = matrix.Length; int columns = matrix[0].Length; int right = rows * columns - 1; while (left
@ryankawall35503 жыл бұрын
Dude you’re awesome !!! I don’t what I’d do without these videos ..
@krzysztofsobocinski22072 жыл бұрын
Nicely explained. I tried another approach with just 1 binary search over whole matrix converting search index to coordinates. Resulting code is more concise.
@urlvo2 жыл бұрын
Hello, I really like your answer, optimal and easy to grasp! I however feel like after finding the targetRow after the first while loop, we do not need to row = (top + bottom) // 2 before the second while loop; we already have row in memory.
@rparsons7792 жыл бұрын
I thought I was going crazy. when I saw that too. You're right, we already have the row in memory.
@sharangkulkarni1759 Жыл бұрын
yes
@erickmercado17117 ай бұрын
Yeah we already have that same calculation stored in memory. That is redundant but maybe its to help people visualize it better
@elab4d140Ай бұрын
I think he did that because he thinks it will go out of scope when it reaches the second loop, but in python, variables defined within a function are not limited to the scope of the block in which they are created
@aspisov2 ай бұрын
we can just assume we have an array instead of matrix and then decode our array index (convert into i, j) n, m = len(matrix), len(matrix[0]) l, r = 0, n * m - 1 while l target: r = mid - 1 else: return True return False this is btw a very useful trick for solving some linear algebra problems (nxm matrix is isomorphic to R^(nxm) vector)
@roguenoir2 жыл бұрын
Since each row and column is sorted and the last value in one list is smaller than the first value in the subsequent list, you can simply join all the consecutive lists together into one huge list and do binary search on that one. This may take extra memory and modifies the input. But if we don't want to take extra memory and don't want to modify the input, we can use that same logic and pretend we're working with a single list and use a function to map an index on that large list to a cell in the matrix. I do it this way: h = len(matrix) w = len(matrix[0]) def translate(x): col = x % w row = (x - col) // w return row,col Then do a binary search on a "list" of length h*w with i = 0 and j = h*w - 1 but you use the translate() function to convert the 1-D index into the 2-D index to look up the value in the matrix.
@bigbigdog Жыл бұрын
If you put all the values into a single list then that would be an O(n) operation.
@jude392611 ай бұрын
@@bigbigdog No it would be log(m*n) because you are essentially gonna perform binary search on m*n elements
@tenkara10110 ай бұрын
I'm wondering why this isn't the best answer. It's easy to visualize, works just as fast at O(log m*n) since we're operating on a m*n length array once the 2D array is translated. @bigbigdog that would be incorrect, because we're just doing binary search on m*n elements. Therefore it takes O(log m*n) time.
@exdoth13769 ай бұрын
Putting the values of the matrix into a list has time complexity O(n). Consider a matrix with m rows but only 1 column (like a vector), to translate this matrix to an array you have to access every single row and thus every single item (since the number of rows is the number of items because each row has 1 item) so in the end it becomes a linear operation.
@sodo38722 жыл бұрын
I think the O time is Logm + Logn, instead of Logm * Logn. Is it so? Because after the binary search of rows, we have narrowed down the search scope to one row. Then we only need to do another binary search for that one row, instead of every row.
@Mo-cn9kd Жыл бұрын
that was what he had i think
@fogotunde-onadele8016 Жыл бұрын
He had it right at 4:30 but wrote it wrong by accident at the end
@thisguylives382710 ай бұрын
well if there is one row and 1000 columns for example, that would be log(m*n) technically worst case
@technophile_6 ай бұрын
log(m) + log(n) can be written as log (m * n), ie log(m) + log(n) = log (m * n). This is known as the product property of logarithms.
@Nazgenyanly2 ай бұрын
Wait till you discover log properties
@bluesteel17 ай бұрын
Lower bound on the last column to find row than binary search on that (log mn) Iterative where you start at the top right go down if array element is smaller go left if array element is larger (m + n)
@ahmadmtera19 күн бұрын
You could've used an auxiliary function to do the 1D Binary Search (Divide a Large Problem into Smaller Ones Strategy). This would allow you to put "return helper(...)" in the else statement at line 13 and a "return false" at line 14 and erased everything from line 15 onwards.
@sumkid926327 күн бұрын
I loved this problem, if you could understand and implement binary search, then you have everything you need to solve this.
@hr33922 жыл бұрын
I don't think we need to check for bottom exceeding top after the first binary search. It worked fine without that portion of code. The break statement would only be hit when the condition for the while loop is valid, so I think the check is not needed
@nguyentuan19903 ай бұрын
correct me if i am wrong, but after the first binary search, we would know exactly which row the target belong to? meaning you dont have to do row = top + bottom // 2 on the second binary search. But at this point, top and bot row are pointing at the same row and for sure contains target and can be treated as an array?
@tuandino69902 ай бұрын
That row variable only exist in the first while loop
@zapuhlyak9 ай бұрын
Thank you for your videos! They are really helpful for me. I decided to share with you my approach with only one loop. This code in Swift. ```func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool { let rows = matrix.count let columns = matrix[0].count var left = 0 var right = rows * columns - 1 while left target { right = middle - 1 } else if value < target { left = middle + 1 } else { return true } } return false }```
@Isaac-gz8wx6 ай бұрын
you do leetcode in swift?
@vividviking6187 Жыл бұрын
I came up with this thinking that it would be log (m * n). Could someone confirm, my thinking is that by using only the first and last element, continuing and not searching the sub list would the same as ignoring it. Is it the same efficiency or would mine be worse? class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for r in range(len(matrix)): low, high = 0, len(matrix[r]) - 1 if target > matrix[r][high] and target < matrix[r][low]: continue else: while low target: high = mid - 1 return False Edit: I recognized that I would still need to visit each row at least once so it probably would have been O (m logn) instead. Implemented a binary search on both rows and column and corrected the issue.
@eshabaweja Жыл бұрын
Solved it before watching the video because your 150 Roadmap says "binary search" which was a HUGE hint. Gonna see your solution now.
@ddshoo52824 ай бұрын
i just modelled it after the basic binary search solution lol: class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: l = 0 r = len(matrix) * len(matrix[0]) - 1 while l target: r = mid - 1 elif matrix[midRow][midCol] < target: l = mid + 1 else: return True return False
@kumareshnatarajan46142 жыл бұрын
A simpler method is to flatten a 2d array by adding it with a empty list, and then checking if target is in the flattened list, 4 lines of code.
@WeirdAlSuperFan Жыл бұрын
that sounds like O(mn) complexity
@Ragdoll333-q5l3 жыл бұрын
Really love your explaination! Could you make a video list of google interview coding questions(high frequency)?
@souvikbhattacharya90822 жыл бұрын
what is the need for line 15 to 17 ? we have already checked the top
@surajthapa58088 ай бұрын
Yes, no need to do row = (top + bot)// 2 second time since we already found our row.
@cristianh.valderrama16033 жыл бұрын
Hello, I am looking for how to perform a search in a 2d array vertically, horizontally and diagonally (right and left) of 4 equal characters, example "AAAA" and see how many times it is repeated, what algorithm do you recommend? I have looked for it but not I know which one to choose, lower cost and time. It is a nxn array, thanks to your help it would be very useful. PS: Sorry my english, I'm using google translator
@DarylKielMora9 ай бұрын
Since we only need to know if the target value is in one of the lists inside the matrix parameter, I decided to just check if the target value exists in the list for the corresponding middle index I get from binary searching. Here's my take on it in python3: class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: start, end = 0, len(matrix) - 1 while start target: end = mid - 1 else: start = mid + 1 return False Thank you for the videos, NeetCode!
@dusvn14842 ай бұрын
I think I solve this on easy way. I listen your lecture for recursion and it's not same for this problem but I identify we need to do search for every row until we find value or mby not. I say this for recursion becouse I identify base problem for every row of matrix So how I solve this: 1.Write function for binary search 2. Go in loop thought all lists and if return value of binary search for single list is != -1 just return true 3. After for loop just return False becouse we go thought all list and we don't find target value I hope this help for us guys :D
@harishsn48662 жыл бұрын
Hey, just a small doubt. in the first while loop, when target > matrix[row][-1] and target < matrix[row][0] fails, we are breaking out of the loop. I was thinking what if the target == matrix[row][-1] or target == matrix[row][0], then we can just return True. I did try this but it shows "Time Limit Exceeded". I could not understand why it doesn't work. Can you please shed some light on this? while top matrix[row][-1]: top = row + 1 elif target < matrix[row][0]: bottom = row - 1 elif target == matrix[row][-1] or target == matrix[row][0]: return True
@Ajay-cs5lf Жыл бұрын
the third condition should not be like this. Because the target value might be falling into the range, not the exact left most position or right most position. try this out: elif target >= matrix[row][0] and target
@stylisgames3 ай бұрын
This is a pretty tough one! Tons of edge cases.
@AcademictoIndustrytalk2 жыл бұрын
One can use itertools.chain() for one line solution. This also valid for problem search 2d matrix II (leetcode 240). return target in list(chain(*matrix))
@WeirdAlSuperFan Жыл бұрын
that's linear time complexity and a one-way ticket to a failed interview
@oguzcan123 Жыл бұрын
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: k = 0 for i in range(len(matrix)): p = matrix[k][0] s = matrix[k][len(matrix[k]) - 1] print(p, s) if p
@thndesmondsaid Жыл бұрын
Funny, I always thought of the first row of the matrix as the "bottom", and the last row as the "top"... thinking about it from an ascending order. Had to realize that I had those swapped to debug my own solution here lol.
If the while loop ends due to the pointers crossing, it means that the binary search was not able to find a row that would contain the target
@shush587810 ай бұрын
class Solution(object): def searchMatrix(self, matrix, target): l = 0 while len(matrix) - 1 >= l: if target in matrix[l]: return True else: l += 1 return False
@Priyam6F4 Жыл бұрын
Intuition This problem will purely be solved on the core principles of how a 2D matrix works,its traversal and a few comparisons. Approach We assign i=0 and j=n-1, means i is at start of the row and j is present at the start of the last column. We start comparing from j=n-1. Basically,the comparison is starting from the last element of the first row. Now,if observed closely, the last element of the first row, moving downwards from there will always result in a greater value as the 2D Matrix happens to be sorted. If target is smaller, there is no point moving down. Hence, we decrement j and move to the previous column. We check again, if target is still smaller (matrix[i][j]>target) we decrement j again. observe one thing. As we move from the extreme right to left, we notice that values are eventually decreasing for the ith row. So we are bound to reach a point, where matrix[i][j] has a smaller value than target. If so, we now increment i and move to the row below,which gets us closer to the target. Finally we reach a point where we find the target. Complexity Time complexity: O(m+n) Space complexity: O(1) Code class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; // row int n = matrix[0].length; // col int i = 0; int j = n - 1; while (i >= 0 && i < m && j >= 0 && j < n) { if (matrix[i][j] == target) { return true; } else if (matrix[i][j] > target) { j--; } else if (matrix[i][j] < target) { i++; } } return false; } }
@JamesBond-mq7pd10 ай бұрын
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROW, COL = len(matrix), len(matrix[0]) left = 0 right = ROW * COL - 1 while left target: right = mid - 1 elif matrix[row][col] < target: left = mid + 1 else: return True return False
@jocelynwang62708 ай бұрын
thank you!
@keyursolanki2 жыл бұрын
Love the way you explain the structure and way to solve the algo. But do we need the second binary search for the element is present in a single row or not. We can do that if we want to find the index of that element but here all we need is that if the element is present or not. Please correct me if I am wrong. Thanks again for your support. :)
@jude392611 ай бұрын
You have the right idea..however, if you did that it would be log(m)*n because you did binary search on rows and then went through every element in that row of n elements to check for the target( "return target in row" is O(n) because it searches every element in that row)
@rasulsilva29852 жыл бұрын
This code doesn't pass the test cases on the problem, for instance [[1],[3],[5]] does not work
@hr33922 жыл бұрын
Its working fine for me
@rasulsilva29852 жыл бұрын
@@hr3392 yea I ended up getting it working too. I can't remember what it was but it was my fault
@henryCcc8614 Жыл бұрын
I don’t think there’s a need for all that. Set current value to the top right, if target less than current, col-1, if target greater than current, row+1, else return current value.
@CeciliaBarnes-f8n11 ай бұрын
Instead of the second while loop, you can just do `return target in matrix[row]`
@pepperdayjackpac452111 ай бұрын
but what would the implementation of "return target in matrix[row]" be?
@victoronofiok45512 жыл бұрын
shouldn't it be if not (bot
@MrRenaissance172 жыл бұрын
I'm curious for my understanding does each row in the matrix have to be the same identical length?
@minciNashu2 жыл бұрын
according to the statement, the sizes are fixed M x N
@hwang160711 ай бұрын
You can solve this by converting regular indices to 2d array indices: class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROWS = len(matrix) COLS = len(matrix[0]) l = 0 r = ROWS*COLS - 1 while l = midnum: l = mid + 1 else: r = mid - 1 return False
@thekiran3 ай бұрын
recalculating the row before the row search loop is redundant as the value of row remains same throughout..
@jasonahn8658 Жыл бұрын
Can anyone explain how "if not(top < = bot): return False" immediately returns True if the target value is not in the matrix?
@The6thProgrammer Жыл бұрын
"if not(top
@AniruddhaShahapurkar-wu3ed9 ай бұрын
Another variant: Key is always starting from top right corner of the matrix. But the time complexity of this is O(m+n) class Solution(object): def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ r = 0 c = len(matrix[0])-1 print(len(matrix)) while r < len(matrix) and c >= 0: if matrix[r][c] < target: r += 1 elif matrix[r][c] > target: c -= 1 else: return True return False
@dragtr0n7 ай бұрын
converted into single array and then did binary search emp = [] for e in matrix: emp = emp + e
@xushengchin5116 ай бұрын
Somehow the code doesn't work on case 1: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] target = 3 Code from video: ```python class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROWS, COLS = len(matrix), len(matrix[0]) top, bot = 0, ROWS - 1 while top matrix[row][-1]: top = row + 1 elif target < matrix[row][-1]: bot = row - 1 else: break if not (top
@david_tgridy11 ай бұрын
I iterated over the list and then did binary search like normal afterwards for ra in matrix: if ra[-1] < target: continue
@raphaelespanha45543 ай бұрын
your approach would be n * log m I guess since you have to iterate over all n rows
@ivayloarnaudov78162 жыл бұрын
Maybe you can do it in O(n + m), because we can use the ordering of the matrix elements and reduce the checks
@DavidDLee Жыл бұрын
Sure, but O(n + m) > O(log(n*m))
@vikaschauhan3845 Жыл бұрын
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for row in matrix: if target == row[0] or target == row[-1]: return True elif target > row[0] and target < row[-1]: low = 0 high = len(row) - 1 while low row[mid]: low = mid + 1 else: return True return False
@fizruk76447 күн бұрын
Yall there's an easier solution: m = len(matrix) # rows n = len(matrix[0]) # columns l = 0 r = m * n - 1 while l matrix[mid_m][mid_n]: l = mid + 1 elif target < matrix[mid_m][mid_n]: r = mid - 1 else: return True return False
@ok-cr3yd Жыл бұрын
10:10 I think you misspoke here. If the target is smaller than the midpoint, you want to search to the left of it, not the right
@harijoel Жыл бұрын
pro tip: you can use else on a while loop statement
@anasraza2000 Жыл бұрын
My Solution : class Solution: def searchMatrix(self, matrix: list[list[int]], target: int) -> bool: that_row = 0 for i in range(len(matrix)): if matrix[i][-1] >= target : break else : that_row += 1 try: if target in matrix[that_row]: return True except: return False
@EmorinkenАй бұрын
Thank you very much man
@valkon_2 жыл бұрын
Holy, did this really got 2k likes more since June? Damn everyone is leetcoding, get your jobs now guys it will be a bloodbath soon.
@myname9114Ай бұрын
Is this a good approach class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: oL, oR = 0, len(matrix) - 1 while oL matrix[mid][-1]: oL = mid + 1 else: arr, il, ir = matrix[mid], 0, len(matrix[mid]) - 1 while il arr[imid]: il = imid + 1 else: return True return False
@sahilarora4602 Жыл бұрын
Thanks Neetcode
@oneke4498 Жыл бұрын
7:58 WHYYYY GOOOOD I KNEEWW IIITT !!! :'D
@ahmedzedan17722 жыл бұрын
Thank you dude!
@sharangkulkarni1759 Жыл бұрын
why recalculate row?
@shadowwolf5578 Жыл бұрын
why c++ and java code is smaller than python :)
@rojinprajapati68409 ай бұрын
This solution now shows the time limit exceeded.
@brentmarquez90578 ай бұрын
getting the same thing
@antony90582 ай бұрын
For me it works perfectly
@jakearmijo2 жыл бұрын
league client tick noise at 6:53 was confusing me. thought it was mine
@ethanhsu6761 Жыл бұрын
I don't hear it? I only hear his keyboard sound?
@mr64622 жыл бұрын
Thanks for the amazing content
@NeetCode2 жыл бұрын
Glad it's helpful!
@GoziePO7 ай бұрын
Who else freaked out at 8 minutes when he switched the top / bottom update on accident? 😂 Thought I was going mad.
@naimeimran32472 жыл бұрын
Thanks
@cloudboysmusic52232 жыл бұрын
Neetcode, memorizing this sh1t for google!
@yugaank100 Жыл бұрын
for i in matrix: if target in i: return True return False this works too 🤣
@yugaank100 Жыл бұрын
and for some reason, this computes faster
@malarkodibalakrishnan79613 ай бұрын
Don't you think this is unnecessary? after breaking while loop row = (top + bot) // 2 Code will just work fine without this
@coliv22 ай бұрын
It seems that this guy doesn't know that log(n*m) = log n + log m, in other words, the more complex algorithm is completely irrelevant, you can just consider the matrix as a big array and do bin search only once!
@indhumathi5846 Жыл бұрын
understood
@AtulSharmany4 ай бұрын
would n't it be easier to do this: key is to translate 2d index to 1d index ------------------------------------------------------------------ t = len(d[0]) * len(d) def search(l1, r1): if l1 >= r1: return -1 m = l1 + ((r1 - l1) // 2) r2, c2 = m // 4, m % 4 diff = target_value - d[r2][c2] if diff == 0: return (r2, c2) , d[r2][c2] elif diff > 0: return search(m + 1, r1) else: return search(l1, m - 1) return -1 res = search(0, t - 1)
@edwardteach24 ай бұрын
You a 2d binary search matrix God😢
@indraxios Жыл бұрын
soon i will crack google too.
@therealjulian12766 ай бұрын
Surprisingly bad solution, this won't even be accepted as a solution on LC anymore. I suggest doing a regular binary search and use `row = mid // cols` and `col = mid % cols`.
@dk20can862 жыл бұрын
This shouldn't be a medium, it's a very easy question.
@minciNashu2 жыл бұрын
it still is a medium on leetcode
@kenkaneki5433Ай бұрын
u should have made binary serach for top and bott. not increasing and decreasing just by one. this way its still linear so u got O(m) + O(log(n)).