Search a 2D Matrix II
Search for a target in a matrix whose rows and columns are each sorted in ascending order.
Open on LeetCode ↗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.
Start at the top-right corner. From there, moving left strictly decreases the value and moving down strictly increases it — so every comparison eliminates a full row or column. Unlike Search a 2D Matrix, the rows aren't globally ordered, so flattening doesn't work.
Approach
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.
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.
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.
Solution & live demo
Common pitfalls
Starting at the top-left corner
r, c = 0, 0
r, c = 0, len(matrix[0]) - 1
At the top-left both directions increase, so a value below the target gives no information about which way to go. Only the corners where the two moves disagree — top-right or bottom-left — support the elimination.
Treating it as one sorted array
lo, hi = 0, rows * cols - 1 v = matrix[mid // cols][mid % cols]
while r < len(matrix) and c >= 0:
That's the Search a 2D Matrix I solution, which relies on each row starting after the previous ends. Here rows only share column-wise ordering, so the flattened sequence isn't sorted and the binary search reports false negatives.
Getting the move directions backwards
if val > target: r += 1 else: c -= 1
if val > target: c -= 1 else: r += 1
Too large means every value below is also too large, so the column must go. Swapping the moves walks off the matrix without ever narrowing the search.
Edge cases
Return False before dereferencing matrix[0].
The first comparison sends the pointer left repeatedly until the column index falls below 0.
The pointer walks straight down until the row index reaches the number of rows.
Degenerates to a linear scan in the one available direction, which is still correct and still O(m + n).