Search a 2D Matrix II
Search a matrix whose rows and columns are each sorted: start at the top-right corner and drop a whole row or column with every comparison.
Problem Understanding
Search a 2D Matrix II: an m × n matrix has every row sorted left to right and every column sorted top to bottom. Return true if target is in it.
Example: in the 5 × 5 matrix below, target = 5 returns true and target = 20 returns false.
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
The Intuition: A Corner That Points Two Ways
Binary search on the whole grid fails here: row 3 starts at 10 while row 2 ends at 22, so the matrix is not one sorted list, unlike Search a 2D Matrix.
Pick the cell where the two orders disagree: the top-right corner.
- Everything to its left is smaller (same row).
- Everything below it is bigger (same column).
- So if it is too big, the whole column can go; if it is too small, the whole row can go.
Each comparison removes a row or a column, and the cell you land on is again the top-right corner of what is left. At most m + n moves end the search. This is the same idea as binary search: throw away the part that cannot hold the answer, just one line at a time instead of half.
Interactive Walkthrough
The live cell starts at the top-right corner; rows above it and columns to its right are struck out as they are ruled out. Try Bottom-left for the longest path, or Example 2 to watch the walk leave the grid.
Dry Run Table
Input: the matrix above, target = 5
| (r, c) | Cell | Compare | Move |
|---|---|---|---|
| (0, 4) | 15 | 15 > 5 | left |
| (0, 3) | 11 | 11 > 5 | left |
| (0, 2) | 7 | 7 > 5 | left |
| (0, 1) | 4 | 4 < 5 | down |
| (1, 1) | 5 | 5 = 5 | found |
Answer: true after 4 moves.
The Solution Template
Two indexes and one loop. No extra memory.
Search a 2D Matrix II Code
1var searchMatrix = function(matrix, target) {2 let r = 0, c = matrix[0].length - 1;3 while (r < matrix.length && c >= 0) {4 if (matrix[r][c] === target) return true;5 if (matrix[r][c] > target) c--;6 else r++;7 }8 return false;9};
Edge Cases & Common Mistakes
- Starting at the top-left: both neighbours are bigger, so a too-small cell gives no direction. Use the top-right or bottom-left corner.
- Flattening into one array: that only works for LeetCode 74, where each row starts after the previous one ends.
- Loop bounds: check
r < mandc >= 0before readingmatrix[r][c]. - Binary search on every row: correct, but O(m log n), which is slower than O(m + n) when the matrix is square.
- Duplicates: fine; the walk stops at the first copy it meets.
Summary
Start at the top-right corner. Too big: move left and drop the column. Too small: move down and drop the row. Each move removes a whole line, so the search ends in O(m + n) time with O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet