Search a 2D Matrix II
MedPrompt
Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.
Example 1:
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: trueExample 2:
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 = 20
Output: false
Constraints:
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The simplest approach is to search every element in the matrix one by one until we find the target element.
Algorithm
- Iterate through each row of the matrix (i from 0 to m-1)
- For each row, iterate through each column (j from 0 to n-1)
- If current element equals target, return true
- If target not found after complete iteration, return false
Walkthrough
In this approach, we iterate through each element in the matrix using nested loops. For each element, we compare it with the target value. If we find a match, we return true. If we complete the search without finding the target, we return false.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; 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) where m is number of rows and n is number of columns
Space
O(1) as we only use constant extra space
Trade-offs
Pros
Simple to implement
No extra space required
Works for any matrix (sorted or unsorted)
Cons
Does not utilize the sorted property of the matrix
Very inefficient for large matrices
Checks every element even when unnecessary
Since each row is sorted, we can perform binary search on each row to find the target element more efficiently than checking each element.
Algorithm
- For each row in the matrix:
- Perform binary search on the current row:
- Calculate middle element
- If middle element is target, return true
- If middle element is less than target, search right half
- If middle element is greater than target, search left half
- If target not found in any row, return false
Walkthrough
This approach takes advantage of the fact that each row is sorted. For each row, we perform a binary search to find the target element. If the element is found in any row, we return true. If we search all rows without finding the target, we return false.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; for (int i = 0; i < m; i++) { int left = 0; int right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (matrix[i][mid] == target) { return true; } else if (matrix[i][mid] < target) { left = mid + 1; } else { right = mid - 1; } } } return false; }}Complexity
Time
O(m * log n) where m is number of rows and n is number of columns
Space
O(1) as we only use constant extra space
Trade-offs
Pros
More efficient than brute force approach
Takes advantage of row-wise sorting
No extra space required
Cons
Does not utilize column-wise sorting
Still needs to check each row
Not the most efficient possible solution
We can start from the top-right corner and use both row and column sorted properties to eliminate either a row or column in each step.
Algorithm
- Start from the top-right corner (row = 0, col = n-1)
- While row is within bounds and col is within bounds:
- If current element equals target, return true
- If current element is greater than target, move left (eliminate column)
- If current element is less than target, move down (eliminate row)
- If we go out of bounds, return false
Walkthrough
This approach starts from the top-right corner of the matrix and uses both the row-wise and column-wise sorting properties. At each step, we compare the current element with the target:
- If current element equals target, we found it
- If current element is greater than target, we can eliminate the current column
- If current element is less than target, we can eliminate the current row
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int row = 0; int col = n - 1; while (row < m && col >= 0) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] > target) { col--; } else { row++; } } return false; }}Complexity
Time
O(m + n) where m is number of rows and n is number of columns
Space
O(1) as we only use constant extra space
Trade-offs
Pros
Most efficient solution
Utilizes both row and column sorting
Eliminates either a row or column in each step
Simple to implement
Cons
Must start from top-right (or bottom-left) corner
Cannot start from arbitrary position
Solutions
Solution
public class Solution { public bool SearchMatrix ( int [][] matrix , int target ) { int m = matrix . Length , n = matrix [ 0 ]. Length ; int i = m - 1 , j = 0 ; while ( i >= 0 && j < n ) { if ( matrix [ i ][ j ] == target ) { return true ; } if ( matrix [ i ][ j ] > target ) { -- i ; } else { ++ j ; } } return false ; } }public class Search_a_2D_Matrix_II { public static void main ( String [] args ) { Search_a_2D_Matrix_II out = new Search_a_2D_Matrix_II (); Solution s = out . new Solution (); System . out . println ( s . searchMatrix ( new int [][]{ { 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 } }, 5 )); } /* valid in Search_a_2D_Matrix, but not in II {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, */ class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { if ( matrix == null || matrix . length == 0 || matrix [ 0 ]. length == 0 ) { return false ; } int row = matrix . length ; int col = matrix [ 0 ]. length ; int i = 0 ; int j = col - 1 ; while ( i < row && j >= 0 ) { int val = matrix [ i ][ j ]; if ( val == target ) { return true ; } else if ( target < val ) { j --; // all numbers in that column are even larger } else { i ++; // all numbers in that row are even smaller } } return false ; } } } ############ class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { int m = matrix . length , n = matrix [ 0 ]. length ; int i = m - 1 , j = 0 ; while ( i >= 0 && j < n ) { if ( matrix [ i ][ j ] == target ) { return true ; } if ( matrix [ i ][ j ] > target ) { -- i ; } else { ++ j ; } } return false ; } }/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function (matrix, target) { const n = matrix[0].length; for (const row of matrix) { let left = 0, right = n; while (left < right) { const mid = (left + right) >> 1; if (row[mid] >= target) { right = mid; } else { left = mid + 1; } } if (left != n && row[left] == target) { return true; } } return false; };# Binary Search Variant def binarySearch ( row : List [ int ], target : int ) -> bool : left , right = 0 , len ( row ) - 1 while left <= right : mid = ( left + right ) // 2 if row [ mid ] == target : return True elif row [ mid ] < target : left = mid + 1 else : right = mid - 1 return False def searchMatrix ( matrix : List [ List [ int ]], target : int ) -> bool : for row in matrix : if binarySearch ( row , target ): return True return False ############## # start from top-right corner class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : if not matrix or not matrix [ 0 ]: return False row , col = len ( matrix ), len ( matrix [ 0 ]) i , j = 0 , col - 1 while i < row and j >= 0 : val = matrix [ i ][ j ] if val == target : return True elif target < val : j -= 1 # all numbers in that column are even larger else : i += 1 # all numbers in that row are even smaller return False # start from bottom-left corner class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : m , n = len ( matrix ), len ( matrix [ 0 ]) i , j = m - 1 , 0 while i >= 0 and j < n : if matrix [ i ][ j ] == target : return True if matrix [ i ][ j ] > target : i -= 1 else : j += 1 return False ############ class Solution ( object ): def searchMatrix ( self , matrix , target ): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ def binarySearch ( nums , target ): start , end = 0 , len ( nums ) - 1 while start + 1 < end : mid = start + ( end - start ) / 2 if nums [ mid ] > target : end = mid elif nums [ mid ] < target : start = mid else : return True if nums [ start ] == target : return True if nums [ end ] == target : return True return False for nums in matrix : if binarySearch ( nums , target ): return True return False// OJ: https://leetcode.com/problems/search-a-2d-matrix-ii/ // Time: O(M + N) // Space: O(1) class Solution { public: bool searchMatrix ( vector < vector < int >>& A , int target ) { int M = A . size (), N = A [ 0 ]. size (), i = 0 , j = N - 1 ; while ( i < M && j >= 0 ) { if ( A [ i ][ j ] == target ) return true ; if ( A [ i ][ j ] < target ) ++ i ; else -- j ; } return false ; } };Video 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.