Hackerrank: Graphs II BFS Multi Source
Multi Source BFS Algorithm Intro
Intro
Multi Source BFS is an extension of Breadth First Search where we start BFS simultaneously from multiple source nodes.
3. Post Office Placement Add One — Hard
Topics: Multi Source BFS, Binary Search, Matrix, Chebyshev Distance Companies: Amazon
Intro
Given a 2D grid where 1 represents a post office and 0 represents an empty cell, you may add at most one new post office anywhere in the grid. Using 9-direction movement (8 neighbors + Chebyshev metric), find the minimum possible value of the maximum distance from any cell to its nearest post office after adding that one office.
| Example Input | Output |
|---|---|
| grid = [[1,0,0],[0,0,0],[0,0,1]] | 1 |
| grid = [[0,0,0],[0,0,0],[0,0,1]] | 1 |
| grid = [[1,0,0,0,1]] | 1 |
Constraints:
m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 100
grid[i][j] is 0 or 1.
At least one cell contains a 1.
Abstraction
Given a grid with existing post offices, place one additional post office to minimize the worst-case (max) Chebyshev distance from any cell to its nearest post office.
Pseudocode
1. multi-source BFS from all existing 1-cells using 8-directional moves
-> dist[r][c] = distance to nearest EXISTING post office
2. binary search on answer d (0 .. max possible distance):
collect all cells where dist[r][c] > d (cells the new office must cover)
if none -> feasible (existing offices already good enough)
else compute bounding box of those cells
(minR, maxR, minC, maxC)
feasible if (maxR - minR) <= 2d AND (maxC - minC) <= 2d
(a single point can Chebyshev-cover a box iff the box fits in a (2d+1)x(2d+1) window)
3. shrink d while feasible, return smallest feasible dSolution 1: [BFS] [Binary Search] Multi Source BFS with Bounding Box Feasibility - Graph/Greedy
def minMaxDistance(self, grid: List[List[int]]) -> int:
# Multi Source BFS (Chebyshev Distance) + Binary Search on Answer
# Determine minimum possible value of the max distance to nearest
# post office, after optimally placing ONE new post office
# Idea:
# - Step 1: BFS from ALL existing post offices simultaneously
# using 8-directional moves -> gives Chebyshev distance
# from every cell to nearest EXISTING office
# - Step 2: Binary search on the answer d. A candidate d is
# feasible if a single new office can cover every cell
# whose existing distance is > d, within radius d
# - Step 3: Feasibility check uses the fact that a Chebyshev ball
# of radius d is a (2d+1) x (2d+1) square, so a set of
# points is coverable by one point iff its bounding box
# fits inside that square
# Edge Case + Setup
# boundaries
# sc: O(1)
m, n = len(grid), len(grid[0])
# Iterative Queue Holds: (row, col, dist)
# sc: O(m*n)
queue = deque()
# dist grid initialized to -1 (unvisited)
# sc: O(m*n)
dist = [[-1] * n for _ in range(m)]
# Multi Source Setup:
# - put all existing post offices in BFS queue at dist 0
# tc: O(m*n)
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
dist[r][c] = 0
queue.append((r, c, 0))
# 8 directions (9-direction movement minus "stay in place")
directions = [(-1,-1), (-1,0), (-1,1),
(0,-1), (0,1),
(1,-1), (1,0), (1,1)]
# BFS Traversal:
# Fills dist[r][c] = distance to nearest EXISTING post office
# tc: O(m*n) each cell processed once
while queue:
# Process current root
r, c, d = queue.popleft()
# Process Choices:
# 8 direction spread
for dr, dc in directions:
nr, nc = r + dr, c + dc
# Early Pruning:
# Valid bounds and unvisited cell
if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1:
# Record distance immediately
dist[nr][nc] = d + 1
# Add next frontier cell to queue
queue.append((nr, nc, d + 1))
# Feasibility Check Helper:
# Given candidate d, can ONE new office cover all cells
# whose existing dist > d, within Chebyshev radius d?
# tc: O(m*n) per call
def feasible(d):
minR, maxR = float('inf'), float('-inf')
minC, maxC = float('inf'), float('-inf')
found = False
# Scan all cells still uncovered at radius d
for r in range(m):
for c in range(n):
if dist[r][c] > d:
found = True
minR, maxR = min(minR, r), max(maxR, r)
minC, maxC = min(minC, c), max(maxC, c)
# No cell left uncovered -> trivially feasible
if not found:
return True
# Bounding box must fit inside a (2d+1) x (2d+1) window
return (maxR - minR) <= 2 * d and (maxC - minC) <= 2 * d
# Binary Search Setup:
# Search space for d: 0 .. max possible Chebyshev distance
# sc: O(1)
lo, hi = 0, max(m, n)
# Binary Search on Answer:
# Shrink toward smallest feasible d
# tc: O(log(m+n)) iterations * O(m*n) feasibility check
while lo < hi:
mid = (lo + hi) // 2
# Try smaller d if feasible, else need bigger d
if feasible(mid):
hi = mid
else:
lo = mid + 1
# overall: tc O(m*n*log(m+n))
# overall: sc O(m*n)
return loSolution 2: [Brute Force] Candidate Cell Simulation - Graph/Simulation
def minMaxDistance(self, grid: List[List[int]]) -> int:
# Brute Force Candidate Placement
# Try placing the new office at EVERY empty cell, recompute the
# resulting max distance, and take the best over all candidates
# Idea:
# - Step 1: BFS from ALL existing post offices to get
# dist[r][c] = distance to nearest EXISTING office
# - Step 2: For every candidate cell (r0, c0), the resulting max
# distance is max over all cells of
# min(dist[r][c], chebyshev(r, c, r0, c0))
# - Step 3: Take the candidate that minimizes that max distance
# Edge Case + Setup
# boundaries
# sc: O(1)
m, n = len(grid), len(grid[0])
# Iterative Queue Holds: (row, col, dist)
# sc: O(m*n)
queue = deque()
# dist grid initialized to -1 (unvisited)
# sc: O(m*n)
dist = [[-1] * n for _ in range(m)]
# Multi Source Setup:
# - put all existing post offices in BFS queue at dist 0
# tc: O(m*n)
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
dist[r][c] = 0
queue.append((r, c, 0))
# 8 directions (9-direction movement minus "stay in place")
directions = [(-1,-1), (-1,0), (-1,1),
(0,-1), (0,1),
(1,-1), (1,0), (1,1)]
# BFS Traversal:
# Fills dist[r][c] = distance to nearest EXISTING post office
# tc: O(m*n) each cell processed once
while queue:
r, c, d = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1:
dist[nr][nc] = d + 1
queue.append((nr, nc, d + 1))
# Best answer found across all candidate placements
# sc: O(1)
best = float('inf')
# Try Every Candidate Cell:
# Simulate placing the new office at (r0, c0)
# tc: O(m*n) candidates
for r0 in range(m):
for c0 in range(n):
# Track worst-case distance for THIS candidate
# sc: O(1)
curMax = 0
# Recompute max distance if office placed here
# tc: O(m*n) per candidate
for r in range(m):
for c in range(n):
# Chebyshev distance to the candidate office
chebyshev = max(abs(r - r0), abs(c - c0))
# Nearest of existing offices vs this candidate
best_for_cell = min(dist[r][c], chebyshev)
curMax = max(curMax, best_for_cell)
# Keep best (smallest) worst-case seen so far
best = min(best, curMax)
# overall: tc O((m*n)^2)
# overall: sc O(m*n)
return best