LeetCode #240 Medium

Search a 2D Matrix II

Search for a target in a matrix whose rows and columns are each sorted in ascending order.

arraymatrixbinary-searchdivide-and-conquer

02

Intuition

💡

Almost everyone starts the pointer at the top-left, because that is where you start everything. It cannot work, and the reason is worth internalising. From the top-left both legal moves, right and down, increase the value. So when the current cell is smaller than the target you learn nothing about which of the two directions to take, and when it is larger than the target you have no move at all that reduces the value. You are stuck with a search that cannot eliminate anything. Start instead at a corner where the two available directions disagree. The top-right is one: moving left strictly decreases and moving down strictly increases. Now every single comparison is decisive. If the cell is bigger than the target, it is the smallest element in its column, so the entire column is too big and you drop it. If it is smaller, it is the largest element still in play in its row, so the whole row is gone and you drop that. The invariant is that the target, if present, always lies in the rectangle below and to the left of your pointer, and each step shrinks that rectangle by a full row or column.

03

Approach

1

Pick a corner with conflicting directions

The top-left and bottom-right corners are useless because both their moves push the value the same way. The top-right and bottom-left are the useful ones. Take the top-right, at row 0 and column cols minus 1: it is the maximum of its row and the minimum of its column, which is exactly the tension that makes a comparison informative.

2

Let each comparison eliminate a whole line

If matrix[r][c] is greater than the target, then because the column is sorted downward every cell below is also greater, so column c is dead and you move left. If it is less than the target, then because the row is sorted rightward and everything right of c has already been discarded, no cell remaining in row r can match, so row r is dead and you move down. Equality ends the search.

3

Stop when the pointer walks off the board

The loop runs while r is in range and c is at least 0. Since every iteration either increments r or decrements c, the pointer takes at most rows plus cols steps before it exits, which gives O(m + n) without any binary search at all. Walking off the edge means every row and column was eliminated by a valid argument, so the target is genuinely absent.

04

Solution & live demo

python

▶1class Solution:
▶2    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
▶3        if not matrix or not matrix[0]:
▶4            return False
▶5        r, c = 0, len(matrix[0]) - 1
▶6        while r < len(matrix) and c >= 0:
▶7            val = matrix[r][c]
▶8            if val == target:
▶9                return True
▶10            if val > target:
▶11                c -= 1
▶12            else:
▶13                r += 1
▶14        return False

05

Edge cases

Empty matrix or empty first row

Return False before dereferencing matrix[0].

Target smaller than every element

The first comparison sends the pointer left repeatedly until the column index falls below 0.

Target larger than every element

The pointer walks straight down until the row index reaches the number of rows.

Single row or single column

Degenerates to a linear scan in the one available direction, which is still correct and still O(m + n).

06

Complexity

Time

O(m + n)

Space

O(1)

Each step removes an entire row or column, so the walk is bounded by rows plus columns rather than by log of the cell count.