Search a 2D Matrix

You are given an m by n grid of integers matrix with two ordering guarantees:

• every row is sorted in strictly increasing order from left to right, and
• the first value of each row is larger than the last value of the row above it.

Together these mean that reading the grid row by row gives one strictly increasing sequence.

Return true if target appears somewhere in the grid and false otherwise. Aim for a running time of O(log(m · n)).

Example 1

Example 2

Example 3

Constraints

• m == matrix.length, n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104
• Each row is strictly increasing, and each row starts above the previous row's last value.

Pattern Path · Binary Search · problem 63 of 169

Start simple

Check every cell: O(m·n) time. A row-then-column walk is O(m + n), still not logarithmic.

The key idea

The two guarantees say that the row-by-row reading of the grid is a single sorted list of length m · n. Searching a sorted list is binary search, so the only question is how to address that list without copying it.

Position k of the virtual list is in row k // n (each full row holds n values) and column k % n. Run a standard binary search on lo = 0, hi = m·n - 1: read the middle value through that mapping, return true if it equals the target, otherwise discard the half that cannot contain it.

Each step halves the remaining range, so there are at most log2(m·n) steps, and no extra memory is used.

An equally fast alternative is two binary searches: first find the last row whose first value is at most the target, then search inside that row. It costs O(log m + log n), which is the same thing.

Complexity

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

Python

class Solution:
    def searchMatrix(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            value = matrix[mid // n][mid % n]   # position mid in the row-by-row reading
            if value == target:
                return True
            if value < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

JavaScript

var searchMatrix = function(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m * n - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const value = matrix[Math.floor(mid / n)][mid % n];  // position mid in the row-by-row reading
    if (value === target) return true;
    if (value < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
};

What the interviewer is checking

The interviewer wants to see you recognise a familiar structure (a sorted array) hidden behind a 2D layout and implement binary search without boundary bugs.

Mistakes to avoid

• Using k // m or k % m instead of dividing by the number of columns n.
• Off-by-one loop bounds (hi = m·n instead of m·n - 1, or lo < hi that skips the last candidate).
• Searching only one row chosen by comparing with the last column, then forgetting the target can be below the first row.
• Building a flattened copy, which costs O(m·n) and defeats the purpose.

Follow-ups to expect

• What if only rows and columns are sorted separately? (Staircase walk from a corner, O(m+n).)
• How would you count occurrences with duplicates allowed? (Lower and upper bound searches.)
• What if the grid is too large for memory? (Same index mapping over paged storage.)

In real software

Paged or chunked storage, such as sorted blocks in a database index or a log split into files, is searched by mapping a global position to (chunk, offset) exactly like this.

Practice next