Problem · LC 74

Search a 2D Matrix

Medium
◧ Template A · index remap

How to recognize it

A matrix where each row is sorted AND the first value of each row exceeds the last of the previous row. That second condition is the tell: the whole grid is one sorted array wearing a 2D costume.

The core idea

Treat the m×n grid as a virtual sorted array of length m·n. Binary search over indices 0..m·n-1 and convert an index k to a cell with row = k // n, col = k % n. No extra memory, one clean log search.

Why It's Tricky

It looks like a 2D problem, so many people try to binary search rows first, then columns. But the problem says rows chain together — so the whole matrix is secretly a 1D sorted array! The trick is recognizing this transformation and doing the index arithmetic correctly.

The Key Insight

The 2D structure is a red herring. Once you flatten the matrix conceptually into one sorted array, it's just Template A. The index remapping (row = k // n, col = k % n) is just bookkeeping — math you know from flattening any 2D structure.

Step-by-Step Walkthrough

Example: 3×4 matrix, target=13

[[1,3,5,7],
[10,11,16,20],
[23,30,34,60]]

Flattened: [1,3,5,7,10,11,16,20,23,30,34,60]

Binary search index 0-11: mid=5 → matrix[5//4][5%4] = matrix[1][1] = 11 < 13 → go right
Next: mid=8 → matrix[8//4][8%4] = matrix[2][0] = 23 > 13 → go left
Next: mid=6 → matrix[6//4][6%4] = matrix[1][2] = 16 > 13 → go left
Next: mid=5 again... found region → return or return false.

time O(log(m·n))
space O(1)
search_a_d_matrix
def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]   # flatten -> 2D
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Interview gotchas

  • Only valid when rows chain together (row i+1 starts above row i ends). If not, this is a different problem — see the follow-up.
  • Index mapping: row = mid // n, col = mid % n. Mixing up n (cols) and m (rows) is the classic bug.

💡 What to Say in the Interview

  • Say: "I notice the matrix is globally sorted — it's like a 1D array in 2D clothing."
  • Explain: "I'll binary search the conceptual 1D array of length m*n and remap indices back to 2D."
  • Walk through: "mid=5 in a 4-column matrix → row=5//4=1, col=5%4=1."
  • Mention: "This only works if rows chain together. If they don't, we'd need a different approach (like start at top-right)."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.