Search a 2D Matrix
Problem
Given an m x n matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, return true if target is in the matrix or false otherwise.
- m == matrix.length
- n == matrix[i].length
- 1 ≤ m, n ≤ 100
- −10⁴ ≤ matrix[i][j], target ≤ 10⁴
- Each row is sorted in ascending order.
- The first integer of each row is greater than the last integer of the previous row.
Example
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3trueThe algorithm first performs a binary search over the rows to find the candidate row that could contain the target. For target = 3, it compares 3 with the last element of the middle row (row 1: 20). Since 3 < 20, it narrows the search to the top half. It then checks if 3 is greater than or equal to the first element of the candidate row. Once the candidate row is found (row 0), a second binary search is performed within that row. The target 3 is found at index 1, so the algorithm returns true.
Approach
Straightforward Solution
A brute-force approach would scan every element in the matrix, resulting in O(m*n) time complexity, which is inefficient for large matrices.
Core Observation
The matrix can be viewed as a sorted list of rows, each sorted internally, with the property that the first element of a row is greater than the last element of the previous row. This allows a two-level binary search: first to find the candidate row, then to find the target within that row.
Path to Optimal
The key recognition signals are 'sorted rows' and 'first integer of each row greater than last integer of previous row'. These indicate a Modified Binary Search because the matrix can be treated as a sorted sequence of rows, enabling binary search to find the candidate row, followed by a standard binary search within that row. This reduces the search space from O(m*n) to O(log m + log n).
Optimal Approach
Perform a binary search on the rows to find the row where the target could reside by comparing the target with the first and last elements of the middle row. Once the candidate row is identified, perform a binary search within that row to find the target. Return true if found, otherwise false.
Time
O(log m + log n)
The algorithm performs two binary searches: one over m rows and one over n columns. Each binary search takes O(log m) and O(log n) respectively, resulting in O(log m + log n) total time.
Space
O(1)
The algorithm uses only a fixed number of variables for indices and does not allocate additional data structures proportional to input size, resulting in constant auxiliary space.
Pattern Spotlight
Modified Binary Search (Two-Level Search in Sorted Matrix)
When a 2D matrix has sorted rows and each row's first element is greater than the previous row's last, treat the matrix as a sorted list of rows and apply binary search twice: first to locate the candidate row, then to locate the target within that row.
Solution
| 1 | class Solution:
|
| 2 | def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
|
| 3 | ROWS, COLS = len(matrix), len(matrix[0])
|
| 4 | top, bot = 0, ROWS - 1
|
| 5 |
|
| 6 | while top <= bot:
|
| 7 | row = (top + bot) // 2
|
| 8 | if target > matrix[row][-1]:
|
| 9 | top = row + 1
|
| 10 | elif target < matrix[row][0]:
|
| 11 | bot = row - 1
|
| 12 | else:
|
| 13 | break
|
| 14 |
|
| 15 | if not (top <= bot):
|
| 16 | return False
|
| 17 |
|
| 18 | row = (top + bot) // 2
|
| 19 | l, r = 0, COLS - 1
|
| 20 | while l <= r:
|
| 21 | m = (l + r) // 2
|
| 22 | if target > matrix[row][m]:
|
| 23 | l = m + 1
|
| 24 | elif target < matrix[row][m]:
|
| 25 | r = m - 1
|
| 26 | else:
|
| 27 | return True
|
| 28 |
|
| 29 | return False |
| 1 | class Solution { |
| 2 | public boolean searchMatrix(int[][] matrix, int target) { |
| 3 | int rows = matrix.length; |
| 4 | int cols = matrix[0].length; |
| 5 | int top = 0; |
| 6 | int bot = rows - 1; |
| 7 | |
| 8 | while (top <= bot) { |
| 9 | int row = top + (bot - top) / 2; |
| 10 | if (target > matrix[row][cols - 1]) { |
| 11 | top = row + 1; |
| 12 | } else if (target < matrix[row][0]) { |
| 13 | bot = row - 1; |
| 14 | } else { |
| 15 | break; |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | if (top > bot) { |
| 20 | return false; |
| 21 | } |
| 22 | |
| 23 | int row = top + (bot - top) / 2; |
| 24 | int l = 0; |
| 25 | int r = cols - 1; |
| 26 | while (l <= r) { |
| 27 | int m = l + (r - l) / 2; |
| 28 | if (target > matrix[row][m]) { |
| 29 | l = m + 1; |
| 30 | } else if (target < matrix[row][m]) { |
| 31 | r = m - 1; |
| 32 | } else { |
| 33 | return true; |
| 34 | } |
| 35 | } |
| 36 | |
| 37 | return false; |
| 38 | } |
| 39 | } |
Step-by-Step Solution
Locate Candidate Row Using Binary Search on Row Boundaries
| 3 | ROWS, COLS = len(matrix), len(matrix[0])
|
| 4 | top, bot = 0, ROWS - 1
|
| 6 | while top <= bot:
|
| 7 | row = (top + bot) // 2
|
| 8 | if target > matrix[row][-1]:
|
| 9 | top = row + 1
|
| 10 | elif target < matrix[row][0]:
|
| 11 | bot = row - 1
|
| 12 | else:
|
| 13 | break
|
Objective
To identify the row that could contain the target by comparing the target with the first and last elements of the middle row.
Key Insight
Because each row is sorted and the first element of each row is greater than the last element of the previous row, the target must lie within a single row whose first element is less than or equal to the target and last element is greater than or equal to the target. Binary searching over the rows using these boundary checks efficiently narrows down the candidate row in O(log m) time.
Interview Quick-Check
Core Logic
Binary search over rows compares the target with the first and last elements of the middle row to decide whether to move up or down the row range.
State & Boundaries
The loop continues while top <= bot, ensuring all candidate rows are considered.
Common Pitfalls & Bugs
Failing to check both the first and last elements of the row can lead to incorrect candidate row selection.
Confirm Candidate Row and Return False if None Found
| 15 | if not (top <= bot):
|
| 16 | return False
|
Objective
To verify if a candidate row was found and return false immediately if the target cannot be in any row.
Key Insight
If the binary search over rows completes without finding a row whose boundaries contain the target, the target is not present in the matrix. This early exit prevents unnecessary further searching and ensures correctness.
Interview Quick-Check
State & Boundaries
Check if top <= bot after the row search loop to confirm candidate row existence.
Common Pitfalls & Bugs
Neglecting this check can lead to searching an invalid row index, causing errors or incorrect results.
Perform Binary Search Within Candidate Row to Find Target
| 18 | row = (top + bot) // 2
|
| 19 | l, r = 0, COLS - 1
|
| 20 | while l <= r:
|
| 21 | m = (l + r) // 2
|
| 22 | if target > matrix[row][m]:
|
| 23 | l = m + 1
|
| 24 | elif target < matrix[row][m]:
|
| 25 | r = m - 1
|
| 26 | else:
|
| 27 | return True
|
Objective
To locate the target within the identified candidate row using standard binary search.
Key Insight
Once the candidate row is identified, the problem reduces to a classic binary search within a sorted array. This step efficiently finds the target in O(log n) time by comparing the target with the middle element and adjusting the search boundaries accordingly.
Interview Quick-Check
Core Logic
Binary search within the row compares the target with the middle element and moves left or right pointers accordingly.
State & Boundaries
The loop continues while l <= r, ensuring all elements in the row are considered.
Common Pitfalls & Bugs
Returning true immediately upon finding the target avoids unnecessary further searching.
Return False When Target is Not Found in Candidate Row
| 29 | return False |
Objective
To return false after exhausting the binary search within the candidate row without finding the target.
Key Insight
If the binary search completes without locating the target, it confirms the target is not present in the matrix. Returning false here correctly signals the absence of the target.
Interview Quick-Check
State & Boundaries
Return false only after the binary search loop ends without a match.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
return TrueReturn true when the target is found.
Finding the target confirms its presence in the matrix and ends the search immediately.
breakStop the row search once a candidate row is found.
Breaking preserves the identified candidate row for the second binary search.
if not (top <= bot):Check whether no candidate row was found.
If the row search ended without a candidate row, the target cannot be in the matrix.
return FalseReturn false when no candidate row exists.
Returning immediately prevents searching inside an invalid row.
else:Enter the successful match branch.
Reaching this branch means the midpoint value matches the target exactly.
return FalseReturn false when the target is not found.
If the row search and the in-row search both fail, the target is absent from the matrix.
if target > matrix[row][-1]:Check whether the target is larger than the current row's last element.
If the target exceeds the last value in the current row, it must lie in a lower row.
elif target < matrix[row][0]:Check whether the target is smaller than the current row's first element.
If the target is smaller than the first value in the current row, it must lie in a higher row.
else:Enter the candidate-row branch.
Reaching this branch means the target lies within the current row's value range.
if target > matrix[row][m]:Check whether the target is larger than the midpoint value.
If the target is larger than the midpoint value, it must lie to the right.
elif target < matrix[row][m]:Check whether the target is smaller than the midpoint value.
If the target is smaller than the midpoint value, it must lie to the left.
row = (top + bot) // 2Compute the middle row index.
Selecting the middle row halves the remaining row search space.
top = row + 1Move the top pointer below the current row.
Moving the top pointer down discards rows that are definitely too small.
bot = row - 1Move the bottom pointer above the current row.
Moving the bottom pointer up discards rows that are definitely too large.
m = (l + r) // 2Compute the middle column index.
Selecting the middle column halves the remaining search space in the row.
l = m + 1Move the left pointer rightward.
Moving left rightward discards values that are definitely too small.
r = m - 1Move the right pointer leftward.
Moving right leftward discards values that are definitely too large.
while top <= bot:Binary search across the rows.
The loop continues while there are still candidate rows to inspect.
row = (top + bot) // 2Select the candidate row.
This recomputes the row that survived the first binary search.
while l <= r:Binary search within the candidate row.
The second binary search checks the sorted candidate row for the target.
ROWS, COLS = len(matrix), len(matrix[0])Calculate the number of rows and columns in the matrix.
Knowing the matrix dimensions is essential for setting the boundaries of the two binary searches.
top, bot = 0, ROWS - 1Initialize the top and bottom row pointers.
These pointers define the initial search space over all rows.
l, r = 0, COLS - 1Initialize the left and right column pointers.
These pointers define the search interval inside the chosen row.
Test Your Understanding
Why is it necessary to perform two separate binary searches instead of a single binary search treating the matrix as a flattened sorted array?
Because the matrix is sorted row-wise with the property that each row's first element is greater than the previous row's last, it can be treated as a sorted list of rows. Performing two binary searches leverages this structure explicitly and avoids the complexity of index mapping required for a single binary search on a flattened array, simplifying implementation and maintaining O(log m + log n) time.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Search a 2D Matrix from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Search a 2D Matrix drill