We have a 2D matrix with a special structure: every row is sorted left to right, and every column is sorted top to bottom. We need to determine whether a given target value exists anywhere in this matrix.

This is different from LeetCode #74 (Search a 2D Matrix), where the first element of each row is greater than the last element of the previous row, effectively making the entire matrix one long sorted array. Here, that property does not hold. For instance, the first element of row 2 could be smaller than the last element of row 1. So we can't just flatten the matrix and do a single binary search.

The sorted-row and sorted-column properties give us a partial ordering across the matrix. The goal is to exploit that ordering so we avoid checking every cell.

Key Constraints:

Intuition

Ignore the sorted properties and scan every cell. Loop through every row and column, compare each value against the target, and return true on the first match. If the scan reaches the end without a match, return false.

This is correct and a useful baseline, but it does no better than searching an unsorted matrix. The next approaches use the ordering to skip work.

Algorithm

Visualization and Code

This approach works but ignores the sorted structure entirely. Since each row is sorted, we can use binary search within each row to skip cells much faster.

Intuition

Each row is individually sorted in ascending order, so we can binary search a single row in O(log n) time instead of scanning it in O(n). Iterate through each row, run binary search on it, and return true if any row contains the target. If no row contains it, the target is absent.

One optimization avoids wasted searches. Because each row is sorted, its first element is the row minimum and its last element is the row maximum. If the target is smaller than the first element or larger than the last, it cannot be in that row, so we skip it before binary searching.

Algorithm

Visualization and Code

This uses the row-sorted property but ignores the column-sorted property. The next approach uses both at once, letting a single comparison eliminate an entire row or column.

Intuition

The starting position determines whether comparisons are useful. From the top-left corner, both moving right and moving down increase the value, so a cell smaller than the target gives no information about which direction to go. The bottom-right corner has the mirror problem: both directions decrease.

The top-right corner avoids this. From position (0, n-1):

Every comparison now points one way. If the current value is larger than the target, move left to eliminate the current column. If it is smaller, move down to eliminate the current row. Each step removes one row or one column, so the search finishes in at most m + n steps.

Algorithm

Visualization and Code