Shortest Path Through a Grid With Obstacles

Pattern: Graphs: BFS, DFS and Union-Find · Difficulty: Medium · Asked at: Amazon, Meta, Uber, DoorDash

Classic version: LeetCode 1091 · LeetCode 127

Problem

grid is a list of strings; '.' is open and '#' is blocked. Moving up/down/left/right costs 1. Return the minimum number of moves from the top-left to the bottom-right cell, or -1 if unreachable (including when either end is blocked).

Examples

shortest_path(["..",
               ".."])        → 2
shortest_path([".#.",
               ".#.",
               "..."])       → 4

Starter code

def shortest_path(grid: list[str]) -> int:
    pass

Hints

Where this shows up in data engineering

BFS levels answer “how many hops?”: degrees of separation in a user graph, how far downstream a broken table’s impact reaches in lineage (blast radius by hop count), and the minimum number of transformations between schemas. With weighted edges (cost, latency) switch to Dijkstra.

Solution

from collections import deque


def shortest_path(grid):
    if not grid or grid[0][0] == "#" or grid[-1][-1] == "#":
        return -1
    rows, cols = len(grid), len(grid[0])
    q = deque([(0, 0, 0)])
    seen = {(0, 0)}
    while q:
        r, c, d = q.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return d
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Tests

Your solution should pass these:

assert shortest_path(["..", ".."]) == 2
assert shortest_path([".#.", ".#.", "..."]) == 4
assert shortest_path(["."]) == 0
assert shortest_path(["#"]) == -1
assert shortest_path([".#", "#."]) == -1
assert shortest_path(["....", "###.", "....", ".###", "...."]) == 13

Explanation

Why BFS is shortest: it processes all cells at distance d before any at distance d+1 (FIFO queue), so the first arrival at the target is optimal. DFS gives a path, not the shortest.

Complexity: O(R·C) time and space.

Variants: 8-directional moves (add diagonals), weighted cells (Dijkstra with a heap), “remove up to k obstacles” (BFS over states (r, c, k_left)), and bidirectional BFS to roughly square-root the explored area on large graphs.

Follow-up questions