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.
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.
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.
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"
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
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;
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
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)
Nicely explained. I tried another approach with just 1 binary search over whole matrix converting search index to coordinates. Resulting code is more concise.
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.
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.
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?
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.
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
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)
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
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 }```
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
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
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.
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
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
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; } }
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. :)
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)
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))
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
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
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.
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.
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.
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
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
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.
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
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
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.
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
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
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!
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)
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`.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
God knows how many people have landed job thanks to this man. Thanks a lot Neetcode
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.
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.
Yeah, playing with the indices itself makes things much easier!
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.
the multiple binary searches strategy should have better worst case perf. log m + log n vs log mn
@@prunesalad no, cause log m + log n = log mn
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"
Dude you’re awesome !!! I don’t what I’d do without these videos ..
Thanks, NeetCode for the amazing content.
Your daily video inspires me a lot.
Keep doing this amazing work.
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
Good point, I think you are correct
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
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
both solutions are log mn
Log (m+n)
Yep, this is the way. What's presented in the video is waay overcomplicated
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)
Nicely explained. I tried another approach with just 1 binary search over whole matrix converting search index to coordinates. Resulting code is more concise.
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.
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.
that was what he had i think
He had it right at 4:30 but wrote it wrong by accident at the end
well if there is one row and 1000 columns for example, that would be log(m*n) technically worst case
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.
Wait till you discover log properties
I loved this problem, if you could understand and implement binary search, then you have everything you need to solve this.
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?
That row variable only exist in the first while loop
it works fine without those 3 lines
#if not (top
@@rabeasayed8368 works fine yes , but without the
if not (top
Thank you very much man
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.
I thought I was going crazy. when I saw that too. You're right, we already have the row in memory.
yes
Yeah we already have that same calculation stored in memory. That is redundant but maybe its to help people visualize it better
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
This is a pretty tough one! Tons of edge cases.
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)
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
Solved it before watching the video because your 150 Roadmap says "binary search" which was a HUGE hint. Gonna see your solution now.
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
}```
you do leetcode in swift?
Really love your explaination! Could you make a video list of google interview coding questions(high frequency)?
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
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
thank you!
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
recalculating the row before the row search loop is redundant as the value of row remains same throughout..
Who else freaked out at 8 minutes when he switched the top / bottom update on accident? 😂 Thought I was going mad.
what is the need for line 15 to 17 ? we have already checked the top
Yes, no need to do row = (top + bot)// 2 second time since we already found our row.
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.
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
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
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
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
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;
}
}
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. :)
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)
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))
that's linear time complexity and a one-way ticket to a failed interview
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
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
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.
If you put all the values into a single list then that would be an O(n) operation.
@@bigbigdog No it would be log(m*n) because you are essentially gonna perform binary search on m*n elements
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.
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.
Maybe you can do it in O(n + m), because we can use the ordering of the matrix elements and reduce the checks
Sure, but O(n + m) > O(log(n*m))
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
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!
Thank you dude!
league client tick noise at 6:53 was confusing me. thought it was mine
I don't hear it? I only hear his keyboard sound?
cmiiw 9:42 at this point the row can just be taken in top or bottom without // 2, it guaranteed to be same
Instead of the second while loop, you can just do `return target in matrix[row]`
but what would the implementation of "return target in matrix[row]" be?
converted into single array and then did binary search
emp = []
for e in matrix:
emp = emp + e
when u traverse the matrix, it will be O(m * n). so whole program will be O{(m * n) + log(m + n)}
you need to write the program in log(m+n)
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.
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
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
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.
Thanks Neetcode
I'm curious for my understanding does each row in the matrix have to be the same identical length?
according to the statement, the sizes are fixed M x N
I iterated over the list and then did binary search like normal afterwards
for ra in matrix:
if ra[-1] < target:
continue
your approach would be n * log m I guess since you have to iterate over all n rows
Thanks for the amazing content
Glad it's helpful!
W vid lb
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
This code doesn't pass the test cases on the problem, for instance [[1],[3],[5]] does not work
Its working fine for me
@@hr3392 yea I ended up getting it working too. I can't remember what it was but it was my fault
7:58 WHYYYY GOOOOD I KNEEWW IIITT !!! :'D
Why does "if not (top
因为如果target很大，top就会一直+1，直到比bot还大，这个时候就证明target不在matrix里。同理，如果target很小，bot一直-1，直到-1，比0小，这个时候target不在matrix里。
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
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
understood
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.
This solution now shows the time limit exceeded.
getting the same thing
For me it works perfectly
pro tip: you can use else on a while loop statement
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
shouldn't it be if not (bot
no. that's what not is for. or we can rewrite if(top > bot) return false
for i in matrix:
if target in i:
return True
return False
this works too 🤣
and for some reason, this computes faster
Thanks
Can anyone explain how "if not(top < = bot): return False" immediately returns True if the target value is not in the matrix?
"if not(top
why recalculate row?
Neetcode, memorizing this sh1t for google!
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.
that sounds like O(mn) complexity
why c++ and java code is smaller than python :)
int binarysearch(int target , vectornums){
int left=0;
int right=nums.size()-1;
while(left
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
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!
You a 2d binary search matrix God😢
Don't you think this is unnecessary?
after breaking while loop
row = (top + bot) // 2
Code will just work fine without this
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)
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`.
soon i will crack google too.
This shouldn't be a medium, it's a very easy question.
it still is a medium on leetcode
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)).
thanks