Search a 2D Matrix: flattening the matrix index into one binary search

The previous article in this series set up the binary search template: left, right, mid, shrink the window by one on each side. LeetCode 74 puts the same template in a 2D context and asks you to notice that the 2D structure is a disguise. Strip it away and you have one binary search, not two.

What the constraints force

The problem guarantees two things. First, each row is sorted in non-decreasing order. Second — and this is the part that matters — the first element of each row is strictly greater than the last element of the previous row. That second guarantee is what changes everything.

Together these two properties mean there are no gaps across row boundaries: row i's last element is always smaller than row i+1's first element. Read the matrix left-to-right, top-to-bottom:

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

Unrolled: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. Fully sorted. Not a single element out of order, regardless of where you cross a row boundary. The 2D layout is cosmetic.

The required complexity is O(log(m _ n)). The constraints say m and n are at most 100, so m _ n tops out at 10,000. Even a linear scan would pass on inputs this small, but the problem explicitly says O(log(m _ n)) — ruling out brute force as a final answer and pointing directly at binary search over all m _ n elements.

The pattern here is "virtual 1D array": a 2D structure that can be treated as 1D because the ordering is perfectly preserved across dimension boundaries. Binary search on the flattened index, then unmap. That's the whole mental model.

Brute force: O(m * n)

Walk every cell. It's the obvious starting point and the one that ignores everything interesting about the matrix structure.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        for row in matrix:
            for num in row:
                if num == target:
                    return True
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        foreach (int[] row in matrix)
            foreach (int num in row)
                if (num == target) return true;
        return false;
    }
}

O(m _ n) time, O(1) space. Fails the requirement. Worth writing once to see exactly what you're throwing away — every cell visited in order, with zero early termination based on the sorted structure. You could improve it slightly by breaking the inner loop as soon as num > target, since each row is sorted. But that's still O(m _ n) worst case. Not good enough.

Two-step binary search: O(log m + log n)

A more natural intermediate step: binary search for the candidate row first, then binary search within that row. You pick the row by checking whether the target falls between row[0] and row[-1]. If target < row[0], the row is too far down. If target > row[-1], the row is too far up.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        top, bottom = 0, m - 1
 
        while top <= bottom:
            mid_row = (top + bottom) // 2
            if target < matrix[mid_row][0]:
                bottom = mid_row - 1
            elif target > matrix[mid_row][n - 1]:
                top = mid_row + 1
            else:
                # target falls in this row's range, now search within it
                left, right = 0, n - 1
                while left <= right:
                    mid_col = (left + right) // 2
                    if matrix[mid_row][mid_col] == target:
                        return True
                    elif matrix[mid_row][mid_col] < target:
                        left = mid_col + 1
                    else:
                        right = mid_col - 1
                return False
 
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int top = 0, bottom = m - 1;
 
        while (top <= bottom) {
            int midRow = top + (bottom - top) / 2;
            if (target < matrix[midRow][0])
                bottom = midRow - 1;
            else if (target > matrix[midRow][n - 1])
                top = midRow + 1;
            else {
                int left = 0, right = n - 1;
                while (left <= right) {
                    int midCol = left + (right - left) / 2;
                    if (matrix[midRow][midCol] == target) return true;
                    else if (matrix[midRow][midCol] < target) left = midCol + 1;
                    else right = midCol - 1;
                }
                return false;
            }
        }
        return false;
    }
}

O(log m + log n) time, O(1) space. Mathematically this equals O(log(m _ n)) — log m + log n = log(m _ n) by the logarithm product rule. So complexity-wise this is fine. But you're writing two separate binary searches with a conditional branch connecting them. It works. It's just doing more than necessary.

The first binary search finds the row. The second finds the column. Two separate problems where there's really only one.

The optimal move: flatten to a virtual 1D array

The cleanest solution skips the row-finding step entirely. Since the full matrix reads as a sorted 1D sequence, treat it as one. Set left = 0, right = m * n - 1, and run a standard binary search. The only extra work: convert mid back to a 2D coordinate to read the actual value.

The mapping is two lines:

row = mid // n
col = mid % n

mid // n is integer division by the number of columns — that's how many full rows fit before index mid. mid % n is the remainder — the position within that row. The reverse direction: index = row * n + col. One coordinate system, two representations.

The decision flow looks like this:

Now trace target = 3 on the 3x4 matrix, step by step:

Virtual array: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Indices:         0  1  2  3   4   5   6   7   8   9  10  11

Step 1: left=0, right=11  -> mid=5  -> row=5//4=1, col=5%4=1 -> matrix[1][1]=11
        11 > 3  -> right = 4

Step 2: left=0, right=4   -> mid=2  -> row=2//4=0, col=2%4=2 -> matrix[0][2]=5
        5 > 3   -> right = 1

Step 3: left=0, right=1   -> mid=0  -> row=0//4=0, col=0%4=0 -> matrix[0][0]=1
        1 < 3   -> left = 1

