74. Search a 2D MatrixMedium

Search a 2D Matrix

MediumArrayBinary SearchMatrix·AmazonMicrosoft

You are given an m x n integer matrix matrix with the following two properties:

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

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input:matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output:true

Example 2:

Input:matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output:false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10000 <= matrix[i][j], target <= 10000

1. Brute Force

O(m * n) Time

🔍

Linear Scan

Time O(m * n)Space O(1)

The brute force approach simply checks every element in the matrix one by one.

Since the matrix is sorted but we're ignoring that structure, we just scan through all rows and all columns until we either find the target or finish searching.

1Loop through every row in the matrix.
2For each row, loop through every column.
3If the current element equals the target, return true.
4After scanning the entire matrix, return false if the target was not found.

2. Staircase Search

O(n + m) Time

🚶

Walk Down a Staircase

Time O(m + n)Space O(1)

Since each row is sorted left-to-right and each column is sorted top-to-bottom, we can search smartly instead of checking every cell.

Start at the top-right corner:

1If the current value is greater than the target → move left (values decrease).
2If it is smaller than the target → move down (values increase).

This works like walking down a staircase—each step eliminates an entire row or column. We keep moving until we either find the target or move out of bounds.

3. Binary Search

O(log m + log n) Time

🎯

Double Binary Search

Time O(log(m * n))Space O(1)

Because each row of the matrix is sorted, and the rows themselves are sorted by their first and last elements, we can apply binary search twice:

1First search over the rows to find the single row where the target could exist by comparing the target with the row's first and last elements.
2Then search inside that row with a normal binary search to check if the target is present.

This eliminates large portions of the matrix at each step and uses the sorted structure fully.

4. Binary Search (One Pass)

O(log(m * n)) Time

📏

Flatten to 1D Array

Time O(log(m * n))Space O(1)

Because the matrix is sorted row-wise and each row is sorted left-to-right, the entire matrix behaves like one big sorted array.

If we imagine flattening the matrix into a single list, the order of elements doesn't change.

This means we can run one binary search from index 0 to ROWS * COLS - 1. For any mid index m, we can map it back to the matrix using:

1row = m // COLS
2col = m % COLS

This lets us access the correct matrix element without actually flattening the matrix.

READYPress ▶ or step forward to begin.

✓

—

matrix (JSON array of arrays)

target

Executing Code

def searchMatrix(matrix, target):

    ROWS, COLS = len(matrix), len(matrix[0])

    l, r = 0, ROWS * COLS - 1

    while l <= r:

        m = (l + r) // 2

        row, col = m // COLS, m % COLS

        if matrix[row][col] > target:

            r = m - 1

        elif matrix[row][col] < target:

            l = m + 1

        else:

            return True

    return False

Common Pitfalls

Confusing Row vs Column Indexing

When converting a 1D index to 2D coordinates in the one-pass binary search approach, it is easy to mix up row = m // COLS and col = m % COLS. Using ROWS instead of COLS in these formulas will produce incorrect indices and lead to wrong answers or out-of-bounds errors.

Off-by-One Errors in Row Selection

In the two-pass binary search approach, after identifying the candidate row, forgetting to recalculate row = (top + bot) // 2 before the second binary search can cause you to search in the wrong row. Similarly, checking top <= bot incorrectly after the first loop can lead to false negatives.

Not Handling Empty Matrix

Failing to check if the matrix is empty or if any row is empty before accessing matrix[0] will cause runtime errors. Always validate that both ROWS > 0 and COLS > 0 before proceeding with the search.

Discussion

…

Loading comments…

LeetMotion