Search a 2D Matrix

Difficulty: Medium

You're given a grid of numbers with two useful properties: every row is sorted left to right, and the first number in each row is bigger than the last number in the row directly above it.

That second property means that if you read the grid row by row, left to right and top to bottom, the numbers come out in one long, uninterrupted sorted sequence — the grid is really just a single sorted list arranged into rows.

Given the grid and a target number, decide whether the target appears anywhere in it.

Examples

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

3 appears in the first row.

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

13 falls between 11 and 16 in the second row, so it doesn't appear anywhere in the grid.

Input: matrix = [[1]], target = 1
Output: true

A 1x1 grid whose only value is the target.

Constraints

  • m == matrix.length

  • n == matrix[i].length

  • 1 <= m, n <= 100

  • -10^4 <= matrix[i][j], target <= 10^4

Approach

A straightforward approach is to check every cell directly, or to first narrow down which row could contain the target and then search within that row. Both work, but neither uses the full picture: the whole grid, read row by row, is one sorted sequence of m * n numbers.

The faster approach treats the grid as if it were a single flattened sorted array, without ever actually building one. Any index i from 0 to m * n - 1 maps to row Math.floor(i / n) and column i % n. With that mapping in hand, you can binary search over the range [0, m*n - 1] exactly like a normal sorted array, translating each candidate index into a row/column lookup as you go.

Solutions

Brute Force — Scan Every Cell

Check every cell in the grid one at a time until the target turns up. Simple, but ignores that the rows are sorted and chained together.

function searchMatrix(matrix, target) {
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < matrix[r].length; c++) {
      if (matrix[r][c] === target) return true;
    }
  }
  return false;
}

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

Optimal — Binary Search Over a Flattened Index

Binary search over the range [0, m*n - 1] as though the grid were one long sorted array, converting each candidate index back into a row and column to look up its value.

function searchMatrix(matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const value = matrix[Math.floor(mid / n)][mid % n];

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

  return false;
}

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