Skip to content
AlgoVisual

Search in Sorted Grid

01 · Question

You're given a 2D grid of integers, grid, where each row is sorted (without duplicates), and the last value in each row is smaller than the first value in the following row. You are also given a target value, target. If the target is in the grid, return an array with its row and column indices. Otherwise, return [-1, -1].

Example 1:

  • Input: target = 4, grid = [[1, 2, 4, 5], [6, 7, 8, 9]]
  • Output: [0, 2]

Example 2:

  • Input: target = 3, grid = [[1, 2, 4, 5], [6, 7, 8, 9]]
  • Output: [-1, -1]

02 · Solution

Reference solution

1def searchInSortedGrid(grid: List[List[int]], target: int) -> List[int]:
2    if not grid: return [-1, -1]
3    rows, cols = len(grid), len(grid[0])
4    l, r = 0, rows * cols - 1
5    
6    while l <= r:
7        mid = (l + r) // 2
8        row, col = mid // cols, mid % cols
9        val = grid[row][col]
10        
11        if val == target:
12            return [row, col]
13        elif val < target:
14            l = mid + 1
15        else:
16            r = mid - 1
17            
18    return [-1, -1]
Previous
Race Overtaking
Next
Search in Huge Array