Step 4: left=1, right=1   -> mid=1  -> row=1//4=0, col=1%4=1 -> matrix[0][1]=3
        3 == 3  -> return True

Four iterations. No row-finding step. No nested loop. The index arithmetic does all the routing.

Now trace target = 13 (the "not found" case):

Step 1: left=0,  right=11 -> mid=5  -> matrix[1][1]=11  -> 11<13 -> left=6
Step 2: left=6,  right=11 -> mid=8  -> matrix[2][0]=23  -> 23>13 -> right=7
Step 3: left=6,  right=7  -> mid=6  -> matrix[1][2]=16  -> 16>13 -> right=5
Step 4: left=6,  right=5  -> left > right -> exit loop

left > right — loop exits clean, return False.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
 
        while left <= right:
            mid = (left + right) // 2
            row, col = mid // n, mid % n
            val = matrix[row][col]
 
            if val == target:
                return True
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
 
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int left = 0, right = m * n - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;
            int val = matrix[row][col];
 
            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
 
        return false;
    }
}

O(log(m * n)) time, O(1) space. One pass, no branching on which row to enter. This is the version I'd ship.

Complexity comparison

The formula to get right

The index conversion trips people up exactly once. The rule: row = mid // n, col = mid % n — divide by the number of columns, not the number of rows. Easy to flip.

Think about it concretely. If you have 4 columns and you're at virtual index 9: row = 9 // 4 = 2 (the third row, zero-indexed), col = 9 % 4 = 1. Verify: in the example matrix, matrix[2][1] = 30, and virtual index 9 holds 30. The formula works because each row holds exactly n elements, so every n elements you advance, you move one row down.

The C# version uses left + (right - left) / 2 instead of (left + right) / 2 to avoid integer overflow when left and right are large. On LeetCode's constraints (m, n <= 100, so right tops out at 9999) this doesn't matter in practice. But it's the right habit to carry into problems where indices are bigger.

Edge cases worth knowing

1x1 matrix — [[5]], target = 5 or target = 3. left = right = 0, single iteration. The code handles both without any special case: target found returns True immediately; target not found exits on left > right after one shrink.

Target below matrix minimum — target is smaller than matrix[0][0]. The first mid comparison is larger than target, so right shrinks. After a few steps left > right and the loop exits cleanly. No special handling needed because the binary search invariant naturally excludes the entire range.

Target above matrix maximum — target is larger than matrix[m-1][n-1]. Symmetrically, left grows past right. Same clean exit.

Single-row matrix — a 1x4 matrix has n = 4, so mid // 4 = 0 for all mid values in [0, 3]. You always stay in row 0. The formula works without any adjustment.

Single-column matrix — a 4x1 matrix has n = 1, so mid // 1 = mid and mid % 1 = 0. You always land in column 0. Same story.

Empty matrix guard — the problem constraints say 1 <= m, n <= 100, so an empty matrix cannot appear. The if not matrix or not matrix[0] check in Python (or the null/length check in C#) is defensive code against callers that don't respect the constraints. Worth keeping; costs nothing.

What this approach does not work for

LeetCode 240 — Search a 2D Matrix II — has a superficially similar setup but drops the guarantee that each row's first element exceeds the previous row's last. Without that property, the matrix does not read as a sorted 1D sequence when unrolled. You cannot flatten and binary search. You need a different approach entirely — the staircase search starting from the top-right or bottom-left corner, which runs in O(m + n).

The guarantee in LeetCode 74 is the one that makes the flattening valid. When you see a sorted-matrix problem, check explicitly: if "first element of row i+1 > last element of row i" is stated, flatten and run one binary search. If not, you're in LeetCode 240 territory and the algorithm changes completely.

Where this sits in the series

The core binary search template appeared in the previous article. This problem uses exactly that template — the only addition is the two-line coordinate mapping. It is a good place to see that binary search is not tied to 1D arrays; it's tied to sorted order and the ability to halve the search space at each step. The 2D wrapper here is incidental.

The next problems in the series (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array) are harder because the sorted order is disrupted. You can no longer compare mid to target and know which half is clean. The invariant you maintain becomes more subtle.

Related problems

• LeetCode 240 — Search a 2D Matrix II: Same surface structure, different guarantees. Rows and columns are individually sorted, but there is no cross-row ordering. The flattening trick breaks here; use staircase search instead.
• LeetCode 33 — Search in Rotated Sorted Array: Binary search on a sorted array that's been cut and rearranged. The invariant you maintain is different — at each step you identify which half is still contiguously sorted.
• LeetCode 153 — Find Minimum in Rotated Sorted Array: Closely related to 33. Binary search where you're hunting the rotation pivot, not a specific target value.
• LeetCode 378 — Kth Smallest Element in a Sorted Matrix: Binary search on value rather than index, in a matrix sorted by rows and columns independently. A different shape but the same "think creatively about what you're searching over" mindset.