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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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 columns n of the matrix. We then set two pointers, left to 0 and right to m * 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 than right. This loop will terminate when left and right 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 of left and right by two.
Index Flattening: The mid index is then flattened into two dimensions, x and y, where x is the row number and y is the column number. This is achieved using the divmod function, where mid is divided by the number of columns n, x takes the quotient, and y 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 the right pointer to mid.
- 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 the left pointer to mid + 1.
Final Check: After the while loop, left should point to the index where the target would be if it's present. We take the left index and convert it back into two-dimensional indices to access the matrix element. If matrix[left // n][left % n] is equal to the target, we return true, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Heap sortMerge sortInsertion sortQuick sort

I don’t know

Example 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) and 3 columns (n). We set our left pointer to 0 and our right pointer to m * n - 1, which is 5 in this case (flattening the matrix to a single list would have indices ranging from 0 to 5).
While Loop Begins: Since left (0) is less than right (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. Dividing 2 by the number of columns (3) gives us a quotient of 0 (row index x) and a remainder of 2 (column index y).
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 target 9.
Search Space Halving:
- Since 5 is less than 9, we can eliminate the first half of the search space and update our left index to mid + 1, which is 3.
While Loop Continues: With the updated left being 3 and right still 5, we continue our search.
Mid Calculation and Conversion: Recalculate mid with (left + right) >> 1, which gives us (3 + 5) >> 1 = 4. This mid index corresponds to the second row and second column in our matrix. We divide 4 by the number of columns (3) to get x = 1 and y = 1.
Index Flattening: The element at index 4 is 9 when looking at the matrix, which is exactly our target.
Final Check: Since matrix[x][y] is equal to the target 9, we have successfully found the target in our matrix! The loop terminates and we return true.

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

Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Heap sortMerge sortInsertion sortQuick sort

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

74. Search a 2D Matrix

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings