Understanding the Problem
We are given an N x M matrix with two important properties:
- Each row is sorted in ascending order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer Target
, we need to determine if it exists in the matrix.
Key Observations
- The matrix is structured in a way that if we flatten it row-wise, it would form a fully sorted 1D array.
- This means that we can use binary search, which efficiently searches for elements in a sorted array.
Approach
Since the matrix can be conceptually treated as a sorted 1D array, we can apply binary search directly. Instead of manually flattening the matrix, we use mathematical indexing to map a 1D index into 2D row-column coordinates:
- Index Mapping:
- Consider the matrix as a 1D array where each index (i) corresponds to:
- Row: i / M
- Column: i % M
- Consider the matrix as a 1D array where each index (i) corresponds to:
Using this, we can access the value at any index without explicitly converting the matrix into an array.
Binary Search Execution
-
Initialize two pointers:
left = 0
(beginning of the matrix)right = N * M - 1
(last index in the conceptual 1D array)
-
Run a binary search:
- Compute
mid = (left + right) / 2
. - Convert
mid
into row and column using the formulas above. - If
matrix[mid / M][mid % M]
equalstarget
, returnTrue
. - If
matrix[mid / M][mid % M]
is less thantarget
, moveleft
tomid + 1
. - Otherwise, move
right
tomid - 1
.
- Compute
-
If the loop ends without finding the target, return
False
.
Complexity Analysis
Since we are performing binary search on a sorted N x M matrix, the time complexity is:
O(log (N x M)) = O(log N + log M)
- The space complexity is O(1) as we use only a few extra variables.
- This is faster than O(N + M), which would be the complexity of a naive row-wise or column-wise search.