74. Search a 2D Matrix - Explanation

Description

You are given an m x n 2-D integer array matrix and an integer target.

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

Return true if target exists within matrix or false otherwise.

Can you write a solution that runs in O(log(m * n)) time?

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

Recommended Time & Space Complexity

You should aim for a solution with O(log(m * n)) time and O(1) space, where m is the number of rows and n is the number of columns in the matrix.

Hint 1

A brute force solution would be to do a linear search on the matrix. This would be an O(m * n) solution. Can you think of a better way? Maybe an efficient searching algorithm, as the given matrix is sorted.

Hint 2

We can use binary search, which is particularly effective when we visualize a row as a range of numbers, [x, y] where x is the first cell and y is the last cell of a row. Using this representation, it becomes straightforward to check if the target value falls within the range. How can you use binary search to solve the problem?

Hint 3

We perform a binary search on the rows to identify the row in which the target value might fall. This operation takes O(logm) time, where m is the number of rows. Now, when we find the potential row, can you find the best way to search the target in that row? The sorted nature of each row is the hint.

Hint 4

Once we identify the potential row where the target might exist, we can perform a binary search on that row which acts as a one dimensional array. It takes O(logn) time, where n is the number of columns in the row.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

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.

Algorithm

Loop through every row in the matrix.
For each row, loop through every column.
If the current element equals the target, return True.
After scanning the entire matrix, return False if the target was not found.

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

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns of matrix.

2. Staircase Search

Intuition

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:

If the current value is greater than the target → move left (values decrease).
If 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.

Algorithm

Let r = 0 (first row) and c = n - 1 (last column).
While r is within bounds and c is within bounds:
- If matrix[r][c] == target, return True.
- If the value is greater than the target, move left (c -= 1).
- If the value is smaller, move down (r += 1).
If we exit the matrix, the target is not found → return False.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        r, c = 0, n - 1

        while r < m and c >= 0:
            if matrix[r][c] > target:
                c -= 1
            elif matrix[r][c] < target:
                r += 1
            else:
                return True
        return False

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns of matrix.

3. Binary Search

Intuition

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:

First search over the rows
We find the single row where the target could exist by comparing the target with the row’s first and last elements.
Binary search helps us quickly narrow down to that one row.
Then search inside that row
Once the correct row is found, we perform a normal binary search within that row to check if the target is present.

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

Algorithm

Set top = 0 and bot = ROWS - 1.
Binary search over the rows:
- Let row = (top + bot) // 2.
- If the target is greater than the last element of this row → move down (top = row + 1).
- If the target is smaller than the first element → move up (bot = row - 1).
- Otherwise → the target must be in this row; stop.
If no valid row is found, return False.
Now binary search within the identified row:
- Use standard binary search to look for the target.
Return True if found, otherwise False.

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) // 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) // 2
        l, r = 0, COLS - 1
        while l <= r:
            m = (l + r) // 2
            if target > matrix[row][m]:
                l = m + 1
            elif target < matrix[row][m]:
                r = m - 1
            else:
                return True
        return False

Time & Space Complexity

Time complexity: $O(\log m + \log n)$ (which reduces to $O(\log(m * n))$ )
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns of matrix.

4. Binary Search (One Pass)

Intuition

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:

row = m // COLS
col = m % COLS

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

Algorithm

Treat the matrix as a single sorted array of size ROWS * COLS.
Set l = 0 and r = ROWS * COLS - 1.
While l <= r:
- Compute the middle index m = (l + r) // 2.
- Convert m back to matrix coordinates:
  - row = m // COLS
  - col = m % COLS
- Compare matrix[row][col] with the target:
  - If equal → return True.
  - If the value is smaller → search the right half (l = m + 1).
  - If larger → search the left half (r = m - 1).
If the loop ends with no match, return False.

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:
            m = l + (r - l) // 2
            row, col = m // COLS, m % COLS
            if target > matrix[row][col]:
                l = m + 1
            elif target < matrix[row][col]:
                r = m - 1
            else:
                return True
        return False

Time & Space Complexity

Time complexity: $O(\log(m * n))$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns of matrix.