Search a 2D Matrix (LeetCode 74)
You're given an m x n grid of integers, matrix, with two guarantees: each row is sorted left-to-right (non-decreasing), and every row's first value is bigger than the previous row's last value — so reading the grid row by row, the numbers only ever increase.
Given a target value, decide whether it appears anywhere in matrix.
Your solution must run in O(log(m * n)) time.
Worked Examples
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3true1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60; 3 is there, at matrix[0][1].matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13false13 would fall between 11 and 16 in the second row, and it is not in the grid.⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
Core Insight
Reading row by row gives one sorted list, and position mid of that list is matrix[mid // n][mid % n]: binary search the positions and never build the list.
Real-World Scenario & Production Applications
Fixed-size pages: a sorted log split into pages of n records stores record k on page k // n at slot k % n. Looking a key up means binary searching record numbers and reading only the pages the probes land on, never loading the whole log into one array.
Step-by-Step Execution Trace Table
| Step | [lo, hi] | mid | row, col = divmod(mid, 4) | val | Compare with 3 | Action |
|---|---|---|---|---|---|---|
| 1 | [0, 11] | 5 | (1, 1) | 11 | 11 > 3 | hi = mid - 1 = 4 |
| 2 | [0, 4] | 2 | (0, 2) | 5 | 5 > 3 | hi = mid - 1 = 1 |
| 3 | [0, 1] | 0 | (0, 0) | 1 | 1 < 3 | lo = mid + 1 = 1 |
| 4 | [1, 1] | 1 | (0, 1) | 3 | 3 == 3 | Return True |
| 1 | Map i to matrix[i // n][i % n]. |
| 2 | Use Lower Bound over [0, m * n). |
| 3 | Guard the returned index before checking equality. |
Conceptual Narrative
The first value of each row is larger than the last value of the row before it, so reading the matrix row by row gives one sorted list of m * n values. Do not build that list: flat index i names the cell matrix[i // n][i % n], so pass at_least_target and the range [0, m * n) to binary_search_lower_bound, then check the returned cell for equality. Each row holds n cells, so i // n full rows come before index i, and the cell is i % n places into its own row. The cells never decrease as i grows, so at_least_target is False and then True. If target is in the matrix, the first True cell holds it. If not, that cell holds a larger value, or binary_search_lower_bound returns m * n, which is one past the last cell. The trap is the divisor: use n, the number of columns, not m. A square matrix has m == n and hides the wrong divisor, so the bug appears only on another shape.
Dividing the flat index by the number of rows
Reading the index
m * nbefore checking the rangeUsing equality as the check
Writing
>instead of>=in the check
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Each row starts above the preceding row's last value. Reading row by row gives one sorted list, so the check matrix[i // n][i % n] >= target is monotonic.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Lower Bound searches [0, m * n) for the first cell at least target. Index i maps to row i // n and column i % n. After the search, i < m * n guards the equality check.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Divide by n, the number of columns. A square matrix hides a wrong divisor.
Guard i < m * n before reading the final cell.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I would read the matrix as one globally sorted row-major list without copying it. Each row has n cells, so flat index i maps to matrix[i // n][i % n]. I pass the monotonic at-least-target check and [0, m * n) to Lower Bound. Then I check the returned index is inside the matrix before testing equality. This takes O(log(m * n)) time and
O(1)extra space.
Complexity & Mathematical Proof
O(log(M * N))
Look at the code: lo = 0; hi = m * n starts with all M * N flat positions. Each pass of while lo < hi does one index mapping, one cell read and one comparison, then keeps the first passing candidate with hi = mid, or discards failed candidates with lo = mid + 1. The range shrinks M·N → M·N/2 → ... → 1, so there are at most floor(log2(M·N)) + 1 passes of constant work: O(log(M * N)).
O(1)
The code keeps m, n, lo, hi, mid, row, col and val, whatever the matrix size, and returns one boolean. It never builds the flat list, so the extra space is O(1).
T(M·N) = T(M·N / 2) + O(1) = O(log(M * N))
Derivation Progression
O(1)
m, n = len(matrix), len(matrix[0]) and lo = 0; hi = m * n are constant work.
at most floor(log2(M·N)) + 1 passes
Each pass of while lo < hi narrows the candidate range with hi = mid or lo = mid + 1.
O(1) per pass
matrix[i // n][i % n], one cell read and one comparison, whatever M and N are.
O(log(M * N))
Constant work times a logarithmic number of passes.
Variable Definitions
Number of rows, len(matrix)
Number of columns, len(matrix[0])
The flat index being probed, a position in the row-by-row list
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): m, n, lo, hi, mid, row, col, val; no flattened copy
O(1): one boolean
Boundary Best / Worst Cases
: the template searches for the boundary before the equality check
: target is absent or found on the last probe
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every row's first value is bigger than the previous row's last value" and "must run in O(log(m * n)) time". The grid is one sorted list stored row by row, so the move is Global Matrix Bisection: Lower Bound on the flat index, using matrix[i // n][i % n] >= target, then one guarded equality check.
, so at most cells and about 14 probes. Budget: time, space. For grids with more than cells the flat index needs a 64-bit integer in Java, C# or C++.
Copying the grid into one list first costs time and memory and throws the log bound away. When each row is a separate page or block in storage, every probe may be a separate read, so the probe count, about , is what the design must keep small; fetch only the probed rows.
Search a 2D Matrix (LeetCode 74)
You're given an m x n grid of integers, matrix, with two guarantees: each row is sorted left-to-right (non-decreasing), and every row's first value is bigger than the previous row's last value — so reading the grid row by row, the numbers only ever increase.
Given a target value, decide whether it appears anywhere in matrix.
Your solution must run in O(log(m * n)) time.
Worked Examples
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3true1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60; 3 is there, at matrix[0][1].matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13false13 would fall between 11 and 16 in the second row, and it is not in the grid.⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
Core Insight
Reading row by row gives one sorted list, and position mid of that list is matrix[mid // n][mid % n]: binary search the positions and never build the list.
Real-World Scenario & Production Applications
Fixed-size pages: a sorted log split into pages of n records stores record k on page k // n at slot k % n. Looking a key up means binary searching record numbers and reading only the pages the probes land on, never loading the whole log into one array.
Step-by-Step Execution Trace Table
| Step | [lo, hi] | mid | row, col = divmod(mid, 4) | val | Compare with 3 | Action |
|---|---|---|---|---|---|---|
| 1 | [0, 11] | 5 | (1, 1) | 11 | 11 > 3 | hi = mid - 1 = 4 |
| 2 | [0, 4] | 2 | (0, 2) | 5 | 5 > 3 | hi = mid - 1 = 1 |
| 3 | [0, 1] | 0 | (0, 0) | 1 | 1 < 3 | lo = mid + 1 = 1 |
| 4 | [1, 1] | 1 | (0, 1) | 3 | 3 == 3 | Return True |
| 1 | Map i to matrix[i // n][i % n]. |
| 2 | Use Lower Bound over [0, m * n). |
| 3 | Guard the returned index before checking equality. |
Conceptual Narrative
The first value of each row is larger than the last value of the row before it, so reading the matrix row by row gives one sorted list of m * n values. Do not build that list: flat index i names the cell matrix[i // n][i % n], so pass at_least_target and the range [0, m * n) to binary_search_lower_bound, then check the returned cell for equality. Each row holds n cells, so i // n full rows come before index i, and the cell is i % n places into its own row. The cells never decrease as i grows, so at_least_target is False and then True. If target is in the matrix, the first True cell holds it. If not, that cell holds a larger value, or binary_search_lower_bound returns m * n, which is one past the last cell. The trap is the divisor: use n, the number of columns, not m. A square matrix has m == n and hides the wrong divisor, so the bug appears only on another shape.
Dividing the flat index by the number of rows
Reading the index
m * nbefore checking the rangeUsing equality as the check
Writing
>instead of>=in the check
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Each row starts above the preceding row's last value. Reading row by row gives one sorted list, so the check matrix[i // n][i % n] >= target is monotonic.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Lower Bound searches [0, m * n) for the first cell at least target. Index i maps to row i // n and column i % n. After the search, i < m * n guards the equality check.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Divide by n, the number of columns. A square matrix hides a wrong divisor.
Guard i < m * n before reading the final cell.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I would read the matrix as one globally sorted row-major list without copying it. Each row has n cells, so flat index i maps to matrix[i // n][i % n]. I pass the monotonic at-least-target check and [0, m * n) to Lower Bound. Then I check the returned index is inside the matrix before testing equality. This takes O(log(m * n)) time and
O(1)extra space.
Complexity & Mathematical Proof
O(log(M * N))
Look at the code: lo = 0; hi = m * n starts with all M * N flat positions. Each pass of while lo < hi does one index mapping, one cell read and one comparison, then keeps the first passing candidate with hi = mid, or discards failed candidates with lo = mid + 1. The range shrinks M·N → M·N/2 → ... → 1, so there are at most floor(log2(M·N)) + 1 passes of constant work: O(log(M * N)).
O(1)
The code keeps m, n, lo, hi, mid, row, col and val, whatever the matrix size, and returns one boolean. It never builds the flat list, so the extra space is O(1).
T(M·N) = T(M·N / 2) + O(1) = O(log(M * N))
Derivation Progression
O(1)
m, n = len(matrix), len(matrix[0]) and lo = 0; hi = m * n are constant work.
at most floor(log2(M·N)) + 1 passes
Each pass of while lo < hi narrows the candidate range with hi = mid or lo = mid + 1.
O(1) per pass
matrix[i // n][i % n], one cell read and one comparison, whatever M and N are.
O(log(M * N))
Constant work times a logarithmic number of passes.
Variable Definitions
Number of rows, len(matrix)
Number of columns, len(matrix[0])
The flat index being probed, a position in the row-by-row list
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): m, n, lo, hi, mid, row, col, val; no flattened copy
O(1): one boolean
Boundary Best / Worst Cases
: the template searches for the boundary before the equality check
: target is absent or found on the last probe
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every row's first value is bigger than the previous row's last value" and "must run in O(log(m * n)) time". The grid is one sorted list stored row by row, so the move is Global Matrix Bisection: Lower Bound on the flat index, using matrix[i // n][i % n] >= target, then one guarded equality check.
, so at most cells and about 14 probes. Budget: time, space. For grids with more than cells the flat index needs a 64-bit integer in Java, C# or C++.
Copying the grid into one list first costs time and memory and throws the log bound away. When each row is a separate page or block in storage, every probe may be a separate read, so the probe count, about , is what the design must keep small; fetch only the probed rows.