Katkat
Back

Compute nearest gate distance in grid

RobinhoodSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform multi-source Breadth-First Search (BFS) on a grid to find the shortest distance from every cell to the nearest target (gate).

Problem Statement

You are given an m x n 2D grid initialized with three types of values:

  • -1: A wall or an obstacle.
  • 0: A gate.
  • INF: Represented by a large integer (e.g., 2^31 - 1), representing an empty room.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, the room should remain INF.

Function Signature

def nearest_gate(grid: List[List[int]]) -> None:
    """
    Modifies grid in-place.
    """

Examples

Example 1: Input:

[[INF, -1,  0,  INF],
 [INF, INF, INF, -1],
 [INF, -1,  INF, -1],
 [0,   -1,  INF, INF]]

Output:

[[3, -1, 0, 1],
 [2, 2, 1, -1],
 [1, -1, 2, -1],
 [0, -1, 3, 4]]

Constraints

  • m == grid.length, n == grid[0].length
  • 1 <= m, n <= 250
  • grid[i][j] is -1, 0, or 2^31 - 1

Edge Cases

  • Grids with no gates.
  • Grids with no empty rooms.
  • Grids completely enclosed by walls.
  • Single-cell grids.

Hints

Hint 1

Instead of starting a BFS from every room, consider starting a multi-source BFS starting simultaneously from all gates.

Hint 2

Initialize your queue with the coordinates of all cells containing '0' and mark them as visited implicitly by updating their distance.

Hint 3

For each cell popped from the queue, explore its four neighbors; if a neighbor's value is greater than the current cell's distance + 1, update it and push it to the queue.

Follow-up questions

  • What is the time and space complexity of your solution, and why is this approach more efficient than running a BFS from each empty room individually?
  • How would you modify your algorithm if gates had different 'weights' or 'capacities', such that distance is calculated by the sum of weights along the path?
  • If the grid were extremely sparse (very few gates relative to rooms), would a different graph traversal algorithm like Dijkstra's offer any benefit?