NeetCode #275LC-74MediumBinary SearchNC 150NC 250
← Back to All Problems#275 · #74 · Search a 2D Matrix(搜索二维矩阵)
📌 Problem Statement & Constraints
You are given an
m x n integer matrix with two properties: each row is sorted left to right, and the first integer of each row is greater than the last integer of the previous row. Given a target, return whether it is in the matrix. Constraints: 1 <= m, n <= 100, -10^4 <= matrix[i][j], target <= 10^4.💡 Core Algorithmic Approaches
- The two properties together mean the matrix is a single sorted array read in row-major order.
- So binary search over the virtual indices
0 .. m*n - 1, mapping indexktomatrix[k // n][k % n]. - This gives O(log(m*n)) time with O(1) space, better than the two-step (row then column) search.
- The row-major mapping is the whole trick -- there is no need to materialise the flattened array.
💻 Benchmark Python3 Implementation
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
v = matrix[mid // n][mid % n] # row-major mapping
if v == target:
return True
if v < target:
lo = mid + 1
else:
hi = mid - 1
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log(m * n)): a single binary search over the flattened index space.
💾 Space Complexity
O(1): no extra array is built.
⚠️ Interview Pitfalls & Follow-ups
- Flattening the matrix into a new list: O(m * n) extra space for no benefit.
- Doing a row binary search and then a column binary search: correct, but O(log m + log n) with more code; the single search is cleaner.
- Using
mid // minstead ofmid // n: the divisor is the number of columns. - Assuming the second property is unnecessary: without it, the row-major order would not be sorted. The staircase variant (240) has only the per-row and per-column sorting, and needs a different approach.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.