DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Search a 2D Matrix

mediumBinary search

Problem statement

You get an m x n integer matrix with two properties:

  • every row is sorted in ascending order, and
  • the first value of each row is greater than the last value of the row above it.

Given a target, return true if it appears anywhere in the matrix and false otherwise. Aim for O(log(m * n)) time.

Examples

Example 1

Input: matrix = [[2, 4, 7], [10, 13, 15], [18, 22, 30]], target = 13

Output: true

Explanation: 13 is in the middle row.

Example 2

Input: matrix = [[2, 4, 7], [10, 13, 15], [18, 22, 30]], target = 16

Output: false

Explanation: 16 would fall between 15 and 18, which are neighbours in reading order.

Hints

Approach

Treat the matrix as one sorted array of length m * n and binary-search it without copying anything.

  1. Set lo = 0 and hi = m * n - 1.
  2. While lo <= hi:
    • mid = lo + (hi - lo) // 2;
    • read the value at row mid // n, column mid % n;
    • compare it to the target and move lo or hi exactly as in ordinary binary search.
  3. Return false if the range empties.

The index conversion is the whole trick. It takes O(log(m·n)) comparisons.

ComplexityTime O(log(m·n))Space O(1)
Python
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
v = matrix[mid // n][mid % n]
if v == target:
return True
if v < target:
lo = mid + 1
else:
hi = mid - 1
return False

Follow-up questions

  • Now rows and columns are each sorted, but a row's first value may be smaller than the previous row's last value. Which approach still works?

Frequently asked questions

n is the number of columns, which is how many flat positions each row holds. Position k has k // n full rows before it and sits k % n cells into its own row. Using m breaks as soon as the matrix is not square.

Data split into fixed-size pages or shards behaves like this matrix: log files rotated at a fixed number of lines, or metrics stored in fixed-size blocks. Converting a global offset to (block, offset-within-block) with // and % is the same step.

That also runs in O(log m + log n), which equals O(log(m·n)). It is a valid answer; the flat-index version is shorter and has fewer boundary cases.