Coding Interview PatternsSearch a 2D Matrix
MediumModified Binary Search
Search a 2D Matrix
Explanation & Solution
Description
You are given an m x n integer matrix with the following properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in the matrix, or false otherwise.
You must write an algorithm with **O(log(m * n))** runtime complexity.
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Output: true
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
Approach
Modified Binary Search pattern
1. Treat the Matrix as a Sorted 1D Array
- The matrix has
m * nelements. Because each row's first element is greater than the previous row's last, the entire matrix is sorted when read row by row.
2. Map 1D Index to 2D Coordinates
- For any virtual index
mid:row = Math.floor(mid / n),col = mid % n.
3. Standard Binary Search
- Set
lo = 0,hi = m * n - 1. - Compute
mid, map to 2D, comparematrix[row][col]with target. - If equal, return
true. If less,lo = mid + 1. If greater,hi = mid - 1.
4. Return false if Not Found
🧠 Key Insight
- The key trick is recognizing that the matrix’s row-wise and cross-row ordering makes it a single sorted sequence.
Time
O(log(m * n)) — single binary search over the virtual 1D array.Space
O(1).Visualization
Input:
DFS Traversal3×4 grid
output—
Press play to start dfs traversal
CurrentQueuedVisitedSource
75 steps