Search a 2D Matrix - Leetcode 74 - Python
Vložit
- čas přidán 26. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: neetcode.io/problems/search-2...
0:00 - Read the problem
1:40 - Drawing Explanation
6:42 - Coding Explanation
leetcode 74
This question was identified as a microsoft coding interview question from here: github.com/xizhengszhang/Leet...
#binary #search #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 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.
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
Nicely explained. I tried another approach with just 1 binary search over whole matrix converting search index to coordinates. Resulting code is more concise.
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
Really love your explaination! Could you make a video list of google interview coding questions(high frequency)?
This is a pretty tough one! Tons of edge cases.
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)
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.
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
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 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
Thank you dude!
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)
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
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
Solved it before watching the video because your 150 Roadmap says "binary search" which was a HUGE hint. Gonna see your solution now.
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.
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?
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.
Thanks for the amazing content
Glad it's helpful!
This solution now shows the time limit exceeded.
getting the same thing
Thanks Neetcode
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)
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
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?
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))
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
7:58 WHYYYY GOOOOD I KNEEWW IIITT !!! :'D
Neetcode, memorizing this sh1t for google!
Who else freaked out at 8 minutes when he switched the top / bottom update on accident? 😂 Thought I was going mad.
pro tip: you can use else on a while loop statement
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.
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.
Thanks
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
converted into single array and then did binary search
emp = []
for e in matrix:
emp = emp + e
recalculating the row before the row search loop is redundant as the value of row remains same throughout..
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
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.
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
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?
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;
}
}
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
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 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
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
shouldn't it be if not (bot
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
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
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
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
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?
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
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
understood
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
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
for i in matrix:
if target in i:
return True
return False
this works too 🤣
and for some reason, this computes faster
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!
why recalculate row?
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!
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
You a 2d binary search matrix God😢
why c++ and java code is smaller than python :)
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)
Don't you think this is unnecessary?
after breaking while loop
row = (top + bot) // 2
Code will just work fine without this
soon i will crack google too.
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`.
This shouldn't be a medium, it's a very easy question.
it still is a medium on leetcode