059 — Search a 2D Matrix

59 — Search a 2D Matrix

LeetCode 74 · Medium. You are given an m x n integer matrix matrix with two properties: each row is sorted in ascending order, and the first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix, or false otherwise. The algorithm must run in O(log(m * n)) time.

---

🍽️ Intuition

The two properties in the setup — rows sorted left to right, and each row's first value bigger than the previous row's last value — aren't two separate facts to juggle. Together they mean something stronger: if you read the matrix row by row, left to right, top to bottom, the values come out in one single ascending sequence, exactly as if the whole 2D grid had been flattened into a 1D sorted array. That reframing is the entire problem. Once you see the matrix as "a sorted array wearing a 2D costume," the solution is just Binary Search chapter 58 again, with one extra step: translating a flat index back into a (row, col) pair.

---

🚩 Pattern-Recognition Cue

"Each row sorted" plus "first element of a row exceeds the last element of the previous row" is the tell that a 2D grid is secretly a 1D sorted sequence in disguise — whenever a matrix has global monotonic order (not just per-row or per-column order), flattening it and binary searching the flattened index is on the table, giving O(log(m*n)) instead of scanning cell by cell.

---

🐢 Brute Force

Check every cell.

func searchMatrixBruteForce(_ matrix: [[Int]], _ target: Int) -> Bool {
    for row in matrix {
        for value in row {
            if value == target {
                return true
            }
        }
    }
    return false
}

// smoke test
print(searchMatrixBruteForce([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3))    // true
print(searchMatrixBruteForce([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13))   // false

Big-O: O(m * n) time — every cell can be visited in the worst case. O(1) space.

---

🚀 Optimal

Binary search over the flat index range 0..<(rows * cols), mapping each midpoint back to (row, col) with integer division and modulo.

func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
    let rows = matrix.count
    guard rows > 0, matrix[0].count > 0 else { return false }
    let cols = matrix[0].count

    var lo = 0
    var hi = rows * cols - 1

    while lo <= hi {
        let mid = lo + (hi - lo) / 2
        let row = mid / cols   // flat index → row
        let col = mid % cols   // flat index → column within that row
        let value = matrix[row][col]

        if value == target {
            return true
        } else if value < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }

    return false
}

// smoke test
print(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3))    // true
print(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13))   // false
print(searchMatrix([[1]], 1))                                       // true

Big-O: O(log(m * n)) time, equivalent to O(log m + log n) — a single binary search over the flattened index space. O(1) space.

---

🔑 The Key Insight

The brute force treats the matrix as m unrelated sorted rows and checks them one at a time, throwing away the fact that the rows are also ordered relative to each other. The optimal solution exploits that global ordering: since reading row-major (left to right, top to bottom) produces one unbroken ascending sequence, index i in that flattened sequence corresponds to matrix[i / cols][i % cols] — a constant-time, no-copy translation. That means Binary Search chapter 58's exact algorithm applies unmodified to a range of flat indices; the only new idea is the (row, col) mapping, not a new search strategy.

---

🔗 Related Chapters

• Binary Search — the flattened matrix is searched with the same [lo, hi]-halving template as any sorted array.
• Arrays & Strings — the matrix is fundamentally a 2D array, and O(1) indexing is what makes the flat-index-to-(row, col) mapping free.
• Binary Search — the 1D version of this exact algorithm; this problem only adds the index-mapping step on top.

---

🧸 Memory Sentence

A matrix where every row's first value beats the previous row's last value isn't really 2D — flatten it in your head with row = mid / cols, col = mid % cols, and it's just Binary Search wearing a grid costume.

---

✅ Check Your Understanding

For matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] (3 rows, 4 columns) and target = 20, what flat index does target live at, and what (row, col) does that map to? Walk through the first two midpoint checks the optimal algorithm would make.

---

⬅️ Previous: Binary Search · Next: Koko Eating Bananas ➡️