medium

Search a 2D Matrix

Find a target value inside a matrix where each row and column is sorted.

1. Define the problem

Search a 2D Matrix

You are given an m x n matrix where every row is sorted left to right, and the first value of each row is greater than the last value of the row before it. This means the whole matrix is really a single sorted list in disguise . Given a target value, return true if it exists in the matrix. Run a binary search over the imaginary flattened array, converting each middle position back into its (row, column) coordinates to read the actual value.

Constraints

  • m == matrix.length
  • n == matrixi.length
  • 1 ≤ m, n ≤ 100
  • -104 ≤ matrixi[j], target ≤ 104

Example

Inputmatrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Outputtrue

Explanation Treating the matrix as the flattened sorted array [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60], binary search lands on 3 at flattened position 1, which is (row 0, column 1).

2. Know the words first

In plain terms

Single sorted list in disguise
If you read the matrix row by row, left to right, top to bottom, the values come out in fully sorted order — so it behaves exactly like one long sorted array.
3. Visualize the solution

Binary search the matrix as one flattened sorted array

Binary search the matrix as one flattened sorted array
Statussearch

low=0, high=11: mid=5 → row=1, col=1 → matrix[1][1]=11. 11 > 3, so search the lower half: high=4.

What happens in this step

low = 0, high = 11
mid = 5 → row = 1, col = 1 → value = 11
11 > 3 → high = mid - 1 = 4
Step 1 of 4

Steps to visualize

  1. Treat the matrix as a single sorted array of length rows x columns, with low and high spanning the whole range.
  2. Compute the middle flattened position, then convert it into its actual row and column to read the value there.
  3. If that value matches the target, it has been found.
  4. If it is smaller than the target, search the upper half; if it is larger, search the lower half — exactly like ordinary binary search.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Binary search the matrix as one flattened sorted array
Statussearch

low=0, high=11: mid=5 → row=1, col=1 → matrix[1][1]=11. 11 > 3, so search the lower half: high=4.

What happens in this step

low = 0, high = 11
mid = 5 → row = 1, col = 1 → value = 11
11 > 3 → high = mid - 1 = 4
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function searchMatrix(matrix, target) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let low = 0;
  let high = rows * cols - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const row = Math.floor(mid / cols);
    const col = mid % cols;
    const value = matrix[row][col];

    if (value === target) {
      return true;
    } else if (value < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return false;
}
Time
O(log(m * n))
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3trueexample from the docstring
matrix = [[5]], target = 5truesmallest valid input where the single cell is the target
matrix = [[5]], target = 3falsesmallest valid input where the single cell is not the target
matrix = [[1, 3, 5], [7, 9, 11]], target = 0falsea target smaller than every value in the matrix
matrix = [[1, 3, 5], [7, 9, 11]], target = 100falsea target larger than every value in the matrix
matrix = [[1, 3, 5], [7, 9, 11]], target = 11truethe target sits in the very last cell of the matrix

Keep reading