Katkat
Back

Compute distance to nearest taxi in grid

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently compute shortest path distances from multiple sources to all reachable grid cells using multi-source Breadth-First Search (BFS).

Problem: Nearest Taxi Distance

You are given an m x n grid represented as a 2D integer array grid where:

  • 0 represents an empty road cell.
  • 1 represents a taxi.

Your task is to update the grid so that each empty cell contains the distance to the nearest taxi. Distance is calculated based on the number of moves (up, down, left, or right) to reach the nearest taxi. You can assume there is at least one taxi in the grid.

Function Signature

def nearest_taxi(grid: List[List[int]]) -> List[List[int]]:

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500

Examples

Example 1: Input: grid = [[0, 0], [0, 1]] Output: [[2, 1], [1, 0]] Explanation: The cell at (0,0) is two steps away from the taxi at (1,1).

Example 2: Input: grid = [[1, 0], [0, 0]] Output: [[0, 1], [1, 2]]

Edge Cases

  • Grids with only one taxi.
  • Grids where all cells are already occupied by taxis.
  • Grids with a single row or single column.

Hints

Hint 1

A naive approach of running a BFS starting from every empty cell will be too slow; consider reversing the perspective.

Hint 2

If you start a BFS simultaneously from all taxi locations, the first time you visit an empty cell, you have found the shortest path to a taxi.

Hint 3

Initialize a queue with all coordinate pairs that contain a '1' and set the distance for these cells to 0, marking empty cells as unvisited (e.g., -1) to process them in layers.

Follow-up questions

  • How would you modify your solution if some road cells were blocked (e.g., represented by a -1) and could not be traversed?
  • What is the time and space complexity of your solution, and can you optimize the space complexity further?
  • If the grid dimensions were significantly larger than the number of taxis, would a different approach be more efficient?