LeetCode 74: Search a 2D Matrix

Problem Restatement

We are given an m x n integer matrix and an integer target.

The matrix has two important properties:

1. Each row is sorted in non-decreasing order.
2. The first integer of each row is greater than the last integer of the previous row.

We need to return true if target exists in the matrix. Otherwise, return false.

The required time complexity is O(log(m * n)). The official constraints are 1 <= m, n <= 100 and -10^4 <= matrix[i][j], target <= 10^4.

Input and Output

Function shape:

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    ...

Examples

For:

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

The answer is:

True

The value 3 appears in the first row.

For:

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

The answer is:

False

The value 13 does not appear anywhere in the matrix.

First Thought: Scan Every Cell

The simplest solution is to check every cell.

class Solution:
    def searchMatrix(
        self,
        matrix: list[list[int]],
        target: int,
    ) -> bool:

        for row in matrix:
            for value in row:
                if value == target:
                    return True

        return False

This is correct, but it takes:

O(m * n)

The problem asks for O(log(m * n)), so we need binary search.

Key Insight

The matrix behaves like one sorted array if we read it row by row.

For example:

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

is logically the same as:

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

We do not need to build this flattened array.

We can binary search over virtual indices from:

0

to:

m * n - 1

For a virtual index mid, convert it back to matrix coordinates:

row = mid // n
col = mid % n

This works because each row has exactly n columns.

Index Mapping

Suppose:

n = 4

Then the virtual indices map like this:

The formula is:

row = index // n
col = index % n

So we can run normal binary search without changing the matrix.

Algorithm

Let:

m = len(matrix)
n = len(matrix[0])

Set:

left = 0
right = m * n - 1

While left <= right:

1. Compute mid.
2. Convert mid to (row, col).
3. Compare matrix[row][col] with target.
4. If equal, return True.
5. If smaller than target, search the right half.
6. If larger than target, search the left half.

If the loop ends, return False.

Correctness

Because each row is sorted and the first element of each row is greater than the last element of the previous row, reading the matrix from left to right and top to bottom gives one globally sorted sequence.

The algorithm performs binary search on this virtual sorted sequence. For every virtual index, the mapping row = index // n and col = index % n returns exactly the corresponding matrix cell in row-major order.

When the middle value is smaller than target, every value before it in the virtual sequence is also smaller, so the algorithm safely discards the left half. When the middle value is larger than target, every value after it is also larger, so the algorithm safely discards the right half.

If target exists, binary search eventually examines its virtual index and returns True. If the search range becomes empty, no possible position remains, so returning False is correct.

Complexity

Implementation

class Solution:
    def searchMatrix(
        self,
        matrix: list[list[int]],
        target: int,
    ) -> bool:

        m = len(matrix)
        n = len(matrix[0])

        left = 0
        right = m * n - 1

        while left <= right:
            mid = left + (right - left) // 2

            row = mid // n
            col = mid % n

            value = matrix[row][col]

            if value == target:
                return True

            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Code Explanation

First read the matrix size:

m = len(matrix)
n = len(matrix[0])

The virtual sorted array has this many elements:

m * n

Set the binary search boundaries:

left = 0
right = m * n - 1

Compute the middle index:

mid = left + (right - left) // 2

Convert the virtual index to matrix coordinates:

row = mid // n
col = mid % n

Read the matrix value:

value = matrix[row][col]

If it matches, return immediately:

if value == target:
    return True

If the value is too small, search the right half:

if value < target:
    left = mid + 1

Otherwise, search the left half:

else:
    right = mid - 1

If the loop ends, the target was not found:

return False

Testing

def run_tests():
    s = Solution()

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

    assert s.searchMatrix(matrix, 3) is True
    assert s.searchMatrix(matrix, 13) is False
    assert s.searchMatrix(matrix, 1) is True
    assert s.searchMatrix(matrix, 60) is True
    assert s.searchMatrix(matrix, 0) is False
    assert s.searchMatrix(matrix, 61) is False

    assert s.searchMatrix([[1]], 1) is True
    assert s.searchMatrix([[1]], 2) is False

    assert s.searchMatrix([[1, 3, 5]], 3) is True
    assert s.searchMatrix([[1], [3], [5]], 3) is True

    print("all tests passed")

run_tests()