A catalog service stores SKU prices in a grid: each row is a price band, sorted left to right, and the first SKU of the next band is more expensive than the last of the previous. Lookups walked every cell. A few hundred SKUs returned instantly. After the marketplace ingest, two million prices across a few thousand rows were still scanning when the request timed out.

Search a 2D Matrix asks you to probe one virtual 1D index. An array already gives a[i] for free. A nested scan uses that and still pays O(m n). The extra fact — next row starts after the previous row ends — is the license to flatten, not decoration.

This is an interview writeup, not a procedure lecture. The binary search post owns the invariant and mid overflow. The membership writeup is the 1D case: inclusive lo / hi on a sorted slice. Here the slice is matrix[r][c] with index = r * n + c. Same discard. Different address.

The problem

Given an m × n int[][] matrix and an int target, return whether target appears. Every row is sorted ascending. The first value of row i + 1 is strictly greater than the last value of row i. Typical interviews want O(log(m n)) time.

matrix =
  4  8  11 15
 19 22 26 29
 33 37 41 48

target = 26  →  true
target = 20  →  false
target = 4   →  true

Note: If only each row is sorted, and the next row can start below the previous row’s last cell, flattening is a lie. That is a different matrix. Confirm the global order before you treat the grid as one array.

Nested scan is the honest brute force

Every cell is compared once. Correct. Linear in the number of cells.

boolean searchScan(int[][] matrix, int target) {
    for (int[] row : matrix) {
        for (int v : row) {
            if (v == target) {
                return true;
            }
        }
    }
    return false;
}

A per-row binary search is the tempting middle: O(m log n). Correct, and still one binary search start per row on a sequence that was already globally ordered. At a few thousand rows you paid m searches for a question one flattened window answers in a handful of probes.

Flatten the index: one search on m * n slots

Keep inclusive bounds on the virtual length: lo = 0, hi = m * n - 1. Mid is lo + (hi - lo) / 2. The cell at virtual index mid is matrix[r][c] with r = mid / n, c = mid % n.

  • If that value equals target, return true.
  • If it is less, everything at or left of mid is too small: lo = mid + 1.
  • If it is greater, everything at or right of mid is too large: hi = mid - 1.

lo > hi means the invariant has nothing left. Return false.

m=3 n=4  virtual = [4, 8, 11, 15, 19, 22, 26, 29, 33, 37, 41, 48]
target = 26

lo=0 hi=11 mid=5  matrix[1][1]=22  22<26  → lo=6
lo=6 hi=11 mid=8  matrix[2][0]=33  33>26  → hi=7
lo=6 hi=7  mid=6  matrix[1][2]=26  hit, true

The Java is that loop:

boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    int lo = 0;
    int hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int r = mid / n;
        int c = mid % n;
        int v = matrix[r][c];
        if (v == target) {
            return true;
        }
        if (v < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return false;
}

Time is O(log(m n)) — each comparison throws away half of the virtual range. Space is O(1) — two indices, no copy of the grid. The membership loop and mid overflow already live on the algorithms post; do not re-lecture them unless they ask.

Note: Decode mid as r = mid / n, c = mid % n. Empty input is m == 0 or n == 0; matrix[0].length throws and hi would be -1. The prompt usually promises a non-empty grid; at the board, ask.

What interviewers usually poke next

  • Rows sorted, columns sorted, no global flatten. Search a 2D Matrix II. Start at a corner and drop a row or a column. Flattening that grid is wrong because row i + 1 can start below row i’s last cell.
  • Return the coordinates. Same loop; decode mid into (mid / n, mid % n) instead of a boolean.
  • Per-row search. Legal if the global-order fact is missing. Name the extra m factor so they know you did not miss it.
  • Empty / null. Production rejects. At the board, ask before you divide by n.

You are done with this problem when you can say, out loud, why the nested scan is correct, why the row-start invariant licenses one virtual index, and why a per-row search starts too many times.