Search a 2D Matrix II
Description
You are given an m x n integer matrix matrix and an integer target. Your task is to determine whether target exists anywhere in the matrix.
The matrix has two special sorting properties:
- Every row is sorted in ascending order from left to right.
- Every column is sorted in ascending order from top to bottom.
Return true if the target value is found in the matrix, or false otherwise.
Important distinction: Unlike "Search a 2D Matrix" (LeetCode 74), the first element of a row is NOT guaranteed to be greater than the last element of the previous row. This means you cannot treat the matrix as a single sorted array. For example, the value 3 (row 2, col 0) is less than 15 (row 0, col 4) even though it appears in a later row.
Examples
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: The value 5 exists in the matrix at position row 1, column 1. We can verify: matrix[1][1] = 5 = target.
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: The value 20 does not appear anywhere in the matrix. The closest values are 19 (row 1, col 4) and 21 (row 4, col 1), but neither equals 20.
Example 3
Input: matrix = [[-5]], target = -5
Output: true
Explanation: The matrix has a single element -5, which equals the target.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 ≤ n, m ≤ 300
- -10^9 ≤ matrix[i][j] ≤ 10^9
- All integers in each row are sorted in ascending order
- All integers in each column are sorted in ascending order
- -10^9 ≤ target ≤ 10^9
Editorial
Brute Force
Intuition
The most straightforward approach is to ignore the sorting properties entirely and check every single cell in the matrix. We scan row by row, column by column, comparing each element to the target. If we find a match, return true. If we exhaust the entire matrix without finding it, return false.
Think of it like searching for a specific book in a library by checking every shelf and every book one by one, without using any catalog or organizational system.
Step-by-Step Explanation
Let's trace through with a smaller 3×4 matrix, target = 14:
[ 1, 3, 5, 7]
[ 2, 4, 6, 8]
[10, 11, 12, 14]
Step 1: Check row 0: matrix[0][0]=1 ≠ 14, matrix[0][1]=3 ≠ 14, matrix[0][2]=5 ≠ 14, matrix[0][3]=7 ≠ 14. Not in row 0.
Step 2: Check row 1: matrix[1][0]=2 ≠ 14, matrix[1][1]=4 ≠ 14, matrix[1][2]=6 ≠ 14, matrix[1][3]=8 ≠ 14. Not in row 1.
Step 3: Check row 2: matrix[2][0]=10 ≠ 14, matrix[2][1]=11 ≠ 14, matrix[2][2]=12 ≠ 14, matrix[2][3]=14 == 14. Found it!
Step 4: Return true.
Brute Force — Scanning Every Cell — Watch how brute force examines every cell in row-major order until it finds the target, ignoring the matrix's sorted properties entirely.
Algorithm
- Iterate through each row i from 0 to m-1:
a. For each column j from 0 to n-1:- If matrix[i][j] == target, return true.
- If no match found after scanning all cells, return false.
Code
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
};class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] == target:
return True
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(m × n)
We visit every cell in the matrix exactly once in the worst case. For a 300×300 matrix, that's up to 90,000 comparisons.
Space Complexity: O(1)
We use only a few index variables. No additional data structures are needed.
Why This Approach Is Not Efficient
The brute force approach treats the matrix as an unstructured collection and completely ignores that every row and every column is individually sorted. With m, n up to 300, the O(m × n) = O(90,000) approach works within time limits, but it wastes the sorted structure that the problem explicitly provides.
The key observation is: each row is a sorted array. Instead of scanning each row linearly (O(n) per row), we can use binary search on each row (O(log n) per row). This reduces the total time from O(m × n) to O(m × log n) — a significant improvement when n is large.
For a 300×300 matrix: brute force does 90,000 comparisons, while binary search per row does only 300 × log₂(300) ≈ 300 × 8.2 ≈ 2,460 comparisons — roughly 37× faster.
Better Approach - Binary Search Per Row
Intuition
Since each row is individually sorted in ascending order, we can treat each row as a separate sorted array and apply binary search to it. For each row, we perform a standard binary search to check if the target exists in that row.
This is like going to a library where books on each shelf are sorted alphabetically. Instead of checking every book on every shelf, you use alphabetical order to quickly find (or rule out) the book on each shelf.
We iterate through all m rows, performing a binary search on each one. If any row contains the target, we return true immediately. If none of the rows contain it, we return false.
Step-by-Step Explanation
Let's trace through the 5×5 matrix, target = 5:
[ 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]
Step 1: Binary search row 0: [1, 4, 7, 11, 15]
- low=0, high=4, mid=2, matrix[0][2]=7. 7 > 5 → high = 1.
- low=0, high=1, mid=0, matrix[0][0]=1. 1 < 5 → low = 1.
- low=1, high=1, mid=1, matrix[0][1]=4. 4 < 5 → low = 2.
- low > high. Target 5 not in row 0.
Step 2: Binary search row 1: [2, 5, 8, 12, 19]
- low=0, high=4, mid=2, matrix[1][2]=8. 8 > 5 → high = 1.
- low=0, high=1, mid=0, matrix[1][0]=2. 2 < 5 → low = 1.
- low=1, high=1, mid=1, matrix[1][1]=5. 5 == 5 → FOUND!
Step 3: Return true. Found target 5 at matrix[1][1] after searching only 2 rows.
Binary Search Per Row — Finding Target 5 — Watch how we perform binary search independently on each row, narrowing the search within each row using the sorted property.
Algorithm
- For each row i from 0 to m-1:
a. Perform binary search on row i for target:- Set low = 0, high = n-1.
- While low ≤ high:
- Compute mid = low + (high - low) / 2.
- If matrix[i][mid] == target, return true.
- If matrix[i][mid] < target, set low = mid + 1.
- If matrix[i][mid] > target, set high = mid - 1.
- If no row contains the target, return false.
Code
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m; i++) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (matrix[i][mid] == target) {
return true;
} else if (matrix[i][mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return false;
}
};class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
for i in range(m):
low, high = 0, n - 1
while low <= high:
mid = low + (high - low) // 2
if matrix[i][mid] == target:
return True
elif matrix[i][mid] < target:
low = mid + 1
else:
high = mid - 1
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; i++) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (matrix[i][mid] == target) {
return true;
} else if (matrix[i][mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(m × log n)
We iterate through all m rows, and for each row we perform a binary search that takes O(log n). Total: m × log n. For a 300×300 matrix, this is about 300 × 8.2 ≈ 2,460 operations.
Space Complexity: O(1)
We only use a few integer variables (low, high, mid) for the binary search. No additional data structures are created.
Why This Approach Is Not Efficient
Binary search per row uses only the row-wise sorting property. It completely ignores the column-wise sorting. This means we always search all m rows, even when many rows can be immediately ruled out.
For instance, if the target is 5 and a row starts with 10, we know 5 cannot be in that row (since the row is sorted and starts with 10, all elements are ≥ 10). Similarly, if a row ends with 3, the target 5 cannot be there either. But binary search per row still searches every row without exploiting these cross-row relationships.
The crucial insight is: if we stand at the top-right corner of the matrix, the value there acts as a decision point. It is the largest in its row (sorted left-to-right) and the smallest in its column (sorted top-to-bottom). This means:
- If the value > target → we can eliminate the entire column (everything below is even larger).
- If the value < target → we can eliminate the entire row (everything to the left is even smaller).
This eliminates either a full row or a full column at each step, giving us O(m + n) — a significant improvement over O(m × log n).
Optimal Approach - Staircase Search
Intuition
The key insight comes from examining the top-right corner (or equivalently, the bottom-left corner) of the matrix. These corners are special because they sit at the intersection of a sorted row and a sorted column, giving us a natural decision point.
Consider the top-right corner value matrix[0][n-1]:
- It is the largest value in its row (row 0), since each row is sorted ascending left-to-right.
- It is the smallest value in its column (column n-1), since each column is sorted ascending top-to-bottom.
This creates a "crossroads" where:
- If the current value equals the target → we found it.
- If the current value is greater than the target → the entire current column is too large (all values below are even greater). Move left to try a smaller column.
- If the current value is less than the target → the entire current row is too small (all values to the left are even smaller). Move down to try a larger row.
Each comparison eliminates either one row or one column from consideration. Since there are m rows and n columns, we make at most m + n comparisons. The path we trace looks like a staircase descending from the top-right corner — hence the name "Staircase Search."
This approach also works starting from the bottom-left corner with mirrored logic. However, starting from the top-left or bottom-right does NOT work because both directions (right and down from top-left, or left and up from bottom-right) increase, providing no way to decide which direction to move.
Step-by-Step Explanation
Let's trace the 5×5 matrix, target = 5:
[ 1, 4, 7, 11, 15] ← start here (top-right: 15)
[ 2, 5, 8, 12, 19]
[ 3, 6, 9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]
Step 1: Start at top-right: row=0, col=4, value=15.
- Is 15 == 5? No. Is 15 > 5? Yes → the entire column 4 is too large. Move left: col = 3.
Step 2: row=0, col=3, value=11.
- Is 11 == 5? No. Is 11 > 5? Yes → column 3 is too large. Move left: col = 2.
Step 3: row=0, col=2, value=7.
- Is 7 == 5? No. Is 7 > 5? Yes → column 2 is too large. Move left: col = 1.
Step 4: row=0, col=1, value=4.
- Is 4 == 5? No. Is 4 < 5? Yes → row 0 is too small (everything left of here is even smaller). Move down: row = 1.
Step 5: row=1, col=1, value=5.
- Is 5 == 5? YES! Found the target.
Step 6: Return true. Only 5 comparisons needed!
Now let's trace target = 20 (not present):
Step 1: row=0, col=4, value=15. 15 < 20 → move down: row = 1.
Step 2: row=1, col=4, value=19. 19 < 20 → move down: row = 2.
Step 3: row=2, col=4, value=22. 22 > 20 → move left: col = 3.
Step 4: row=3, col=3, value=17. 17 < 20 → move down: row = 4. (Note: skip row 2 col 3 = 16)
Wait, let me retrace more carefully:
Step 3: row=2, col=4, value=22. 22 > 20 → move left: col = 3.
Step 4: row=2, col=3, value=16. 16 < 20 → move down: row = 3.
Step 5: row=3, col=3, value=17. 17 < 20 → move down: row = 4.
Step 6: row=4, col=3, value=26. 26 > 20 → move left: col = 2.
Step 7: row=4, col=2, value=23. 23 > 20 → move left: col = 1.
Step 8: row=4, col=1, value=21. 21 > 20 → move left: col = 0.
Step 9: row=4, col=0, value=18. 18 < 20 → move down: row = 5.
Step 10: row=5 is out of bounds. Return false. Target 20 not found.
Staircase Search — Finding Target 5 from Top-Right — Starting from the top-right corner, each comparison eliminates either a full row or a full column. Watch the staircase path emerge as we narrow the search.
Now let's see the "not found" case: target = 20:
Staircase Search — Target 20 Not Found — When the target doesn't exist, the staircase path traverses from top-right toward bottom-left until the search goes out of bounds.
Algorithm
- Initialize row = 0 (top row) and col = n - 1 (rightmost column). This is the top-right corner.
- While row < m AND col ≥ 0:
a. If matrix[row][col] == target, return true.
b. If matrix[row][col] > target, move left: col = col - 1 (eliminate current column).
c. If matrix[row][col] < target, move down: row = row + 1 (eliminate current row). - If the loop ends without finding the target, return false.
Code
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
// Start from the top-right corner
int row = 0;
int col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
// Current value too large — eliminate this column
col--;
} else {
// Current value too small — eliminate this row
row++;
}
}
return false;
}
};class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
# Start from the top-right corner
row = 0
col = n - 1
while row < m and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
# Current value too large — eliminate this column
col -= 1
else:
# Current value too small — eliminate this row
row += 1
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
// Start from the top-right corner
int row = 0;
int col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
// Current value too large — eliminate this column
col--;
} else {
// Current value too small — eliminate this row
row++;
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(m + n)
At each step, we either move down (incrementing row) or move left (decrementing col). The row variable starts at 0 and can increase at most m times before going out of bounds. The col variable starts at n-1 and can decrease at most n times before going below 0. Therefore, the total number of steps is at most m + n. For a 300×300 matrix, that's at most 600 comparisons.
Space Complexity: O(1)
We use only two integer variables (row and col) to track our position. No additional data structures are needed.