Search a 2D Matrix
MedPrompt
You are given an m x n integer matrix matrix with the following two 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 matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: trueExample 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
Approaches
4 approaches with complexity analysis and trade-offs.
This is the most straightforward but least efficient approach. We can simply iterate through every cell of the m x n matrix and check if the element at that cell is equal to the target. This method does not take advantage of the matrix's special sorted structure.
Algorithm
- Get the dimensions of the matrix,
m(rows) andn(columns). - Iterate through each row
ifrom0tom-1using a for loop. - For each row
i, iterate through each columnjfrom0ton-1using a nested for loop. - Inside the inner loop, check if the element
matrix[i][j]is equal to thetarget. - If a match is found, return
trueimmediately. - If the loops complete without finding the
target, returnfalseafter the loops finish.
Walkthrough
The algorithm uses two nested loops to traverse the matrix. The outer loop iterates through the rows from index 0 to m-1, and the inner loop iterates through the columns from index 0 to n-1. In each iteration of the inner loop, we compare the current element matrix[row][col] with the target value. If they are equal, we have found the target and can return true. If we traverse the entire matrix and do not find the target, the loops will complete, and we return false.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; if (m == 0) { return false; } int n = matrix[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == target) { return true; } } } return false; }}Complexity
Time
O(m * n)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Works on any 2D matrix, regardless of whether it's sorted or not.
Cons
Highly inefficient as it does not leverage the sorted properties of the matrix.
Fails to meet the
O(log(m * n))time complexity requirement specified in the problem description.
A better approach than brute force is to leverage the fact that each row is sorted. We can iterate through each row and, for each one, perform an efficient binary search to check for the target's presence. This avoids a linear scan of every single element.
Algorithm
- Iterate through each row
iof the matrix from0tom-1. - For each row, check if the
targetcould potentially be in that row. This can be done by checking iftargetis between the first (matrix[i][0]) and last (matrix[i][n-1]) elements of the row. - If the
targetis within the range of the current row, perform a standard binary search on that rowmatrix[i]. - If the binary search finds the
target, returntrue. - If the loop finishes after checking all rows and the
targetis not found, returnfalse.
Walkthrough
This method involves a linear scan of the rows. For each row, we first perform a quick check to see if the target could even exist in that row. Since each row is sorted, the target must be greater than or equal to the first element and less than or equal to the last element. If this condition holds, we then apply a binary search on that specific row. If the binary search finds the element, we return true. If we iterate through all the rows without finding the target, we conclude it's not in the matrix and return false.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; if (m == 0) { return false; } int n = matrix[0].length; for (int i = 0; i < m; i++) { if (n > 0 && target >= matrix[i][0] && target <= matrix[i][n - 1]) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (matrix[i][mid] == target) { return true; } else if (matrix[i][mid] < target) { low = mid + 1; } else { high = mid - 1; } } } } return false; }}Complexity
Time
O(m * log(n))
Space
O(1)
Trade-offs
Pros
More efficient than the brute-force approach.
Effectively uses the sorted property of individual rows.
Cons
Does not utilize the property that rows are sorted with respect to each other (i.e.,
matrix[i-1][n-1] < matrix[i][0]).The time complexity does not meet the
O(log(m * n))requirement for all cases, especially whenmis large.
This approach fully utilizes both sorted properties of the matrix to achieve the desired logarithmic time complexity. It involves two phases of binary search: first to find the correct row where the target might exist, and second to find the target within that specific row.
Algorithm
- Step 1: Find the Row. Perform a binary search on the rows of the matrix (from index
0tom-1).- For a middle row
mid, comparetargetwith the first (matrix[mid][0]) and last (matrix[mid][n-1]) elements of that row. - If
target < matrix[mid][0], the target must be in an earlier row, so adjust the search space to the upper half. - If
target > matrix[mid][n-1], the target must be in a later row, so adjust the search space to the lower half. - If
matrix[mid][0] <= target <= matrix[mid][n-1], we have found the correct row. Store this row index and proceed to Step 2.
- For a middle row
- Step 2: Find the Element. Perform a standard binary search for the
targetwithin the row identified in Step 1. - If the
targetis found in Step 2, returntrue. - If no suitable row is found in Step 1, or the
targetis not found in Step 2, returnfalse.
Walkthrough
The key insight is that we can first narrow down the search to a single row. Since the first element of each row is greater than the last element of the previous row, we can perform a binary search on the rows themselves. We search for a row i such that matrix[i][0] <= target <= matrix[i][n-1]. This first binary search takes O(log m) time. Once we identify this potential row, we perform a second, standard binary search on this row's elements to find the target. This second search takes O(log n) time. The total time complexity is the sum of these two searches.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; if (m == 0) return false; int n = matrix[0].length; if (n == 0) return false; // Binary search to find the row int top = 0, bottom = m - 1; int targetRow = -1; while (top <= bottom) { int midRow = top + (bottom - top) / 2; if (target >= matrix[midRow][0] && target <= matrix[midRow][n - 1]) { targetRow = midRow; break; } else if (target < matrix[midRow][0]) { bottom = midRow - 1; } else { top = midRow + 1; } } if (targetRow == -1) { return false; // Target is not in the range of any row } // Binary search within the identified row int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (matrix[targetRow][mid] == target) { return true; } else if (matrix[targetRow][mid] < target) { left = mid + 1; } else { right = mid - 1; } } return false; }}Complexity
Time
O(log(m) + log(n))
Space
O(1)
Trade-offs
Pros
Highly efficient, meeting the problem's time complexity requirement.
Logically separates the problem into two smaller, manageable binary searches.
Cons
The implementation is slightly more complex as it involves two separate binary search logics.
This is arguably the most elegant and efficient approach. The matrix's properties guarantee that if we were to flatten it into a single list, that list would be sorted. We can perform a single binary search on this "virtual" 1D array without actually creating it in memory.
Algorithm
- Initialize two pointers,
left = 0andright = m * n - 1, representing the start and end of the virtual 1D array. - While
left <= right:- Calculate the middle index
mid = left + (right - left) / 2. - Convert the 1D index
midto 2D coordinates:row = mid / n,col = mid % n. - Get the element
val = matrix[row][col]. - If
val == target, returntrue. - If
val < target, the target must be in the right half, so move theleftpointer tomid + 1. - If
val > target, the target must be in the left half, so move therightpointer tomid - 1.
- Calculate the middle index
- If the loop terminates, the target was not found, so return
false.
Walkthrough
We can treat the m x n matrix as a sorted 1D array of size m * n. The binary search will operate on indices from 0 to m * n - 1. The main challenge is to map a 1D index from our binary search back to the 2D matrix coordinates (row, col). This mapping is straightforward: for a given 1D index k and a matrix with n columns, the corresponding row is k / n and the col is k % n. With this mapping, we can perform a standard binary search on the range of indices, comparing matrix[mid / n][mid % n] with the target in each step to narrow down the search space.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; if (m == 0) { return false; } int n = matrix[0].length; int left = 0; int right = m * n - 1; while (left <= right) { int mid = left + (right - left) / 2; int midElement = matrix[mid / n][mid % n]; if (midElement == target) { return true; } else if (midElement < target) { left = mid + 1; } else { right = mid - 1; } } return false; }}Complexity
Time
O(log(m * n))
Space
O(1)
Trade-offs
Pros
Most efficient and concise solution.
Implemented with a single, clean binary search loop.
Directly addresses the problem as a search in a single sorted space, which is the core of binary search.
Cons
Requires understanding the mapping from a 1D index to 2D coordinates, which might be slightly less intuitive at first glance.
Solutions
Solution
class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { int m = matrix . length , n = matrix [ 0 ]. length ; int left = 0 , right = m * n - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int x = mid / n , y = mid % n ; if ( matrix [ x ][ y ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return matrix [ left / n ][ left % n ] == target ; } }/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function (matrix, target) { const m = matrix.length, n = matrix[0].length; let left = 0, right = m * n - 1; while (left < right) { const mid = (left + right + 1) >> 1; const x = Math.floor(mid / n); const y = mid % n; if (matrix[x][y] <= target) { left = mid; } else { right = mid - 1; } } return matrix[Math.floor(left / n)][left % n] == target; };class Solution { public: bool searchMatrix ( vector < vector < int >>& matrix , int target ) { int m = matrix . size (), n = matrix [ 0 ]. size (); int left = 0 , right = m * n - 1 ; while ( left < right ) { int mid = left + right >> 1 ; int x = mid / n , y = mid % n ; if ( matrix [ x ][ y ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return matrix [ left / n ][ left % n ] == target ; } };class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : m , n = len ( matrix ), len ( matrix [ 0 ]) left , right = 0 , m * n - 1 while left <= right : # must be <=, not <, for matrax=[[1]],target=1 mid = ( left + right ) >> 1 x , y = divmod ( mid , n ) # note: divide column count if matrix [ x ][ y ] == target : return True elif matrix [ x ][ y ] > target : right = mid - 1 else : left = mid + 1 return False ########### class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : m , n = len ( matrix ), len ( matrix [ 0 ]) left , right = 0 , m * n - 1 while left < right : mid = ( left + right ) >> 1 x , y = divmod ( mid , n ) if matrix [ x ][ y ] >= target : right = mid else : left = mid + 1 return matrix [ left // n ][ left % n ] == targetVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.