240. Search a 2D Matrix II
Model: qwen3.5:9b
Topics: Binary Search,Divide and Conquer
FAANG asked: 1
Acceptance rate: 45.3%
Problem Breakdown
We are given an m x n integer matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. We need to determine if a specific target value exists within this structure.
Inputs:
- A 2D list of integers (
matrix). - An integer target value (
target).
Outputs:
- Boolean:
Trueif found,Falseotherwise.
Constraints & Edge Cases:
- Matrix dimensions and are between 1 and 300 (non-empty per constraints).
- Values range from to .
- The sorting property is strict for rows and columns individually, but not necessarily globally. This means we cannot simply flatten the matrix or use standard binary search on a flattened array without verifying order preservation across boundaries (which doesn’t hold here).
Intuition
A brute-force approach would iterate through every cell to check if it matches target. While this works for small constraints ( operations), the time complexity is . Given that we have sorted rows and columns, we can do significantly better.
The key insight relies on eliminating entire lines (rows or columns) from consideration in each step:
- If I am at a cell
(row, col)wherematrix[row][col] > target: Since the column is sorted top-to-bottom, all cells below this one are even larger. Thus, we can discard everything below and to the right of current position? No, specifically for columns: if current value is too big, any value in that same column at a lower row index will also be bigger (due to col sort). So we must move Left () because values decrease as we go left. - If
matrix[row][col] < target: Since the row is sorted left-to-right, all cells to the right are larger. We need a bigger value, so we can discard everything in this column above us? No, specifically for rows: if current value is too small, any cell in that same row at an earlier index will be smaller (due to row sort). So we must move Down () because values increase as we go down.
Starting from the top-right corner (0, n-1) allows us to make this decision deterministically:
- If current > target Move Left (discard column below/right logic implies moving left is safe).
- If current < target Move Down (discard row above/left logic implies moving down is safe).
This reduces the search space by one dimension per step.
Approach
- Initialize pointers at
row = 0andcol = n - 1. This places us at the top-right corner of the matrix. - Enter a loop that continues as long as we are within valid row bounds (
row < m) and column bounds (col >= 0). - Compare
matrix[row][col]withtarget:- If equal, return
True. - If greater than target: The current value is too large for this position. Since columns increase downwards, all values below are also larger. We need a smaller number, so we move Left (
col -= 1). - If less than target: The current value is too small. Since rows increase rightwards, all values to the left are even smaller (and thus invalid). Wait, if it’s too small, and row increases L->R, then moving Right would be bigger? No, we want a bigger number. Moving Down () gives us larger numbers because columns increase downwards.
- If equal, return
- If the loop terminates without finding
target, returnFalse.
Complexity Analysis
- Time Complexity: . In each iteration of the while loop, we either increment
rowor decrementcol. Since both indices can change at most once per dimension (from 0 to m and from n-1 down to -1), the maximum number of steps is bounded by the sum of dimensions. - Space Complexity: . We only use two integer variables for pointers, 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)
n = len(matrix[0])
# Start at top-right corner
row, col = 0, n - 1
while row < m and col >= 0:
current_val = matrix[row][col]
if current_val == target:
return True
elif current_val > target:
# Value is too large; move left to find smaller values in the same row.
col -= 1
else:
# Value is too small; move down to find larger values in the same column.
row += 1
return False
Edge Cases Handled
- Empty Matrix: Although constraints specify , the initial check
if not matrix or not matrix[0]handles empty inputs gracefully. - Single Row/Column: The logic holds naturally; if only one row exists, we can’t move down (loop condition fails), forcing left movement until found/exhausted. Same for single column.
- Target Outside Range: If target is smaller than the minimum element in the matrix or larger than maximum, pointers will eventually hit boundaries (
row == morcol < 0) and returnFalse. - Duplicates: The sorting property allows duplicates within rows/cols; strict inequality checks handle finding any instance of the target.