Search a 2D Matrix II

Write an efficient search for a target in a row-and-column sorted matrix.

matrix binary-search search

Write a function `search_matrix(matrix, target)` that takes a 2D list of integers `matrix` and an integer `target`. Each row of the matrix is sorted in ascending order, and each column is also sorted in ascending order. Return `True` if `target` is present in the matrix, otherwise return `False`. You may assume that the matrix is not necessarily square. For efficiency, aim for O(m + n) time, where m is the number of rows and n is the number of columns.

Your solution must work for empty matrices and empty rows.

Constraints

- 0 <= rows, cols <= 1000
- -10^9 <= matrix[i][j] <= 10^9
- -10^9 <= target <= 10^9
- Each row and each column is sorted in non-decreasing order.
- Aim for O(m + n) time and O(1) space.

Example

```python
>>> search_matrix([[1,4,7], [2,5,8], [3,6,9]], 5)
True
>>> search_matrix([[1,4,7], [2,5,8], [3,6,9]], 10)
False
>>> search_matrix([], 1)
False
>>> search_matrix([[]], 1)
False
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start from the top-right corner of the matrix.

Compare the current element with the target. If it is too large, move left; if too small, move down.

Think about why this greedy walk never misses the target.

Be careful with empty matrix or empty rows.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.