Search a 2D Matrix - Leetcode 74 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
6:42 - Coding Explanation

leetcode 74

#binary #search #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[canete_code]

God knows how many people have landed job thanks to this man. Thanks a lot Neetcode

[yt-user-]

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.

[parthbrahmbhatt]

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"

[ryankawall]

Dude you’re awesome !!! I don’t what I’d do without these videos ..

[JyotiKumari-dgoq]

Thanks, NeetCode for the amazing content.
Your daily video inspires me a lot.
Keep doing this amazing work.

[OMFGallusernamesgone]

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

[haymasunder]

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

[andreytamelo]

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 <= right)
{
int middle = left + (right - left) / 2;

(int row, int column) = Math.DivRem(middle, columns);

if (matrix[row][column] == target) return true;

if (matrix[row][column] < target)
left = middle + 1;
else
right = middle - 1;
}

return false;
}
}

[aspisov]

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 <= r:
mid = l + (r - l) // 2
i, j = mid // m, mid % m
if matrix[i][j] < target:
l = mid + 1
elif matrix[i][j] > 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)

[krzysztofsobocinski]

Nicely explained. I tried another approach with just 1 binary search over whole matrix converting search index to coordinates. Resulting code is more concise.

[ahmadmtera]

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.

[sumkid]

I loved this problem, if you could understand and implement binary search, then you have everything you need to solve this.

[shush]

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

[bluesteel]

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)

[ddshoo]

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 <= r:
mid = (l + r) // 2
midRow = mid // len(matrix[0])
midCol = mid % len(matrix[0])
if matrix[midRow][midCol] > target:
r = mid - 1
elif matrix[midRow][midCol] < target:
l = mid + 1
else:
return True
return False

[sodo]

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.

[hr]

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

[stylisgames]

This is a pretty tough one! Tons of edge cases.

[roguenoir]

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.

[urlvo]

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.