74. Search a 2D Matrix
Problem Description
You are given a two-dimensional array, referred to as a 'matrix', where each row is sorted in ascending order, and the first element of each row is greater than the last element of the previous row. Your task is to check whether a given integer, 'target', exists within this matrix. To solve this problem efficiently, you must devise an algorithm that operates with a time complexity of O(log(m * n))
, where m
is the number of rows and n
is the number of columns in the matrix. This time complexity hint suggests that we should consider a binary search approach, as it can perform searches in logarithmic time.
Intuition
Given the properties of the matrix, we can treat it as a sorted list. The idea here is that even though the matrix has two dimensions, the sorted nature of the rows and the rule that the first element of the current row is greater than the last element of the previous row means that a logical ordering exists as if all elements were in a single sorted list.
We can then apply a binary search on this 'virtual' sorted list. First, we initialize two pointers, left
and right
, which represent the start and end of the possible space where the target can be located. These are initially set to point to the first and last indices of this virtual list (0 and m * n - 1
, respectively).
In each iteration of the binary search, we calculate the middle index, mid
. We then convert mid
back into two dimensions, x
and y
, using the divmod function, to compare the matrix element at this position against the target. If the element at [x][y]
is greater than or equal to the target, we bring the right
pointer to mid
, thereby discarding the second half of the search space. If the element is smaller, we increase the left
pointer to mid + 1
, discarding the first half of the search space. This process continues until the space is narrowed down to a single element.
Finally, we check if the element at this narrowed down position is equal to the target. If so, we return true; otherwise, false. The binary search guarantees that we will find the target if it exists in the matrix within O(log(m * n))
time complexity.
Learn more about Binary Search patterns.
Solution Approach
The solution approach implements a binary search algorithm, which is a classic method used to find an element within a sorted list in logarithmic time. However, in this context, we are using binary search on a two-dimensional matrix by treating it as if it were a linear array. Here's how it's done:
-
Variables Setup: We start by calculating the number of rows
m
and columnsn
of the matrix. We then set two pointers,left
to 0 andright
tom * n - 1
, which represent the range of possible indexes where our target might be if we were to flatten the matrix into a single list. -
While Loop: The search process continues while
left
is less thanright
. This loop will terminate whenleft
andright
converge on the index where the target either is or would be if it were in the matrix. -
Mid Calculation and Conversion: Inside the loop, the mid-point index is calculated using the expression
(left + right) >> 1
, which is a bitwise operation equivalent to dividing the sum ofleft
andright
by two. -
Index Flattening: The mid index is then flattened into two dimensions,
x
andy
, wherex
is the row number andy
is the column number. This is achieved using thedivmod
function, wheremid
is divided by the number of columnsn
,x
takes the quotient, andy
takes the remainder of this division. -
Search Space Halving: Depending on the value at
matrix[x][y]
, we adjust our search space:- If
matrix[x][y]
is greater than or equal to the target, it means the target, if present, should be to the left, including the current mid. We then move theright
pointer tomid
. - Conversely, if
matrix[x][y]
is less than the target, the target can only be on the right, excluding the current mid. We then set theleft
pointer tomid + 1
.
- If
-
Final Check: After the while loop,
left
should point to the index where the target would be if it's present. We take theleft
index and convert it back into two-dimensional indices to access the matrix element. Ifmatrix[left // n][left % n]
is equal to the target, we returntrue
, indicating the target is present in the matrix.
This binary search algorithm effectively flattens the 2D search space into 1D, allowing us to utilize the time efficiency of binary search in a multidimensional context.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following matrix and we are looking for the target value 9
.
1Matrix: 21 3 5 37 9 11 4 5Target: 69
Here's what the solution would look like step by step:
-
Variables Setup: We start by determining that the matrix has
2
rows (m
) and3
columns (n
). We set ourleft
pointer to0
and ourright
pointer tom * n - 1
, which is5
in this case (flattening the matrix to a single list would have indices ranging from0
to5
). -
While Loop Begins: Since
left
(0
) is less thanright
(5
), we continue our search. -
Mid Calculation and Conversion: We calculate the middle index with the expression
(left + right) >> 1
, which gives us(0 + 5) >> 1 = 2
. Now we need to convert this index back to two dimensions. Dividing2
by the number of columns (3
) gives us a quotient of0
(row indexx
) and a remainder of2
(column indexy
). -
Index Flattening: The element at the middle index, which is in the first row and third column of our matrix, is the number
5
. We compare this with our target9
. -
Search Space Halving:
- Since
5
is less than9
, we can eliminate the first half of the search space and update ourleft
index tomid + 1
, which is3
.
- Since
-
While Loop Continues: With the updated
left
being3
andright
still5
, we continue our search. -
Mid Calculation and Conversion: Recalculate
mid
with(left + right) >> 1
, which gives us(3 + 5) >> 1 = 4
. Thismid
index corresponds to the second row and second column in our matrix. We divide4
by the number of columns (3
) to getx = 1
andy = 1
. -
Index Flattening: The element at index
4
is9
when looking at the matrix, which is exactly our target. -
Final Check: Since
matrix[x][y]
is equal to the target9
, we have successfully found the target in our matrix! The loop terminates and we returntrue
.
By following these steps, this approach uses binary search to resolve the search problem within a two-dimensional matrix efficiently.
Solution Implementation
1class Solution:
2 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3 # Get the number of rows and columns in the matrix
4 num_rows, num_columns = len(matrix), len(matrix[0])
5
6 # Initialize pointers for the binary search
7 left, right = 0, num_rows * num_columns - 1
8
9 # Conduct a binary search in the matrix
10 while left < right:
11 # Calculate the middle index between left and right
12 mid = (left + right) >> 1 # Equivalent to floor division by 2 (mid = (left + right) // 2)
13 # Convert the 1D representation mid back to 2D indices x and y
14 row, column = divmod(mid, num_columns)
15 # If the middle element is greater or equal to the target, go left
16 if matrix[row][column] >= target:
17 right = mid
18 # If the middle element is less than the target, go right
19 else:
20 left = mid + 1
21
22 # After the loop, left should point to the target element if it exists
23 # Check if the target is indeed at the (left // num_columns, left % num_columns) position
24 return matrix[left // num_columns][left % num_columns] == target
25
1// Class name should start with an uppercase letter following Java naming conventions.
2class Solution {
3
4 // Method to search for a target value in a matrix.
5 public boolean searchMatrix(int[][] matrix, int target) {
6 // Get the number of rows and columns from the matrix.
7 int rows = matrix.length, cols = matrix[0].length;
8
9 // Initialize the left and right pointers for the binary search.
10 int left = 0, right = rows * cols - 1;
11
12 // Loop until the search space is reduced to one element.
13 while (left < right) {
14 // Calculate the middle point of the current search space.
15 int mid = (left + right) / 2; // Shift operator can also be used (left + right) >> 1
16
17 // Map the middle index to a 2D position in the matrix.
18 int x = mid / cols, y = mid % cols;
19
20 // Compare the middle element with the target.
21 if (matrix[x][y] >= target) {
22 // If the middle element is greater or equal to the target,
23 // narrow the search to the left half including mid.
24 right = mid;
25 } else {
26 // If the middle element is less than the target,
27 // narrow the search to the right half excluding mid.
28 left = mid + 1;
29 }
30 }
31
32 // After exiting the loop, left should point to the target element, if it exists.
33 // Check if the element at the 'left' position equals the target.
34 return matrix[left / cols][left % cols] == target;
35 }
36}
37
1#include <vector>
2
3class Solution {
4public:
5 // Function to search for a target value in a 2D matrix.
6 bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
7 int rowCount = matrix.size(); // Number of rows in the matrix
8 int colCount = matrix[0].size(); // Number of columns in the matrix
9 int left = 0, right = rowCount * colCount - 1; // Set search range within the flattened matrix
10
11 // Binary search
12 while (left < right) {
13 int mid = left + (right - left) / 2; // Find the mid index
14 int row = mid / colCount; // Compute row index from mid
15 int col = mid % colCount; // Compute column index from mid
16
17 // Compare the element at [row][col] with target
18 if (matrix[row][col] >= target) {
19 // If the element is greater than or equal to target, move the right boundary left
20 right = mid;
21 } else {
22 // If the element is less than target, move the left boundary right
23 left = mid + 1;
24 }
25 }
26
27 // Check if the target is at the final search point
28 return matrix[left / colCount][left % colCount] == target;
29 }
30};
31
1// Function to perform binary search in a 2D matrix where each row and column is sorted.
2// It returns true if the target number is found, otherwise returns false.
3function searchMatrix(matrix: number[][], target: number): boolean {
4 // Get the number of rows in the matrix
5 const numRows = matrix.length;
6 // Get the number of columns in the matrix
7 const numCols = matrix[0].length;
8 // Initialize the left pointer to start the binary search
9 let left = 0;
10 // Initialize the right pointer to the end of the logical 1D representation of the matrix
11 let right = numRows * numCols;
12
13 // Loop until the pointers meet, which means the target is not found if it exits the loop
14 while (left < right) {
15 // Calculate the mid point of the current search space
16 const mid = Math.floor((left + right) / 2);
17 // Compute the row index from the mid point
18 const rowIndex = Math.floor(mid / numCols);
19 // Compute the column index from the mid point
20 const colIndex = mid % numCols;
21
22 // If the element at mid position equals the target, return true for found
23 if (matrix[rowIndex][colIndex] === target) {
24 return true;
25 }
26
27 // Otherwise, move the search space depending on the comparison with the target
28 if (matrix[rowIndex][colIndex] < target) {
29 left = mid + 1; // Move the left pointer to narrow the search space
30 } else {
31 right = mid; // Move the right pointer to narrow the search space
32 }
33 }
34
35 // If we exit the loop, the target was not found in the matrix
36 return false;
37}
38
Time and Space Complexity
The time complexity of the searchMatrix function is O(log(m*n))
where m
is the number of rows and n
is the number of columns in the matrix. This is because the function performs a binary search on a virtual flattened list representation of the matrix which has m*n
elements. The search converges by halving the candidate range in each iteration.
The space complexity of the searchMatrix function is O(1)
. This is achieved as no additional storage that scales with the input size is being used. All the operations are done in place with a few auxiliary variables that occupy constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.