Search A Sorted Grid
Problem
A grid has every row sorted increasing from left to right, and every column sorted increasing from top to bottom. Find a target value and report its position as a row and column pair, or report that it is absent. Scanning every cell is too slow for a large grid.
Examples
Input: grid = [[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16]], target = 5
Output: (1, 1)Input: same grid, target = 10
Output: None
Why: 10 sits between 9 and 11 but appears nowhereInput: grid = [[1]], target = 1
Output: (0, 0)
Why: edge case, a single cell gridHints
0 / 3
The grid is not one sorted sequence read left to right, so a plain binary search over all the cells does not apply.
Look for a starting cell where a comparison rules out a whole row or a whole column at once. The middle of the grid does not do that, but two of the corners do.
Start at the top-right cell. If it is larger than the target, nothing else in that column can match, so drop the column. If it is smaller, nothing else in that row can match, so drop the row. Repeat until the value is found or you walk off the grid.
Solution
The top-right cell is the largest in its row and the smallest in its column, so a single comparison against it always eliminates an entire line. Too large means the whole column is too large and the column is dropped, too small means the whole row is too small and the row is dropped, which is why the walk never has to backtrack. Each step removes one row or one column, so the search visits at most rows plus columns cells. Time is O(rows + cols), and space is O(1).
def find_value(g, target):
r, c = 0, len(g[0]) - 1 # start at the top-right corner
while r < len(g) and c >= 0:
v = g[r][c]
if v == target:
return (r, c)
if v > target:
c -= 1 # this column is all too large
else:
r += 1 # this row is all too small
return None
grid = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16]]
print(find_value(grid, 5)) # -> (1, 1)
print(find_value(grid, 16)) # -> (2, 3)
print(find_value(grid, 10)) # -> None
print(find_value([[1]], 1)) # -> (0, 0)Stuck on the idea rather than the code? Search a 2D Matrix covers it.