Each row of the grid is sorted left-to-right and each column is sorted top-to-bottom.
Return true if target appears in the grid.
searchGrid(grid, target)
Input format: rows | target, where rows are separated by ; and the values in
each row are space-separated. For example 1 4 7;2 5 8;3 6 9 | 5.
[[1,4,7],[2,5,8],[3,6,9]], target=5 // → true
[[1,4,7],[2,5,8],[3,6,9]], target=0 // → false
Each row is sorted left to right, each column top to bottom — richer structure than a single sorted list, but there's no single global ordering across two dimensions, so plain binary search on the whole grid doesn't directly apply. The challenge is finding a starting position where every comparison gives an unambiguous direction.
The top-left corner is the smallest value in the grid — if it's less than the target, both "move right" and "move down" lead to larger values, so you learn nothing about direction. Top-left and bottom-right are the two corners where increasing rows and increasing columns push the value the same way, so a comparison there only rules out that one cell.
The top-right corner is the largest value in its row and the smallest in its column — simultaneously. That dual property makes every comparison decisive:
Each comparison eliminates a whole row or column, never just one cell.
Every step moves left (one fewer column) or down (one fewer row), stopping on a match or falling off the grid. Since you can move left at most "columns" times and down at most "rows" times, total steps are bounded by rows plus columns — far better than checking every cell (rows × columns). This staircase walk is the two-dimensional version of binary search's elimination principle: each comparison must rule out a large chunk of the remaining space, never just one element.
def search_grid(grid, target):
if len(grid) == 0 or len(grid[0]) == 0:
return False
r = 0
c = len(grid[0]) - 1
while r < len(grid) and c >= 0:
if grid[r][c] == target:
return True
if grid[r][c] > target:
c -= 1
else:
r += 1
return False
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.