You are given an m x n grid of integers matrix with a double-sorted structure:
Given an integer target, return true if target appears anywhere in the grid, and false otherwise.
Note what the guarantee does not say: the grid is not one long sorted list — the last value of a row may be larger than the first value of the next row. An efficient search must exploit both sort orders instead of touching every cell.
target, its entire column is bigger — step left. If smaller, its entire row is smaller — step down. You finish in at most m + n steps.15 while row 1 starts at 2 in the example). Without that chain there is no single sorted order to binary search. That trick only works on a fully sorted matrix.target you have no idea which way to go. Only the top-right and bottom-left corners give a decisive move for both outcomes.target.O(m + n).O((m + n) log(range)). That is Kth Smallest Element in a Sorted Matrix.Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true 5 sits at row 1, column 1 — it is in the grid.
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false 20 falls between values that exist (19 and 21) but never appears itself.
- m == matrix.length - n == matrix[i].length - 1 <= n, m <= 300 - -10^9 <= matrix[i][j] <= 10^9 - All integers in each row are sorted in ascending order, left to right - All integers in each column are sorted in ascending order, top to bottom - -10^9 <= target <= 10^9
A grid sorted along both axes looks like one big sorted list — it is not. The arc of this tutorial: see exactly why one global binary search breaks, then discover the one corner of the grid where every single comparison eliminates an entire row or column.
(row, col) pair and knowing which index moves you down vs right.In plain English: you get a grid where sliding right along any row makes values grow, and sliding down any column makes values grow. Decide whether target is somewhere in it.
Formally: given an m x n matrix with ascending rows and ascending columns, return true iff some cell matrix[i][j] == target.
Worked example — target = 5, then target = 20
1 4 7 11 15 start at top-right (15) 2 5 8 12 19 15 > 5 → left … 11, 7 → left 3 6 9 16 22 4 < 5 → down 10 13 14 17 24 5 == 5 → true ✓ 18 21 23 26 30 target = 20: 15 → 19 → 22 → 16 → 17 → 26 → 23 → 21 → 18 → off the grid → false
Asking two or three sharp questions before coding shows you design against guarantees, not assumptions.
“Is every row sorted left to right and every column sorted top to bottom?”
This double guarantee is the entire problem. With only rows sorted, the staircase walk is invalid and you fall back to binary searching each row.
“Can values repeat inside the grid?”
Yes — double-sorted does not mean distinct. The staircase only ever asks bigger, smaller, or equal, so duplicates cost nothing.
“What if target is below the smallest or above the largest value?”
The top-left cell is the global minimum and the bottom-right the global maximum — an out-of-range target can be rejected instantly.
“What about a single row or a single column?”
The staircase degenerates into a plain linear scan and stays correct — a good sanity test for your boundary conditions.
“How large can the grid get?”
Up to 300 x 300 = 90,000 cells. A full scan passes the judge, but the interviewer set up two sort orders and expects you to use them.
Before I code, I want to confirm the guarantee: every row ascends left to right and every column ascends top to bottom, correct?
Values may repeat, and I only return whether the target exists, not where.
Since the top-left cell is the global minimum and the bottom-right the global maximum, I can reject out-of-range targets immediately.
In a fully sorted matrix, each row starts after the previous row ends, so you can pretend it is one array and binary search it. Here that chain is broken: row 0 ends at 15, yet row 1 begins at 2. Ranges overlap, so a single global binary search has no valid ordering to work with.
The top-right cell is the largest in its row and the smallest in its column — the two sort orders pull in opposite directions there, so every comparison is decisive.
smaller ← … ← [15] 15 > target → its whole column is > target → step left
↓ 15 < target → its whole row is < target → step down
biggerContrast with the top-left corner: moving right and moving down both increase the value, so a comparison there tells you nothing about which way to go.
Each comparison either deletes one column (step left) or one row (step down). You can do that at most m + n - 1 times before walking off the grid — so the walk is O(m + n), at most 599 steps for the largest allowed grid.
| Brute force | Row binary search | Staircase | |
|---|---|---|---|
| Time | O(m · n) | O(m log n) | O(m + n) |
| Space | O(1) | O(1) | O(1) |
Full, runnable implementations of all three live in the Approaches selector below.
Key takeaway
When data is sorted along two axes, stand at a corner where the orders conflict — the cell that is the max of its row and the min of its column — and every comparison discards an entire line of the grid. This saddleback walk turns a 90,000-cell search into at most 599 steps.
row ← 0, col ← n − 1
while row < m and col ≥ 0:
if matrix[row][col] == target: return true
if matrix[row][col] > target: col ← col − 1 (whole column too big)
else: row ← row + 1 (whole row too small)
return false