{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Search a 2D Matrix – Solution & Complexity

Interview solutions
/
Search a 2D Matrix

Solution Walkthrough

  1. Step 1: Exploit both sorting rules

    • Every row is ascending, and each row starts after the previous row ends.
    • Concatenating the rows would produce one fully sorted sequence of m * n values.
    • That means a single binary search can cover the whole matrix.

  2. Step 2: Brute-force scan

    • Visit every cell and compare it with the target.
    • Correct but O(m * n), ignoring the sorted structure.
    def search_matrix(matrix, target):
    for row in matrix:
        for value in row:
            if value == target:
                return True
    return False

  3. Step 3: Flatten with index math

    • Number the cells 0 .. m*n - 1 in row-major order.
    • Flat index i maps to matrix[i // n][i % n].
    • Now run an ordinary binary search over 0 .. m*n - 1.

  4. Step 4: Single binary search

    • Keep lo/hi bounds over the flat index space.
    • Convert mid back to row/column with the division and modulo.
    def search_matrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

  5. Step 5: Dry run

    Trace matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 (cols = 4).

    lohimidcell [mid/4][mid%4]value vs 3
    0115[1][1] = 1111 > 3, hi = 4
    042[0][2] = 55 > 3, hi = 1
    010[0][0] = 11 < 3, lo = 1
    111[0][1] = 3match, return true

  6. Step 6: Final solution and complexity

    The flattened binary search runs in O(log(m * n)) time and O(1) extra space.

    def search_matrix(matrix: list[list[int]], target: int) -> bool:
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False
Learn the Binary Search pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Search a 2D Matrix online (run code in the browser)Binary Search solution (easy)Find Minimum in Rotated Sorted Array solution (medium)Koko Eating Bananas solution (medium)Kth Smallest Element in a Sorted Matrix solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?