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 <= 104Problem Overview: You are given an m x n 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. The task is to determine whether a given target value exists in the matrix.
Approach 1: Linear Scan (O(m * n) time, O(1) space)
The most direct method is to iterate through every element in the matrix and compare it with the target. Use nested loops: the outer loop scans rows and the inner loop scans columns. The algorithm stops early if the target is found. This approach requires no additional data structures and works for any matrix layout, but it ignores the sorted structure of the matrix and performs unnecessary comparisons.
Time complexity is O(m * n) because every cell may be visited in the worst case. Space complexity is O(1). This approach is useful only as a baseline or when the matrix is extremely small.
Approach 2: Two-step Binary Search (O(log m + log n) time, O(1) space)
The matrix ordering provides a key observation: the first column effectively acts like a sorted list of row ranges. First perform a binary search on rows to find the row that could contain the target. Compare the target with the first and last elements of each candidate row to narrow the search. Once the correct row is identified, run a second binary search on that row to locate the target value.
This method leverages properties of both binary search and sorted arrays. The first search takes O(log m) time and the second takes O(log n). Space complexity remains O(1) since the search operates directly on the matrix.
Approach 3: Binary Search Treating Matrix as 1D (O(log(m * n)) time, O(1) space)
Because each row's first element is greater than the previous row's last element, the entire matrix behaves like a single sorted array. Treat the matrix as a virtual 1D array of length m * n. During binary search, convert the midpoint index into matrix coordinates using row = mid / n and col = mid % n.
This removes the need for two separate searches and performs a single O(log(m * n)) binary search. Only index arithmetic is required, so space complexity stays O(1). This technique is a common pattern when working with sorted matrix problems.
Recommended for interviews: Interviewers typically expect the binary search solution that treats the matrix as a flattened sorted array. It demonstrates that you recognize the global ordering property and can map 1D indices to 2D coordinates efficiently. Starting with the brute force scan shows baseline reasoning, but the O(log(m * n)) approach demonstrates strong algorithmic thinking.
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.
The 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.
C++
Java
Python
C#
JavaScript
Time complexity: O(log(m * n))
Space complexity: O(1)
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.
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.
C++
Java
Python
C#
JavaScript
Time complexity: O(log(m) + log(n))
Space complexity: O(1)
| Approach | Complexity |
|---|---|
| Binary Search on Matrix as a 1D Array | Time complexity: |
| Two-step Binary Search (Row then Column) | Time complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(m * n) | O(1) | Baseline approach or when the matrix is very small |
| Two-step Binary Search (Row then Column) | O(log m + log n) | O(1) | When rows are clearly separated ranges and you want an intuitive binary search approach |
| Binary Search on Matrix as 1D Array | O(log(m * n)) | O(1) | Most optimal and common interview solution leveraging global sorted order |
Search a 2D Matrix - Leetcode 74 - Python • NeetCode • 206,302 views views
Watch 9 more video solutions →Practice Search a 2D Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor