MediumNeetCode150ArrayBinary SearchMatrixDivide and Conquer
Search a 2D Matrix II
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.
Examples
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 exists in the matrix.
Constraints
- •
m == matrix.length - •
n == matrix[i].length - •
1 <= m, n <= 300 - •
-10^9 <= matrix[i][j], target <= 10^9 - •
All the integers in each row are sorted in ascending order.
Approaches
Search every element.
CodeT: O(m*n) | S: O(1)
Start from top-right corner. If current > target, move left. If current < target, move down.
CodeT: O(m+n) | S: O(1)
def searchMatrix(matrix, target):
if not matrix or not matrix[0]: return False
r, c = 0, len(matrix[0])-1
while r < len(matrix) and c >= 0:
if matrix[r][c] == target: return True
elif matrix[r][c] > target: c -= 1
else: r += 1
return FalseFor each row, binary search for target. Or use divide and conquer.
CodeT: O(m log n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(m*n) | O(1) | Search every element. |
| Staircase Search | O(m+n) | O(1) | Start from top-right corner. If current > target, move left. If current < target, move down. |
| Binary Search on Rows | O(m log n) | O(1) | For each row, binary search for target. Or use divide and conquer. |
Brute Force
T: O(m*n)S: O(1)
Search every element.
Staircase Search
T: O(m+n)S: O(1)
Start from top-right corner. If current > target, move left. If current < target, move down.
Binary Search on Rows
T: O(m log n)S: O(1)
For each row, binary search for target. Or use divide and conquer.
Common Mistakes
Not handling empty matrix
Wrong direction in staircase search
Off-by-one in boundary checks