Search a 2D Matrix II

Search a 2D Matrix II

What is this problem about?

The Search a 2D Matrix II interview question gives you an m×n integer matrix where each row is sorted left to right and each column is sorted top to bottom (but rows are NOT globally sorted relative to each other). Given a target integer, determine whether it exists in the matrix. Unlike its predecessor, you cannot treat this as a 1D binary search — the structure requires a different O(m+n) staircase algorithm.

Why is this asked in interviews?

This problem is asked at Apple, Uber, Goldman Sachs, Microsoft, Meta, Amazon, TikTok, Google, Bloomberg, and Adobe because it demonstrates a non-obvious O(m+n) search strategy. The staircase search — starting from a corner and eliminating a row or column at each step — is an elegant application of matrix structure reasoning. It tests mathematical insight over brute-force enumeration, a distinction critical in product engineering at scale.

Algorithmic pattern used

The pattern is the staircase search (top-right corner traversal). Start at the top-right cell (0, n-1). At each step: if the current value equals the target, return true. If the current value is greater than the target, move left (eliminate the current column — all values below are larger). If the current value is less than the target, move down (eliminate the current row — all values to the left are smaller). Continue until out of bounds.

Example explanation

Matrix:

[ 1,  4,  7, 11]
[ 2,  5,  8, 12]
[ 3,  6,  9, 16]
[10, 13, 14, 17]

Target = 9. Start at (0, 3) = 11.

• 11 > 9 → move left. (0,2) = 7.
• 7 < 9 → move down. (1,2) = 8.
• 8 < 9 → move down. (2,2) = 9. Found! Return true.

Target = 15:

• (0,3)=11 < 15 → down. (1,3)=12 < 15 → down. (2,3)=16 > 15 → left. (2,2)=9 < 15 → down. (3,2)=14 < 15 → down. Out of bounds → false.

Common mistakes candidates make

• Starting from the top-left corner — you cannot eliminate a row or column from there since both right and down have larger values.
• Confusing this with Search a 2D Matrix I and applying binary search on the flattened array — invalid since rows are not globally ordered.
• Starting from the bottom-left corner (also valid) but implementing the direction logic incorrectly.
• Using O(m log n) row-by-row binary search when O(m+n) staircase is expected.

Interview preparation tip

For the Search a 2D Matrix II coding problem, the matrix and divide-and-conquer interview pattern is elegant via the staircase approach. Always start from the top-right or bottom-left corner — these are the only corners where exactly one direction increases and one decreases. Interviewers at Coupang and Zomato often test both matrix variants back-to-back — be ready to articulate why different algorithms are needed for each based on the matrix structure guarantees.