0365MediumArrayBreadth-First SearchMatrix

Steps to the Nearest Dock

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A warehouse floor is stored as the m x n grid rooms. Every cell holds one of three values:

-1 means a rack stands there and nothing can pass through it.
0 means a charging dock sits there.
2147483647 means open aisle.

A trolley moves between cells that share an edge, never diagonally and never into a rack. One move counts as one step.

Fill in every open aisle cell with the number of steps on a shortest walk from that cell to any charging dock. If no dock can be walked to from a cell, leave that cell holding 2147483647. Rack cells and dock cells keep the values they already hold.

Rewrite rooms in place rather than building a new grid, and return the same grid you were handed so the result can be read back.

Examples

Example 1

Input: rooms = [[0,2147483647,2147483647,0]]
Output: [[0, 1, 1, 0]]

The second cell is one step from the dock on its left and the third cell is one step from the dock on its right.

Example 2

Input: rooms = [[2147483647,2147483647,2147483647],[2147483647,-1,2147483647],[2147483647,2147483647,0]]
Output: [[4, 3, 2], [3, -1, 1], [2, 1, 0]]

The only dock is the bottom-right cell and a rack sits in the centre. Reading the grid back, the top-left cell ends up four steps away and the cell above the dock one step away.

Example 3

Input: rooms = [[0,-1,2147483647]]
Output: [[0, -1, 2147483647]]

The rack cuts the third cell off from the dock, so that cell keeps 2147483647.

Example 4

Input: rooms = [[2147483647,-1]]
Output: [[2147483647, -1]]

There is no dock anywhere on this floor, so the open cell keeps 2147483647 and the rack is left alone.

Constraints

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2147483647.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def walls_and_gates(rooms: list[list[int]]) -> list[list[int]]:

Java

public int[][] wallsAndGates(int[][] rooms)

The intended approach

Time O(m * n)Space O(m * n) for the queue

Push every dock into one queue before expanding anything, then run a single breadth-first sweep. Because all docks start at step 0 together, the first time the sweep touches an open cell it has arrived along a shortest walk from the closest dock, so writing the step count straight into the cell is safe and also marks it as visited. Cells the sweep never reaches keep 2147483647, which covers both a floor with no dock and pockets fenced off by racks.

Pythonentry point: walls_and_gates

from collections import deque

OPEN = 2147483647


def walls_and_gates(rooms):
    # Every dock enters the queue at once, so a cell is reached first along a
    # shortest walk and each cell is written at most once.
    # Time O(m * n), space O(m * n) for the queue in the worst case.
    m, n = len(rooms), len(rooms[0])
    queue = deque()
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                queue.append((i, j))
    while queue:
        i, j = queue.popleft()
        step = rooms[i][j] + 1
        for a, b in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= a < m and 0 <= b < n and rooms[a][b] == OPEN:
                rooms[a][b] = step
                queue.append((a, b))
    return rooms

The obvious version

Take each open cell on its own and breadth-first search outward from it until a dock turns up, recording that distance; write all the collected distances back at the end so no search sees a half-updated grid.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

from collections import deque

OPEN = 2147483647


def bf_walls_and_gates(rooms):
    m, n = len(rooms), len(rooms[0])
    targets = [(i, j) for i in range(m) for j in range(n) if rooms[i][j] == OPEN]
    answers = []
    for si, sj in targets:
        seen = {(si, sj)}
        queue = deque([(si, sj, 0)])
        found = OPEN
        while queue:
            i, j, d = queue.popleft()
            if rooms[i][j] == 0:
                found = d
                break
            for a, b in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= a < m and 0 <= b < n and (a, b) not in seen:
                    if rooms[a][b] == -1:
                        continue
                    seen.add((a, b))
                    queue.append((a, b, d + 1))
        answers.append(found)
    for (i, j), value in zip(targets, answers):
        rooms[i][j] = value
    return rooms

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in