Problem Overview

We are given an m x n matrix and a target value. The matrix has two important properties:

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

Because of these rules, the entire matrix behaves like one sorted array.

We need to return True if the target exists in the matrix, otherwise return False.

The expected time complexity is:

O(log(m * n))

Brute Force Approach

The simplest solution is to check every element in the matrix.

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == target:
                    return True
        return False

Explanation

We loop through every row and every column. If we find the target, we return True. If we finish checking all values and do not find it, we return False.

Time Complexity

O(m * n)

Space Complexity

O(1)

This works, but it does not satisfy the required O(log(m * n)) time complexity.

Better Approach: Binary Search Twice

Since each row is sorted and the rows are also ordered, we can first find the correct row, then binary search inside that row.

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        top, bot = 0, ROWS - 1

        while top <= bot:
            row = top + (bot - top) // 2

            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bot = row - 1
            else:
                break

        if not (top <= bot):
            return False

        row = top + (bot - top) // 2
        l, r = 0, COLS - 1

        while l <= r:
            mid = l + (r - l) // 2

            if matrix[row][mid] > target:
                r = mid - 1
            elif matrix[row][mid] < target:
                l = mid + 1
            else:
                return True

        return False

Explanation

First, we binary search over the rows.

For each middle row, we check:

matrix[row][0]
matrix[row][-1]

If the target is greater than the last value in the row, the target must be in a lower row.

If the target is smaller than the first value in the row, the target must be in an upper row.

Otherwise, the target could be inside this row.

After finding the possible row, we run a normal binary search inside that row.

Time Complexity

O(log m + log n)

Space Complexity

O(1)

This is efficient and works well.

Optimal Approach: Treat the Matrix Like a Sorted Array

Because of the matrix properties, we can imagine the 2D matrix as one sorted 1D array.

For example:

[
  [1, 2, 4, 8],
  [10, 11, 12, 13],
  [14, 20, 30, 40]
]

Can be viewed as:

[1, 2, 4, 8, 10, 11, 12, 13, 14, 20, 30, 40]

Instead of actually creating a new array, we can use math to convert a 1D index into a 2D position.

row = mid // COLS
col = mid % COLS

Code

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        l, r = 0, ROWS * COLS - 1

        while l <= r:
            mid = l + (r - l) // 2
            row, col = mid // COLS, mid % COLS

            if target > matrix[row][col]:
                l = mid + 1
            elif target < matrix[row][col]:
                r = mid - 1
            else:
                return True

        return False

Explanation

We set the search range from:

0

to:

ROWS * COLS - 1

This represents the index range of the imaginary sorted 1D array.

For every mid, we convert it back to a matrix position:

row = mid // COLS
col = mid % COLS

Then we compare:

matrix[row][col]

with the target.

If the current value is smaller than the target, we search the right half.

If the current value is greater than the target, we search the left half.

If it matches, we return True.

Time Complexity

O(log(m * n))

Space Complexity

O(1)

Why This Works

The key observation is that the matrix is globally sorted.

Because:

first element of each row > last element of previous row

there is no overlap between rows. So the matrix acts exactly like one sorted list.

That means binary search can be applied directly across all elements.

Final Thoughts

The brute force approach is easy to understand, but it checks every element.

The two-step binary search improves the solution by first finding the row and then searching inside it.

The cleanest and most optimal solution is to treat the matrix as a virtual 1D sorted array and run one binary search over it.

This gives us the required:

O(log(m * n))

time complexity with constant space.