Skip to content
Hello Python

Expand a Multi-Source Frontier

Practice ExerciseInterviewEasyMulti-source BFS

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement multi_source_distances(rows, columns, sources, blocked). Return a rows-by-columns matrix of shortest four-direction distances to any source. Blocked and unreachable cells are -1. sources and blocked contain [row, column] pairs.

Starter code

def multi_source_distances(rows, columns, sources, blocked):
    pass
Test cases

two-sources

{
  "args": [
    3,
    4,
    [
      [
        0,
        0
      ],
      [
        2,
        3
      ]
    ],
    []
  ]
}

Expected: [[0,1,2,2],[1,2,2,1],[2,2,1,0]]

blocked-cell

{
  "args": [
    2,
    3,
    [
      [
        0,
        0
      ]
    ],
    [
      [
        0,
        1
      ]
    ]
  ]
}

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

Wizard outline
  1. Step 1: Initialize unreachable distances

    Return a rows-by-cols grid of -1 when there are no sources. The -1 sentinel distinguishes undiscovered cells from sources whose real distance is zero.

  2. Step 2: Expand one source frontier

    Seed a deque with all source cells at zero and assign each undiscovered neighbor parent distance plus one. A single source makes the shortest-layer invariant visible before obstacles and competing sources interact.

  3. Step 3: Exclude blocked cells from the shared frontier

    Build a blocked set and refuse to assign or enqueue those coordinates while all sources compete normally. Obstacle membership is the final eligibility condition for the otherwise complete multi-source BFS.

Footguns and prerequisites
  • Running a separate BFS per source repeats work and complicates choosing the nearest result.
  • Assigning distance when dequeuing allows duplicate frontier entries and can overwrite shorter paths.
  • trees and graphs
Reviewed references
Prepared Interview Problems
  • Rotting Oranges(opens in a new tab)

    Expand a Multi-Source Frontier isolates every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order. That focused state discipline is required when implementing rotting oranges as a complete Interview Problem.

  • Walls and Gates(opens in a new tab)

    Expand a Multi-Source Frontier isolates every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order. That focused state discipline is required when implementing walls and gates as a complete Interview Problem.

Recommended approach and implementation

When distance is measured to the nearest of many starts, enqueue all starts at distance zero before expanding one shared BFS. Every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order.

Why it works: All sources begin at distance zero in one queue. Breadth-first expansion reaches each unvisited neighbor with the smallest possible edge count, and marking on enqueue prevents any longer route from replacing it.

from collections import deque

def multi_source_distances(rows, columns, sources, blocked):
    distances = [[-1] * columns for _ in range(rows)]
    blocked_cells = {tuple(cell) for cell in blocked}
    queue = deque()
    for row, column in sources:
        if (row, column) not in blocked_cells and distances[row][column] == -1:
            distances[row][column] = 0
            queue.append((row, column))
    while queue:
        row, column = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, column + dc
            if 0 <= nr < rows and 0 <= nc < columns and (nr, nc) not in blocked_cells and distances[nr][nc] == -1:
                distances[nr][nc] = distances[row][column] + 1
                queue.append((nr, nc))
    return distances