{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Search a 2D Matrix – Solution & Complexity

Interview solutions
/
Search a 2D Matrix

Solution Walkthrough

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. 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. 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. 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. 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. 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

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)Kth Smallest Element in a Sorted Matrix solution (medium)Longest Increasing Subsequence solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?