You are given an m x n integer matrix matrix with the following two properties:
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: true
Example 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 <= 104The key observation in Search a 2D Matrix is that the matrix follows a sorted structure: each row is sorted and the first element of every row is greater than the last element of the previous row. This property allows us to treat the matrix like a single sorted array.
A common approach is to perform binary search across the entire matrix by conceptually flattening it. Instead of converting it to a new array, we map a one-dimensional index back to matrix coordinates using row = mid / n and col = mid % n. This allows efficient lookup while maintaining the sorted order.
Another strategy is a two-step binary search: first locate the potential row where the target could exist, and then run binary search within that row. Both methods leverage the sorted structure to avoid scanning the whole matrix.
These techniques significantly reduce search time compared to linear traversal, making them ideal for coding interviews where efficiency is critical.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search on Flattened Matrix | O(log(m * n)) | O(1) |
| Row Selection + Binary Search | O(log m + log n) | O(1) |
NeetCode
The matrix can be viewed as a single sorted list. Hence, we can perform a binary search on the entire matrix by treating it as a 1D array. Suppose we have a matrix of size m x n, any element in the matrix can be accessed using a single index calculated as follows:
Element at index k can be accessed using matrix[k / n][k % n], where / and % represent integer division and modulus operations, respectively.
This approach ensures that the solution operates in O(log(m * n)) time complexity as required.
Time complexity: O(log(m * n))
Space complexity: O(1)
1#include <stdbool.h>
2bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
3 int m = matrixSize;
4The function searchMatrix implements binary search on a conceptual 1D version of the matrix. The mid index is calculated using integer division and modulus to map it to the matrix cell. This mapping ensures that all matrix elements can be inspected via binary search.
The problem also allows for a two-step binary search owing to the special properties of the matrix. First, we identify the row which potentially contains the target by performing binary search on first elements of each row. Then, we conduct a binary search in that specific row.
Although not strictly O(log(m * n)), this approach exploits the matrix's properties in an efficient manner for similar effective results.
Time complexity: O(log(m) + log(n))
Space complexity: O(1)
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar variations frequently appear in technical interviews at companies like Amazon, Google, and Microsoft. It tests understanding of binary search, index mapping, and matrix traversal patterns.
The optimal approach treats the matrix as a single sorted array and applies binary search. By mapping the mid index back to row and column positions, we can search the matrix in O(log(m*n)) time without extra space.
Yes, you could scan each row or each element sequentially, but that would take O(m*n) time. Binary search is preferred because it significantly reduces the search time and is expected in interviews.
The problem primarily relies on arrays and binary search. The sorted property of rows and their ordering across rows allows the matrix to behave like a continuous sorted list.
This C code expands the binary search to two distinct logical steps: first identifying the potential row and then binary searching within that row itself to find the target efficiently.