Search a 2D Matrix — Flat-Index Binary Search [LC 74, Amazon, Microsoft]

Problem Statement#

Given an m x n integer matrix sorted row-by-row and with each row starting after the previous row ends (globally sorted), determine if a target value exists.

Constraints:

• m == matrix.length, n == matrix[0].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j] <= 10^4
• Matrix is sorted in non-decreasing order row by row, with each row's first element greater than the previous row's last

Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Why This Problem Matters#

LC 74 is a favourite problem at Amazon and Microsoft because it tests whether candidates can recognise when a 2D structure reduces to a 1D problem. Most candidates see a matrix and reach for a 2D loop or a nested binary search. The clean solution treats the entire m x n matrix as a single sorted array of m * n elements and runs one standard binary search — the only novelty is the coordinate mapping.

This flat-index insight also appears in matrix serialisation problems, 2D heap verification, and cache-friendly array traversal. Interviewers use LC 74 to probe spatial reasoning: can you mentally "unroll" a 2D grid into a 1D sequence and back?

The follow-up, LC 240 (Search a 2D Matrix II), has a weaker guarantee (sorted rows and columns, but no global ordering) and requires an entirely different algorithm — the staircase approach. Knowing which guarantee you have and which algorithm to apply is itself a strong interview signal.

The Core Insight#

The matrix has a globally sorted order: element at (r, c) comes before element at (r, c+1), and the last element of row r comes before the first element of row r+1. This makes the entire matrix equivalent to a sorted 1D array of length m * n.

Map a flat index mid to 2D coordinates:

• row = mid // n
• col = mid % n

Run standard binary search on [0, m * n - 1]. At each step, compute (row, col) from mid and compare matrix[row][col] to the target.

Visual Dry Run#

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

n = 4 columns. Flat indices: 0..11.

Solution (Optimal)#

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 - lo) // 2
            row, col = mid // n, mid % n
            val = matrix[row][col]
 
            if val == target:
                return True
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1
 
        return False

var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length;
    let lo = 0, hi = m * n - 1;
 
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        const row = Math.floor(mid / n);
        const col = mid % n;
        const val = matrix[row][col];
 
        if (val === target) return true;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
 
    return false;
};

Time: O(log(m * n)) — single binary search over all elements Space: O(1) — only index variables

Common Mistakes#

• Using a nested binary search (find row first, then column) — works but is O(log m + log n) and adds unnecessary complexity.
• Forgetting to use integer division for row — in Python 3, // is required; in JavaScript, use Math.floor.
• Applying this to LC 240 (different matrix guarantee) — LC 240 is only row-sorted and column-sorted, not globally sorted. The flat-index trick breaks there; use the staircase approach.
• Setting hi = m * n instead of m * n - 1 — this off-by-one causes an out-of-bounds access when lo == hi == m * n.
• Not checking if the matrix is empty before computing dimensions.

Interview Tips#

• State the global-sort guarantee first: "each row ends before the next begins, making the whole matrix one sorted sequence."
• Write the coordinate mapping formula immediately after setting up lo and hi — it shows you have a clear mental model.
• Distinguish LC 74 from LC 240 proactively — interviewers often ask which algorithm you would use for the weaker guarantee.
• For overflow: m * n can reach 10^4, well within 32-bit range. No overflow concern here.

Follow-up Questions#

• LC 240 (Search a 2D Matrix II): Only row-sorted and column-sorted. Use staircase: start at top-right, move left if too large, down if too small. O(m + n).
• Return the 2D coordinates instead of a boolean: Replace return True with return (row, col) and return False with return (-1, -1).
• Binary search on row first, then column: Find the last row where matrix[r][0] <= target (O(log m)), then binary search within that row (O(log n)). Same asymptotic but two passes.
• What if the matrix is enormous and stored on disk? The flat-index mapping still applies logically; each "read" corresponds to fetching a specific element by position.
• What if m * n overflows a 32-bit integer? For m, n <= 100, max product is 10,000 — no issue. For larger matrices in other contexts, use 64-bit integers.

Key Takeaways#

• LC 74 reduces a 2D search problem to a 1D binary search using the flat-index mapping: row = mid // n, col = mid % n.
• The globally sorted guarantee (each row's last element precedes the next row's first) is the essential prerequisite for this approach.
• Standard while lo <= hi binary search with lo = mid + 1 and hi = mid - 1 applies directly once the mapping is established.
• The approach is O(log(m * n)) — a single binary search over all elements, not a nested one.
• LC 240 has a weaker guarantee and requires the O(m + n) staircase algorithm — always clarify which matrix property applies in an interview.
• This flat-index trick generalises to any multi-dimensional array stored in row-major order where global sorted order is preserved.
• Amazon and Microsoft ask this problem specifically to test spatial reasoning and the ability to reduce higher-dimensional problems to simpler ones.