Coding Interview PatternsSearch a 2D Matrix II
MediumModified Binary Search
Search a 2D Matrix II
Explanation & Solution
Description
Write an efficient algorithm that searches for a value target in an m x n integer matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
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
Constraints
m == matrix.lengthn == matrix[i].length1 <= 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
Approach
Modified Binary Search pattern
1. Start from the Top-Right Corner
- Set
row = 0andcol = n - 1(top-right corner). - This position has a special property: everything to its left is smaller, everything below is larger.
2. Staircase Search
- If
matrix[row][col] === target, returntrue. - If
matrix[row][col] < target, the target can't be in this row (all values to the left are even smaller) → move down (row++). - If
matrix[row][col] > target, the target can't be in this column (all values below are even larger) → move left (col--).
3. Out of Bounds
- If
row >= morcol < 0, the target doesn't exist → returnfalse.
🧠 Key Insight
- Starting from the top-right (or bottom-left) gives us a decision at each cell: go left or go down. This is like binary search in two dimensions, eliminating one row or column per step.
Time
O(m + n)at most m + n steps (each step eliminates a row or column).Space
O(1).Visualization
Input:
DFS Traversal5×5 grid
output—
Press play to start dfs traversal
CurrentQueuedVisitedSource
153 steps