⚡Flashcard Drill➔
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

  1. The two properties together mean the matrix is a single sorted array read in row-major order.
  2. So binary search over the virtual indices 0 .. m*n - 1, mapping index k to matrix[k // n][k % n].
  3. This gives O(log(m*n)) time with O(1) space, better than the two-step (row then column) search.
  4. 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 // m instead of mid // 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems