LeetCode 240: Search a 2D Matrix II

Problem Restatement

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

The matrix has two sorted properties:

• Each row is sorted in ascending order from left to right.
• Each column is sorted in ascending order from top to bottom.

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

LeetCode examples include searching for 5, which returns true, and searching for 20, which returns false, in the same sorted matrix. The constraints allow 1 <= m, n <= 300, and values can be between -10^9 and 10^9.

Input and Output

Function shape:

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

Examples

Example 1:

Input:
matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target = 5

Output: true

The value 5 exists at row 1, column 1.

Example 2:

Input:
matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target = 20

Output: false

The value 20 does not exist in the matrix.

First Thought: Search Every Cell

The simplest method 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 ignores the sorted structure.

If the matrix has m rows and n columns, this takes:

O(m * n)

We can do better.

Key Insight

Start from the top-right corner.

At position (row, col), let:

value = matrix[row][col]

This position is special because:

• Everything to the left is smaller or equal.
• Everything below is larger or equal.

So we can eliminate one row or one column each step.

If value is too large

If:

value > target

then every value below it in the same column is also too large, because columns are sorted top to bottom.

So the target cannot be in this column.

Move left:

col -= 1

If value is too small

If:

value < target

then every value to the left in the same row is also too small, because rows are sorted left to right.

So the target cannot be in this row.

Move down:

row += 1

If value equals target

Return True.

Algorithm

1. Start at the top-right corner:
   • row = 0
   • col = n - 1
2. While row < m and col >= 0:
   • If matrix[row][col] == target, return True.
   • If matrix[row][col] > target, move left.
   • If matrix[row][col] < target, move down.
3. If we leave the matrix, return False.

Walkthrough

Use the matrix:

[
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Search for:

target = 5

Start at top-right:

Correctness

At every step, the algorithm is positioned at some cell (row, col).

If matrix[row][col] > target, then every value below it in column col is also greater than or equal to matrix[row][col], and therefore greater than target. So column col cannot contain the target in any remaining row. Moving left removes only impossible cells.

If matrix[row][col] < target, then every value to the left in row row is less than or equal to matrix[row][col], and therefore less than target. So row row cannot contain the target in any remaining column. Moving down removes only impossible cells.

If matrix[row][col] == target, the algorithm returns True, which is correct.

Each move eliminates one full row or one full column from the remaining search area. Since the algorithm only removes cells that cannot contain the target, it never discards a valid answer.

If the search exits the matrix, all possible rows or columns have been eliminated, so the target does not exist in the matrix. Returning False is correct.

Complexity

Here, m is the number of rows, and n is the number of columns.

Implementation

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

        row = 0
        col = n - 1

        while row < m and col >= 0:
            value = matrix[row][col]

            if value == target:
                return True

            if value > target:
                col -= 1
            else:
                row += 1

        return False

Code Explanation

Get the matrix size:

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

Start from the top-right corner:

row = 0
col = n - 1

Continue while the position is valid:

while row < m and col >= 0:

Check the current value:

value = matrix[row][col]

If it matches, return immediately:

if value == target:
    return True

If the value is too large, move left:

if value > target:
    col -= 1

Otherwise, the value is too small, so move down:

else:
    row += 1

If the loop ends, the target was not found:

return False

Alternative: Binary Search Each Row

Because each row is sorted, we can binary search every row.

This gives:

O(m log n)

That is valid, but the top-right method is usually better because it uses both row and column sorting.

Testing

def run_tests():
    s = Solution()

    matrix = [
        [1, 4, 7, 11, 15],
        [2, 5, 8, 12, 19],
        [3, 6, 9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30],
    ]

    assert s.searchMatrix(matrix, 5) is True
    assert s.searchMatrix(matrix, 20) 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]], 4) is False
    assert s.searchMatrix([[-5, -3, 0], [-2, 1, 4], [2, 6, 9]], -3) is True

    print("all tests passed")

run_tests()