220. Search a 2D Matrix II
You are given an m × n integer matrix with a two-way ordering: every row is sorted ascending left to right, and every column is sorted ascending top to bottom. Given an integer target, return true if it appears anywhere in the matrix and false otherwise.
Note what is not promised: unlike a matrix whose rows continue each other, here the last value of one row can be larger than the first value of the next. Flattening it does not give a sorted list, so a single global binary search is off the table.
The two orderings still leak a lot of information from a single comparison — enough to discard a full row or column at a time. Aim for O(m + n).
Example 1:
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
Explanation: 5 sits at row 1, column 1, so the answer is true.
Example 2:
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
Explanation: 20 appears nowhere in the matrix, so the answer is false.
Constraints:
- 1 ≤ m, n ≤ 300
- -10⁹ ≤ matrix[i][j], target ≤ 10⁹
- Each row is sorted in ascending order left to right.
- Each column is sorted in ascending order top to bottom.
Hints:
Stand on the top-right value. Everything to its left in that row is smaller; everything below it in that column is larger. What does comparing it against the target let you eliminate?
If the corner value is greater than the target, that whole column can go; if it is smaller, that whole row can go. Each comparison permanently discards a row or a column, so the walk ends within m + n steps.
Middle ground if you don't spot the staircase: binary-search each row independently — O(m log n), still a big step up from scanning.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
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
Expected output: true