Search a 2D Matrix

Search a 2D Matrix

What is this problem about?

The Search a 2D Matrix interview question gives you an m×n matrix where each row is sorted in ascending order, and the first element of each row is greater than the last element of the previous row. Given a target value, determine whether it exists in the matrix. This "sorted matrix" structure allows you to treat the entire matrix as a sorted 1D array and apply binary search.

Why is this asked in interviews?

This problem is asked at Apple, Cisco, Uber, Goldman Sachs, Microsoft, Meta, Amazon, TikTok, Oracle, Google, Bloomberg, and Adobe because it is the canonical demonstration of adapting binary search to a 2D structure. The matrix's property makes it equivalent to a sorted 1D array, enabling O(log(m×n)) binary search — far better than O(m×n) linear scan. It tests spatial reasoning and index arithmetic.

Algorithmic pattern used

The pattern is binary search on the flattened matrix. Treat the matrix as a 1D array of length m * n. Binary search on indices [0, m*n - 1]. For a mid index k: the corresponding row is k // n and column is k % n. Compare matrix[k//n][k%n] with target. Adjust left/right pointers accordingly. This gives O(log(m×n)) time.

Alternative: row binary search to find the correct row, then column binary search within that row — also O(log m + log n) = O(log(m×n)).

Example explanation

Matrix:

[1,  3,  5,  7]
[10, 11, 16, 20]
[23, 30, 34, 60]

Target = 16. m=3, n=4. Search range [0, 11].

• mid = 5 → matrix[5//4][5%4] = matrix[1][1] = 11. 11 < 16 → search right.
• left=6. mid=8 → matrix[8//4][8%4] = matrix[2][0] = 23. 23 > 16 → search left.
• left=6, right=7. mid=6 → matrix[1][2] = 16. Found! Return true.

Common mistakes candidates make

• Confusing this with the "Search a 2D Matrix II" problem (where rows are sorted but the first element is NOT greater than the last of the previous row) — different algorithm needed.
• Incorrect 2D index conversion: row = k // n (divide by number of COLUMNS), column = k % n.
• Off-by-one in the binary search boundaries: right = m * n - 1.
• Not handling empty matrices — check for m == 0 or n == 0 first.

Interview preparation tip

For the Search a 2D Matrix coding problem, the binary search and matrix interview pattern is the key skill. The index formula (k // n, k % n) is the heart of the solution — practice it until it's automatic. Interviewers at Grab and Coupang often ask the follow-up "Search a 2D Matrix II" (only row-sorted, not globally sorted) — know that it requires the "staircase search" starting from the top-right corner instead of binary search. Practice both variants.