74. Search a 2D Matrix
Model: qwen3.5:9b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 38.1%
Problem Breakdown
We are given a 2D matrix where each row is sorted in ascending order from left to right. Crucially, there is no overlap between rows: the first element of any specific row is strictly greater than the last element of the previous row (e.g., matrix[i][0] > matrix[i-1][-1]).
Inputs:
matrix: A list of lists containing integers (mrows,ncolumns).target: An integer value to search for.
Outputs:
- Boolean: Returns
Trueif the target exists in the matrix, otherwiseFalse.
Constraints & Edge Cases:
- Dimensions . This is small enough that even linear scan passes easily (), but we are asked for an efficient algorithm.
- Values range from -10^4 to 10^4 (no overflow issues in standard integer types).
- The constraints guarantee non-empty rows/columns, so
mandnwill be at least 1. However, robust code should handle the logic gracefully if dimensions were larger or empty.
Intuition
If we iterate through every element to find the target, that is a brute-force approach with time complexity. Given the sorted nature of both rows and columns (specifically across row boundaries), this structure implies something powerful: the entire matrix can be treated as a single 1D sorted array.
Imagine flattening [[1,3],[4,5]] into [1,3,4,5]. The property that the first element of each row is greater than the last of the previous ensures there are no “dips” between rows. This means we can apply Binary Search directly on this virtual 1D array rather than iterating linearly or doing nested loops.
The key insight is mapping a hypothetical index mid in this flattened space back to actual matrix coordinates (row, col). If the value at that coordinate matches our target, return true; if it’s smaller, we search right (higher indices); if larger, search left. This reduces complexity from linear or even row-by-row binary search ( with overhead) to a single logarithmic pass over the total number of elements.
Approach
- Define Search Space: The virtual array has length
m * n. We set our left pointer (left) at index 0 and right pointer (right) atm * n - 1. - Binary Search Loop: While
left <= right:- Calculate the middle index:
mid = (left + right) // 2.
- Calculate the middle index:
- Coordinate Mapping: Convert this flat
midindex back to matrix coordinates using integer division and modulo arithmetic:- Row index:
row = mid // n - Column index:
col = mid % n
- Row index:
- Comparison: Access the value at
matrix[row][col].- If equal, return
True. - If smaller than target (
val < target), move left pointer tomid + 1. - If larger (
val > target), move right pointer tomid - 1.
- If equal, return
- Termination: If the loop completes without finding the value, return
False.
Complexity Analysis
- Time Complexity: . Since we are performing binary search over a total of elements, and , this is optimal for sorted data. In the worst case (e.g., 100x100), operations count is roughly .
- Space Complexity: . We only use a constant amount of extra space for pointers and indices, regardless of input size.
Solution
def searchMatrix(matrix: list[list[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m = len(matrix) # Number of rows
n = len(matrix[0]) # Number of columns (width)
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
# Map the flat index 'mid' back to row and column indices
row_idx = mid // n
col_idx = mid % n
current_val = matrix[row_idx][col_idx]
if current_val == target:
return True
elif current_val < target:
left = mid + 1
else:
right = mid - 1
return False
Edge Cases Handled
- Single Element Matrix: The loop handles
leftandrightconverging on the single index correctly. - Target Outside Range: If target is smaller than min or larger than max, binary search naturally narrows pointers until they cross (
left > right) without infinite loops. - Negative Values: Comparison logic works identically for negative integers as positive ones in Python/standard integer arithmetic.
- Constraints Compliance: The code assumes valid input per constraints (), but includes a quick check at the start to prevent index errors if an empty matrix were passed unexpectedly (defensive programming).