Search a 2D Matrix II
Medium · Binary Search · Explanation and code example
Staircase Search
How it works
At the top-right corner, every value to the left is smaller and every value below is larger. A comparison therefore eliminates one whole column or row. Move left when the current value is too large and down when it is too small.
Steps
- Start at row zero and the last column.
- Compare the current cell with the target.
- Move left or down until the target is found or the matrix bounds are crossed.
Complexity
- Time: O(rows + columns).
- Space: O(1).
Things to watch for
- Rows and columns are individually sorted; flattening the matrix is not generally sorted.
- A single row or column still works.
- The problem guarantees a nonempty matrix.
Python code example
class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
r = 0
c = len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
if matrix[r][c] == target:
return True
if target < matrix[r][c]:
c -= 1
else:
r += 1
return False
C++ code example
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int r = 0;
int c = matrix[0].size() - 1;
while (r < matrix.size() && c >= 0) {
if (matrix[r][c] == target)
return true;
if (matrix[r][c] > target)
--c;
else
++r;
}
return false;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.