Search a 2D Matrix
Last Updated: March 29, 2026
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. This means if you read the matrix row by row, the entire sequence of elements is sorted. We need to determine whether a given target value exists somewhere in this matrix.
The critical insight is that this matrix is essentially 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. So we are really just doing a search in a sorted sequence, which immediately suggests binary search.
Key Constraints:
1 <= m, n <= 100→ The matrix has at most 100 rows and 100 columns, so at most 10,000 elements total. Even an O(m n) scan would be fast, but the problem requires O(log(m n)).- Rows are sorted, and first element of each row > last element of previous row → The entire matrix is globally sorted when read row by row. This is exactly the structure binary search needs.
-10^4 <= matrix[i][j] <= 10^4→ Standard integer range, no overflow concerns.
Approach 1: Brute Force (Linear Scan)
Intuition
The simplest approach: just check every element in the matrix. Iterate through each row and each column, and if you find the target, return true. If you exhaust the entire matrix without finding it, return false.
This does not use the sorted property at all, which is wasteful, but it establishes a baseline and makes the logic crystal clear.
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 entire matrix is one long sorted sequence when read row by row.
So we can run a standard binary search on indices 0 through m*n - 1. The trick is converting a 1D index mid to a 2D position: the row is mid / n and the column is mid % n, where n is the number of columns. This lets us look up the actual matrix value at any virtual 1D position in O(1).
The two matrix properties guarantee a total ordering: matrix[0][0] < matrix[0][1] < ... < matrix[0][n-1] < matrix[1][0] < ... < matrix[m-1][n-1]. This is exactly the same as a sorted 1D array. Binary search works on any sorted sequence, so by mapping 1D indices to 2D coordinates with row = mid / n and col = mid % n, we get O(log(m * n)) search for free.
The mapping is straightforward because the matrix is stored in row-major order. Index 0 maps to (0, 0), index n-1 maps to (0, n-1), index n maps to (1, 0), and so on. Integer division gives the row, modulo gives the column.
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.