Converging Pointers already teaches that two pointers can start at two ends and discard one end per comparison. This card adds only the grid version: the two pointers are row and col, and each comparison discards a whole row or a whole column.

In Search a 2D Matrix II (LC 240), every row increases from left to right, and every column increases from top to bottom. The top-right value is the largest in its row, and it is the smallest in its column.

If val > target, the values below val in the same column are larger than val. None of them can equal target, so col -= 1 drops the column. If val < target, the values to the left of val in the same row are smaller than val. None of them can equal target, so row += 1 drops the row.

After a drop, the cells that are left form a smaller rectangle. Its top-right cell has the same property, so the next comparison works in the same way.

The board shows the matrix of Example 1 of Search a 2D Matrix II (LC 240). A dot marks a cell in a row or column that an earlier step dropped. The tag val marks the cell that is compared.

The walk starts at 15. It is smaller than 23, so row += 1. The values 19 and 22 are also smaller, so row becomes 3. Then 24 is larger than 23, so col becomes 3.

The value 17 is smaller, so row becomes 4. The value 26 is larger, so col becomes 2. The value at row 4 and column 2 is 23, which equals target, so the function returns True.

The walk read 7 cells of a 25-cell matrix. If target is 20, which is not in the matrix, the walk reads 9 cells. It ends when row passes the last row. For the same matrix, target = 5 returns True and target = 20 returns False.

The start corner must be the top-right or the bottom-left corner. At the top-left corner, moving right and moving down both lead to larger values. In the trace, 1 < 23 does not say whether 23 is to the right or below. A top-left walk that moves right when val < target and down otherwise returns False for target = 5 on the traced matrix, although 5 is in it.

At the top-right corner, the two moves lead to different directions of change: left is smaller and down is larger. This is why each comparison has exactly one safe drop.

The loop condition is row < len(matrix) and col >= 0. Column 0 is a real column, so col > 0 would end the walk before it reads column 0. A target that is only in column 0, such as 18 in the trace, would be reported missing.

No comparison removes half of the cells, so this is not a binary search. Each comparison removes one line. Search a 2D Matrix (LC 74) is different: each row starts after the previous row ends, so the whole grid reads as one sorted list, and a binary search on that list is faster.

Each step moves row down or col left, and neither moves back. A matrix with M rows and N columns allows at most M + N - 1 reads, so the time is O(M + N). The extra space is O(1).

The same walk follows the border between small and large values in other sorted grids. Count Negative Numbers in a Sorted Matrix (LC 1351) walks the same way on a matrix sorted in decreasing order, and counts a whole column at once when a value is negative. Leftmost Column with at Least a One (LC 1428) walks along the border of the zeros and the ones.

Find Positive Integer Solution for a Given Equation (LC 1237) does not give a matrix. It gives a function that increases in both arguments. The two arguments play the roles of row and col.