Search a 2D Matrix
Understanding the Problem
We have a 2D matrix where each row is sorted left to right, and the last element of any row is smaller than the first element of the next row. Reading the matrix row by row produces one fully sorted sequence of elements. We need to determine whether a given target value exists somewhere in this matrix.
This matrix is a sorted 1D array that has been wrapped into rows. The two properties guarantee a strict global ordering: every element in row i is smaller than every element in row i+1. That makes the problem a search over a sorted sequence, which binary search handles in logarithmic time.
Key Constraints:
1 <= m, n <= 100→ At most 10,000 elements, so an O(m n) scan would finish quickly, but the problem requires O(log(m n)).- Rows are sorted, and the first element of each row exceeds the last element of the previous row → The matrix is globally sorted when read row by row, which is the structure binary search needs.
-10^4 <= matrix[i][j] <= 10^4→ Values fit in a 32-bit integer, som * nand intermediate index math cannot overflow.
Approach 1: Brute Force (Linear Scan)
Intuition
Check every element in the matrix. Iterate through each row and each column, return true when the target appears, and return false after scanning the whole matrix without a match.
This ignores the sorted property, so it does more work than necessary, but it establishes a correct baseline to optimize from.
Algorithm
- Iterate through each row
ifrom 0 to m - 1. - For each row, iterate through each column
jfrom 0 to n - 1. - If
matrix[i][j] == target, return true. - If the loop completes without finding the target, return false.
Example Walkthrough
Code
- Time Complexity: O(m * n). In the worst case, we visit every element in the matrix before concluding the target is not there.
- Space Complexity: O(1). Only loop variables. No extra data structures.
This approach works but ignores the sorted structure entirely. Since the matrix is globally sorted when read row by row, we can treat it as a virtual 1D array and apply binary search.
Approach 2: Binary Search on Virtual 1D Array
Intuition
Because each row is sorted and the first element of each row is greater than the last element of the previous row, the matrix is one long sorted sequence when read row by row.
We run a standard binary search over the indices 0 through m*n - 1 of that virtual sequence. To read the actual value at a virtual index mid, convert it to a 2D position: the row is mid / n and the column is mid % n, where n is the number of columns. That conversion is O(1), so each binary search step looks up its midpoint value in constant time.
The virtual index k counts elements in row-major order: row 0 occupies indices 0 through n-1, row 1 occupies n through 2n-1, and so on. Element k sits in row k / n (how many full rows of n came before it) at column k % n (its offset within that row). Index 0 maps to (0, 0), index n-1 to (0, n-1), index n to (1, 0). Because the values are globally sorted in this same order, binary search over k is a valid binary search over a sorted array.
Algorithm
- Set
left = 0andright = m * n(one past the last index). - While
left < right: - Compute
mid = left + (right - left) / 2. - Convert
midto 2D:row = mid / n,col = mid % n. - If
matrix[row][col] == target, return true. - If
matrix[row][col] < target, setleft = mid + 1. - Otherwise, set
right = mid. - Return false (target not found).
Example Walkthrough
Code
- Time Complexity: O(log(m n)). Standard binary search over m n elements. Each iteration halves the search range.
- Space Complexity: O(1). Only uses a few integer variables for left, right, mid, row, and col.