Search a 2D Matrix II
Medium Staircase search
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rows are sorted left to right and columns top to bottom (but rows don't continue each other). Decide if target is present.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rows and columns are each sorted; is the target there?
Why this works: start top-right. Going left decreases, going down increases, so each step throws away a whole row or column.
Example: target 5, top-right 15
15 > 5 → left 11 → left 7 → left 44 < 5 → down 5 ✓
✦Hints open one at a time
↗Approach
At (r, c): if the value is bigger than target, the whole column below is bigger too, so move left. If smaller, the whole row to the left is smaller, so move down. Each step removes a row or a column.
</>Solution (Java)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
int v = matrix[r][c];
if (v == target) return true;
if (v > target) c--; // drop this column
else r++; // drop this row
}
return false;
}
}!Common mistake
Starting at the top-left, where both directions increase and you can't decide where to go.
- Time: O(m + n).
- Space: O(1).