Distances to a pickup point: A Sample Coding Interview Solution

The coding question

You're given a grid where -1 is a wall, 0 is the Dasher pickup gate, and a very large number is an empty room. Fill each room with its walking distance to the gate, moving up, down, left or right.

Ask a few questions first

Ask	What we'll assume
Can there be more than one gate?	Yes. Each room gets the distance to its nearest gate.
What if a room can't reach any gate?	Leave it as the large number.
What's the large number?	2147483647. We'll treat anything bigger than any real distance as empty.
Change the grid in place, or return a new one?	In place is fine. We'll also return it.

A couple of examples

Input	Output
[[INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [0, -1, INF, INF]]	[[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]
[[0, INF], [INF, -1]]	[[0, 1], [1, -1]]
[[INF, -1], [-1, 0]]	[[INF, -1], [-1, 0]] (the room is walled off)

Start with brute force

For every empty room, run a breadth-first search outward until you hit a gate. The first gate you reach is the closest one.

Cost: Each search can visit the whole grid, so with R rows and C columns it's O((R × C)²) time. A 1,000 by 1,000 grid would take about a trillion steps.

A better way

Flip it around. Instead of searching from every room to the gates, search from the gates out to the rooms.

Put every gate in the queue at the start, then run one breadth-first search. It spreads out in rings: first everything 1 step from any gate, then 2 steps, and so on. So the first time it reaches a room, that's the shortest distance to the nearest gate. Each room is filled once.

Scan the grid and add every gate to a queue.
Take a cell off the front of the queue.
For each of its four neighbours, if it's inside the grid and its value is bigger than this cell's distance plus 1, set it to that and add it to the queue.
Walls are -1 and gates are 0, so that check skips them on its own. Rooms already filled never get bigger values, so they're skipped too.
Keep going until the queue's empty.

The code

solution.pypython

from collections import deque

WALL, GATE = -1, 0


def fill_distances(grid):
    if not grid or not grid[0]:
        return grid
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == GATE:
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c] + 1:
                grid[nr][nc] = grid[r][c] + 1
                queue.append((nr, nc))
    return grid

	Cost	Why
Time	O(R × C)	Every cell goes into the queue at most once, and we check 4 neighbours each time
Space	O(R × C)	The queue can hold a big chunk of the grid, like when half the cells are gates

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

An empty grid, or one with no columns. Return it as it is.
No gates at all. The queue starts empty and every room stays at the large number.
A room walled off from every gate, like the third example. It never gets reached, so it stays as it is.
Two gates next to each other. Neither gets overwritten, because 0 isn't bigger than 1.
A single cell grid.

Common mistakes

Running a separate search from each gate. That's back to slow, and you also have to take the minimum across gates.
Using depth-first search. It doesn't reach cells in order of distance, so you'd fill a room with a longer path first and have to fix it later.
Forgetting to check grid bounds before reading a neighbour.
Using a Python list and pop(0) as the queue. That's O(n) per pop. Use deque.

Follow-up questions

What if some rooms take longer to walk through?

Then distances aren't just step counts, so plain breadth-first search won't work. Use Dijkstra's algorithm with a heap, starting with every gate in it at distance 0.

What if you also want to know which gate is closest?

Store the gate's ID along with the distance, and copy it from a cell to each neighbour you fill.

What if the grid's too big for memory?

Process it in tiles. Run the search inside each tile, then pass the distances along tile edges to neighbouring tiles and repeat until nothing changes.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on the input
5–10	Brute force: search from every room
10–20	Flip it: search from all gates at once
20–35	Write the code
35–40	Test it on the examples and edge cases
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by DoorDash.