Search a 2D Matrix

The key idea

Because every row is sorted and each row's first value exceeds the previous row's last value, the whole matrix reads as ONE sorted list when flattened row by row. So you can binary-search the index range 0 .. m*n - 1 and map a flat index mid back to a cell with matrix[mid / n][mid % n].

Problem

You are given an m x n integer matrix matrix with two important properties:

- Each row is sorted in non-decreasing order from left to right.
- The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix, or false otherwise.

You must write a solution that runs in O(log(m * n)) time.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

Examples

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false

Complexity

Time: O(log(m*n)) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →