Shortest Path: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Shortest Path Algorithms: Complete Guide with Examples

Welcome to the practice problems for shortest path. If you need to refresh the algorithm code first, the code templates have Dijkstra, BFS, Bellman-Ford, and Floyd-Warshall in all 6 languages. Each problem below includes a hint, a visual snapshot, and a full working solution you can trace against a small input. If the “why this pattern” lines do not click yet, the concept guide builds the selection logic from scratch.

Recommended Study Order

The problems build on each other, and the order matters more than the individual solutions.

Minimum Depth of Binary Tree teaches the BFS layer mechanic on an input where the graph is a tree. The graph noise is gone, so the layer-by-layer discovery is visible by itself.
Shortest Path in Binary Matrix moves BFS onto a grid, which is where most interviewers actually test it. The only new wrinkle is the 8-direction adjacency.
Network Delay Time swaps the queue for a heap. This is the Dijkstra you will write most in interviews, and the start of weighted thinking.
Cheapest Flights Within K Stops adds a budget, and the budget turns the problem into a Bellman-Ford round count. If you understood problem 3 fully, this one clicks quickly.
Find the City With the Smallest Number of Neighbors at a Threshold Distance is the all-pairs problem. Floyd-Warshall does the heavy lifting and the answer logic is the new part.
Swim in Rising Water redefines what “short” means. The path cost is the tallest obstacle on the path, and Dijkstra still works.
Shortest Path Visiting All Nodes is the hardest. The visited mask turns the state space into 2^N states, and BFS over states finishes it.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy

1. Minimum Depth of Binary Tree

LeetCode 111 | Difficulty: Easy

Brief: Return the minimum depth of a binary tree, which is the number of nodes along the shortest path from the root down to the nearest leaf.

Why this pattern: a tree is a graph where each node has at most two neighbors, and every edge costs one level. BFS visits nodes layer by layer, so the first time a node with no children shows up, that layer count is the answer.

Key Insight: the answer is the depth of the first leaf in BFS order. No need to search the rest of the tree.

Visual:

    graph TD
    R["root: 3, depth 1"] --> A["9, depth 2"]
    R --> B["20, depth 2"]
    B --> C["15, depth 3"]
    B --> D["7, depth 3"]
    L["BFS pops 9 at depth 2. It is a leaf, so depth 2 is the answer"]
    A -.-> L

Code:

var minDepth = function(root) {
    if (root === null) return 0;

    const queue = [root];
    let depth = 1;

    while (queue.length > 0) {
        const levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            // BFS checks nodes in depth order, so the first leaf
            // found is the one the answer must come from
            if (node.left === null && node.right === null) return depth;
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        depth++;
    }
    return depth;
};

from collections import deque

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        queue = deque([root])
        depth = 1

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                # The first leaf found is the closest one because
                # the queue processes entire levels in order
                if node.left is None and node.right is None:
                    return depth
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1

        return depth

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // The first node without children is the nearest leaf
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }
        return depth;
    }
}

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;

        queue<TreeNode*> q;
        q.push(root);
        int depth = 1;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                // A leaf found at depth d means no smaller depth exists
                if (!node->left && !node->right) return depth;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    queue := []*TreeNode{root}
    depth := 1

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            // First leaf in BFS order owns the minimum depth
            if node.Left == nil && node.Right == nil {
                return depth
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        depth++
    }
    return depth
}

def min_depth(root)
    return 0 if root.nil?

    queue = [root]
    depth = 1

    until queue.empty?
        level_size = queue.length
        level_size.times do
            node = queue.shift
            # Levels are processed in order, so this first leaf
            # is the one with the fewest edges from the root
            return depth if node.left.nil? && node.right.nil?
            queue.push(node.left) if node.left
            queue.push(node.right) if node.right
        end
        depth += 1
    end

    depth
end

The level counter is the extra piece over plain BFS. By draining exactly one level per iteration, depth reflects how many edges separate the current layer from the root, and the first leaf encountered answers the question. A DFS would need to track the best-so-far and prune, which is more machinery for the same answer.

Medium

2. Shortest Path in Binary Matrix

LeetCode 1091 | Difficulty: Medium

Brief: return the length of the shortest clear path from the top-left to the bottom-right cell in an n x n binary matrix, moving in 8 directions through cells that contain 0.

Why this pattern: the grid is a graph, and moving to a neighbor costs one step. BFS guarantees the first time the target cell is discovered, it is via fewest steps, so the distance array doubles as the visited set.

Key Insight: an 8-directional move stays one step, so the 8 neighbors are simply a second direction list. The answer counts cells visited, which the distance value naturally does when the start is counted as 1.

Visual:

    graph TD
    A["grid: 0 0 0 / 1 1 0 / 1 1 0 (1 = blocked)"] --> B["Start (0,0) at distance 1"]
    B --> C["Only (0,1) is open from the start: distance 2"]
    C --> D["Step to (0,2) or (1,2): distance 3"]
    D --> E["Target (2,2) reached at distance 4"]

Code (all 6 languages):

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;

    const dirs = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1],           [0, 1],
        [1, -1],  [1, 0],  [1, 1]
    ];
    const queue = [[0, 0, 1]]; // [row, col, steps]
    const visited = Array.from({ length: n }, () => new Array(n).fill(false));
    visited[0][0] = true;

    while (queue.length > 0) {
        const [r, c, steps] = queue.shift();
        if (r === n - 1 && c === n - 1) return steps;

        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                grid[nr][nc] === 0 && !visited[nr][nc]) {
                // First discovery is the shortest path, so mark
                // immediately to keep duplicates out of the queue
                visited[nr][nc] = true;
                queue.push([nr, nc, steps + 1]);
            }
        }
    }
    return -1;
};

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1

        dirs = [(-1, -1), (-1, 0), (-1, 1),
                (0, -1),           (0, 1),
                (1, -1),  (1, 0),  (1, 1)]

        queue = deque([(0, 0, 1)])  # (row, col, steps)
        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True

        while queue:
            r, c, steps = queue.popleft()
            if r == n - 1 and c == n - 1:
                return steps

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n and
                        grid[nr][nc] == 0 and not visited[nr][nc]):
                    # The first node to reach this cell owns the shortest run
                    visited[nr][nc] = True
                    queue.append((nr, nc, steps + 1))

        return -1

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;

        int[][] dirs = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},           {0, 1},
            {1, -1},  {1, 0},  {1, 1}
        };
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1], steps = cur[2];
            if (r == n - 1 && c == n - 1) return steps;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                    grid[nr][nc] == 0 && !visited[nr][nc]) {
                    // find the first discoverer, then never re-enqueue
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, steps + 1});
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;

        vector<pair<int, int>> dirs = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},           {0, 1},
            {1, -1},  {1, 0},  {1, 1}
        };

        queue<array<int, 3>> q; // row, col, steps
        q.push({0, 0, 1});
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;

        while (!q.empty()) {
            auto [r, c, steps] = q.front();
            q.pop();
            if (r == n - 1 && c == n - 1) return steps;

            for (auto [dr, dc] : dirs) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                    grid[nr][nc] == 0 && !visited[nr][nc]) {
                    visited[nr][nc] = true;  // BFS first-seen is shortest
                    q.push({nr, nc, steps + 1});
                }
            }
        }
        return -1;
    }
};

func shortestPathBinaryMatrix(grid [][]int) int {
    n := len(grid)
    if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
        return -1
    }

    dirs := [8][2]int{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1}, {0, 1},
        {1, -1}, {1, 0}, {1, 1},
    }

    queue := [][3]int{{0, 0, 1}}
    visited := make([][]bool, n)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    visited[0][0] = true

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        r, c, steps := cur[0], cur[1], cur[2]
        if r == n-1 && c == n-1 {
            return steps
        }

        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < n && nc >= 0 && nc < n &&
                grid[nr][nc] == 0 && !visited[nr][nc] {
                visited[nr][nc] = true // first finder holds the shortest hop count
                queue = append(queue, [3]int{nr, nc, steps + 1})
            }
        }
    }
    return -1
}

def shortest_path_binary_matrix(grid)
    n = grid.length
    return -1 if grid[0][0] == 1 || grid[n - 1][n - 1] == 1

    dirs = [[-1, -1], [-1, 0], [-1, 1],
            [0, -1],           [0, 1],
            [1, -1],  [1, 0],  [1, 1]]

    queue = [[0, 0, 1]]  # row, col, steps
    visited = Array.new(n) { Array.new(n, false) }
    visited[0][0] = true

    until queue.empty?
        r, c, steps = queue.shift
        return steps if r == n - 1 && c == n - 1

        dirs.each do |dr, dc|
            nr = r + dr
            nc = c + dc
            if nr >= 0 && nr < n && nc >= 0 && nc < n &&
               grid[nr][nc] == 0 && !visited[nr][nc]
                # Mark on enqueue so no cell is queued twice
                visited[nr][nc] = true
                queue.push([nr, nc, steps + 1])
            end
        end
    end

    -1
end

Counting steps as 1 + the number of moves is the same pattern as depth in the previous problem. The 8 directions may look like extra work, but each cell still gets discovered exactly once, so the runtime stays

O(N²)

with the visited matrix doing double duty as the distance record.

3. Network Delay Time

LeetCode 743 | Difficulty: Medium

Brief: a signal starts at node k and travels through a weighted directed graph. Return the time until every node received the signal, or -1 if some node is unreachable.

Why this pattern: this is single-source shortest distances, exactly what Dijkstra computes, and the answer is the maximum of those distances.

Key Insight: once Dijkstra finishes, one scan over the distance array answers both remaining questions. An Infinity means unreachable, and the largest finite distance is the moment the last node got the signal.

Visual:

    graph TD
    A["times: 1-2 cost 1, 1-3 cost 4, 2-3 cost 1"] --> B["Dijkstra from 1"]
    B --> C["dist[1] = 0, pop 1"]
    C --> D["relax 2 to 1, relax 3 to 4"]
    D --> E["pop 2 (closest unsettled), relax 3 to 2"]
    E --> F["dist[2]=1, dist[3]=2, max = 2"]

Code:

class MinHeap {
    constructor() { this.items = []; }
    push(item) {
        this.items.push(item);
        let i = this.items.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.items[p][0] <= this.items[i][0]) break;
            [this.items[p], this.items[i]] = [this.items[i], this.items[p]];
            i = p;
        }
    }
    pop() {
        const top = this.items[0];
        const last = this.items.pop();
        if (this.items.length > 0) {
            this.items[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < this.items.length && this.items[l][0] < this.items[s][0]) s = l;
                if (r < this.items.length && this.items[r][0] < this.items[s][0]) s = r;
                if (s === i) break;
                [this.items[i], this.items[s]] = [this.items[s], this.items[i]];
                i = s;
            }
        }
        return top;
    }
    get size() { return this.items.length; }
}

var networkDelayTime = function(times, n, k) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) graph[u].push([v, w]);

    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;

    const heap = new MinHeap();
    heap.push([0, k]);

    while (heap.size > 0) {
        const [d, u] = heap.pop();
        // Skip heap entries that aged out after a better path was found
        if (d > dist[u]) continue;

        for (const [v, w] of graph[u]) {
            const nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                heap.push([nd, v]);
            }
        }
    }

    let maxTime = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1; // node never reached
        maxTime = Math.max(maxTime, dist[i]);
    }
    return maxTime;
};

import heapq

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n + 1)]
        for u, v, w in times:
            graph[u].append((v, w))

        dist = [float('inf')] * (n + 1)
        dist[k] = 0

        heap = [(0, k)]

        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue  # a better route to u was found since this entry aged

            for v, w in graph[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(heap, (nd, v))

        max_time = 0
        for i in range(1, n + 1):
            if dist[i] == float('inf'):
                return -1
            max_time = max(max_time, dist[i])
        return max_time

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] t : times) graph[t[0]].add(new int[]{t[1], t[2]});

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        heap.offer(new int[]{0, k});

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            // stale entries only add work; information arrives once
            if (d > dist[u]) continue;

            for (int[] e : graph[u]) {
                int v = e[0], w = e[1];
                int nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    heap.offer(new int[]{nd, v});
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1; // unreachable node
            maxTime = Math.max(maxTime, dist[i]);
        }
        return maxTime;
    }
}

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> graph(n + 1);
        for (auto& t : times) graph[t[0]].push_back({t[1], t[2]});

        vector<int> dist(n + 1, INT_MAX);
        dist[k] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        heap.push({0, k});

        while (!heap.empty()) {
            auto [d, u] = heap.top();
            heap.pop();
            if (d > dist[u]) continue; // better route discovered later
            for (auto [v, w] : graph[u]) {
                int nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    heap.push({nd, v});
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) return -1;
            maxTime = max(maxTime, dist[i]);
        }
        return maxTime;
    }
};

import (
    "container/heap"
    "math"
)

type pqItem struct {
    dist, node int
}

type minpq []pqItem
func (h minpq) Len() int            { return len(h) }
func (h minpq) Less(i, j int) bool  { return h[i].dist < h[j].dist }
func (h minpq) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minpq) Push(x interface{}) { *h = append(*h, x.(pqItem)) }
func (h *minpq) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func networkDelayTime(times [][]int, n, k int) int {
    graph := make([][][2]int, n+1)
    for _, t := range times {
        graph[t[0]] = append(graph[t[0]], [2]int{t[1], t[2]})
    }

    dist := make([]int, n+1)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[k] = 0

    h := &minpq{}
    heap.Init(h)
    heap.Push(h, pqItem{0, k})

    for h.Len() > 0 {
        it := heap.Pop(h).(pqItem)
        d, u := it.dist, it.node
        if d > dist[u] {
            continue // superseded by a better route already recorded
        }
        for _, e := range graph[u] {
            v, w := e[0], e[1]
            nd := d + w
            if nd < dist[v] {
                dist[v] = nd
                heap.Push(h, pqItem{nd, v})
            }
        }
    }

    maxTime := 0
    for i := 1; i <= n; i++ {
        if dist[i] == math.MaxInt32 {
            return -1
        }
        if dist[i] > maxTime {
            maxTime = dist[i]
        }
    }
    return maxTime
}

class MinHeap
    def initialize
        @items = []
    end

    def push(item)
        @items.push(item)
        i = @items.length - 1
        while i > 0
            p = (i - 1) / 2
            break if @items[p][0] <= @items[i][0]
            @items[p], @items[i] = @items[i], @items[p]
            i = p
        end
    end

    def pop
        top = @items[0]
        last = @items.pop
        unless @items.empty?
            @items[0] = last
            i = 0
            loop do
                s = i
                l = 2 * i + 1
                r = 2 * i + 2
                s = l if l < @items.length && @items[l][0] < @items[s][0]
                s = r if r < @items.length && @items[r][0] < @items[s][0]
                break if s == i
                @items[i], @items[s] = @items[s], @items[i]
                i = s
            end
        end
        top
    end

    def empty?
        @items.empty?
    end
end

def network_delay_time(times, n, k)
    graph = Array.new(n + 1) { [] }
    times.each { |u, v, w| graph[u] << [v, w] }

    dist = Array.new(n + 1, Float::INFINITY)
    dist[k] = 0

    heap = MinHeap.new
    heap.push([0, k])

    until heap.empty?
        d, u = heap.pop
        next if d > dist[u]  # a later, better route aged out this entry

        graph[u].each do |v, w|
            nd = d + w
            if nd < dist[v]
                dist[v] = nd
                heap.push([nd, v])
            end
        end
    end

    max_time = 0
    (1..n).each do |i|
        return -1 if dist[i] == Float::INFINITY
        max_time = [max_time, dist[i]].max
    end
    max_time
end

The distance array starts at 0 for the source and Infinity for everyone else. After the heap is drained, Infinity means the signal never arrived, and the code reads that sentinel in the final max loop instead of a second structure. This is the canonical “start a weighted problem, see if Dijkstra fits” problem, and the heap handles triple-digit edge counts without rework.

4. Cheapest Flights Within K Stops

LeetCode 787 | Difficulty: Medium

Brief: find the cheapest flight price from src to dst with at most k intermediate stops, or -1 if no such route exists.

Why this pattern: the stop limit bounds the number of flight legs to k + 1. Bellman-Ford relaxes edges once per allowed leg, so the k budget maps directly onto the round count.

Key Insight: each Bellman-Ford round must run against the snapshot from the previous round, never the in-progress array. Without the snapshot, one round can chain several flights and quietly exceed the stop limit.

Visual:

    graph TD
    A["flights: 0 to 1 cost 1, 0 to 2 cost 5, 1 to 2 cost 1, 2 to 3 cost 1; src 0, dst 3, k = 1"] --> B["round 1: best 1-leg prices 0-1 = 1, 0-2 = 5"]
    B --> C["round 2: extend round-1 prices, 1 to 2 now 2, 2 to 3 now 6"]
    C --> D["Answer: cheapest dst = 6, 2 flight legs = 1 stop"]

Code:

var findCheapestPrice = function(n, flights, src, dst, k) {
    let prices = new Array(n).fill(Infinity);
    prices[src] = 0;

    // at most k stops means at most k + 1 flight legs
    for (let round = 0; round < k + 1; round++) {
        // snapshot: read the previous round so one pass cannot
        // chain multiple flights into a single "leg"
        const next = [...prices];
        for (const [u, v, price] of flights) {
            if (prices[u] === Infinity) continue;
            const candidate = prices[u] + price;
            if (candidate < next[v]) next[v] = candidate;
        }
        prices = next;
    }

    return prices[dst] === Infinity ? -1 : prices[dst];
};

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [float('inf')] * n
        prices[src] = 0

        # at most k stops = at most k + 1 flight legs
        for _ in range(k + 1):
            # each round builds from the previous round's snapshot, so a
            # single round cannot chain several flights together
            next_prices = prices[:]
            for u, v, price in flights:
                if prices[u] == float('inf'):
                    continue
                candidate = prices[u] + price
                if candidate < next_prices[v]:
                    next_prices[v] = candidate
            prices = next_prices

        return -1 if prices[dst] == float('inf') else prices[dst]

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;

        // k stops = k + 1 legs max, so run k + 1 rounds
        for (int round = 0; round < k + 1; round++) {
            // relaxing against the copy stops one round from hopping
            // through several flights that take several rounds
            int[] next = prices.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], price = f[2];
                if (prices[u] == Integer.MAX_VALUE) continue;
                int candidate = prices[u] + price;
                if (candidate < next[v]) next[v] = candidate;
            }
            prices = next;
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> prices(n, INT_MAX);
        prices[src] = 0;

        // at most k stops = at most k + 1 legs per allowed route
        for (int round = 0; round < k + 1; round++) {
            // copying the previous round blocks multi-leg hops
            // inside a single round
            vector<int> next = prices;
            for (auto& f : flights) {
                int u = f[0], v = f[1], price = f[2];
                if (prices[u] == INT_MAX) continue;
                int candidate = prices[u] + price;
                if (candidate < next[v]) next[v] = candidate;
            }
            prices = next;
        }

        return prices[dst] == INT_MAX ? -1 : prices[dst];
    }
};

import "math"

func findCheapestPrice(n int, flights [][]int, src, dst, k int) int {
    prices := make([]int, n)
    for i := range prices {
        prices[i] = math.MaxInt32
    }
    prices[src] = 0

    // k stops allowed = k+1 legs allowed = k+1 relaxation rounds
    for round := 0; round < k+1; round++ {
        next := make([]int, n)
        copy(next, prices)
        for _, f := range flights {
            u, v, price := f[0], f[1], f[2]
            if prices[u] == math.MaxInt32 {
                continue
            }
            candidate := prices[u] + price
            if candidate < next[v] {
                next[v] = candidate
            }
        }
        prices = next
    }

    if prices[dst] == math.MaxInt32 {
        return -1
    }
    return prices[dst]
}

def find_cheapest_price(_n, flights, src, dst, k)
    prices = Array.new(_n, Float::INFINITY)
    prices[src] = 0

    # k stops max means k + 1 flight legs, one round per leg
    (k + 1).times do
        # Run each round off the previous snapshot so a single
        # round never hoots through multiple legs.
        next_prices = prices.dup
        flights.each do |u, v, price|
            next if prices[u] == Float::INFINITY
            candidate = prices[u] + price
            next_prices[v] = candidate if candidate < next_prices[v]
        end
        prices = next_prices
    end

    prices[dst] == Float::INFINITY ? -1 : prices[dst]
end

The snapshot copy is the whole trick, and it is the easiest thing to drop in a hurry. If you relax edge (u, v) and then immediately read the updated price[v], the next edge in the same flight list can build on it, letting one round trail through unlimited legs. The interview version of this problem is often stated as “Dijkstra with a stop budget”, and the Bellman-Ford framing here answers it without a three-dimensional visited structure.

5. Find the City With the Smallest Number of Neighbors at a Threshold Distance

LeetCode 1334 | Difficulty: Medium

Brief: given an undirected weighted graph, return the city with the fewest other cities reachable within a distance threshold. Ties go to the city with the larger index.

Why this pattern: the question must count neighbors for every city, and every pair distance must be compared to the threshold. That is the all-pairs requirement, and Floyd-Warshall fills exactly that matrix.

Key Insight: every city needs distances to every other city, so running Dijkstra n times (n log V each) works but the triple loop solves it in one pass over the matrix, which is less code to get signed-off.

Visual:

    graph TD
    A["threshold = 4"] --> B["dist matrix after Floyd-Warshall"]
    B --> C["count per city of dist[i][j] <= 4"]
    C --> D["city 1 reaches 2, city 0 reaches 4"]
    D --> E["fewest = city 3 (2 neighbors), answer 3"]

Code:

var findTheCity = function(n, edges, distanceThreshold) {
    const INF = Infinity;
    const dist = Array.from({ length: n }, () => new Array(n).fill(INF));
    for (let i = 0; i < n; i++) dist[i][i] = 0;
    for (const [u, v, w] of edges) {
        dist[u][v] = w;
        dist[v][u] = w;
    }

    // k-th pass lets every pair route through city k
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] !== INF && dist[k][j] !== INF) {
                    const via = dist[i][k] + dist[k][j];
                    if (via < dist[i][j]) dist[i][j] = via;
                }
            }
        }
    }

    let bestCity = -1;
    let fewest = Infinity;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (j !== i && dist[i][j] <= distanceThreshold) count++;
        }
        // strictly fewer wins; equal count prefers the larger index
        if (count < fewest || (count === fewest && i > bestCity)) {
            fewest = count;
            bestCity = i;
        }
    }
    return bestCity;
};

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:
        dist = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w

        # city k can be the bridge for every pair
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                        via = dist[i][k] + dist[k][j]
                        if via < dist[i][j]:
                            dist[i][j] = via

        best = -1
        fewest = float('inf')
        for i in range(n):
            count = sum(1 for j in range(n)
                        if j != i and dist[i][j] <= threshold)
            # ties resolve to the largest index
            if count < fewest or (count == fewest and i > best):
                fewest = count
                best = i
        return best

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        final int INF = Integer.MAX_VALUE / 2; // safe for sums
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dist[i], INF);
        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (int[] e : edges) {
            dist[e[0]][e[1]] = e[2];
            dist[e[1]][e[0]] = e[2];
        }

        // Floyd-Warshall: k is the candidate mid-hop city
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] == INF || dist[k][j] == INF) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int best = -1;
        int fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (j != i && dist[i][j] <= distanceThreshold) count++;
            }
            // smaller count wins, ties go to larger index
            if (count < fewest || (count == fewest && i > best)) {
                fewest = count;
                best = i;
            }
        }
        return best;
    }
}

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const long long INF = 1e18;
        vector<vector<long long>> dist(n, vector<long long>(n, INF));
        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (auto& e : edges) {
            dist[e[0]][e[1]] = e[2];
            dist[e[1]][e[0]] = e[2];
        }

        // route every pair through city k in the k-th pass
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] != INF && dist[k][j] != INF)
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        int best = -1, fewest = INT_MAX;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= distanceThreshold) count++;
            if (count < fewest || (count == fewest && i > best)) {
                fewest = count;
                best = i;
            }
        }
        return best;
    }
};

import "math"

func findTheCity(n int, edges [][]int, threshold int) int {
    const INF = math.MaxInt32 / 2
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = INF
        }
        dist[i][i] = 0
    }
    for _, e := range edges {
        dist[e[0]][e[1]] = e[2]
        dist[e[1]][e[0]] = e[2]
    }

    // k-th pass lets each pair try to route through city k
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] == INF || dist[k][j] == INF {
                    continue
                }
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    best := -1
    fewest := math.MaxInt32
    for i := 0; i < n; i++ {
        count := 0
        for j := 0; j < n; j++ {
            if j != i && dist[i][j] <= threshold {
                count++
            }
        }
        // Fewer neighbors wins; ties pick the larger index
        if count < fewest || (count == fewest && i > best) {
            fewest = count
            best = i
        }
    }
    return best
}

def find_the_city(n, edges, threshold)
    dist = Array.new(n) { Array.new(n, Float::INFINITY) }
    n.times { |i| dist[i][i] = 0 }
    edges.each do |u, v, w|
        dist[u][v] = w
        dist[v][u] = w
    end

    # one pass for every candidate middle city
    n.times do |k|
        n.times do |i|
            n.times do |j|
                next if dist[i][k] == Float::INFINITY || dist[k][j] == Float::INFINITY
                via = dist[i][k] + dist[k][j]
                dist[i][j] = [dist[i][j], via].min
            end
        end
    end

    best = -1
    fewest = Float::INFINITY
    n.times do |i|
        count = (0...n).count { |j| j != i && dist[i][j] <= threshold }
        if count < fewest || (count == fewest && i > best)
            fewest = count
            best = i
        end
    end
    best
end

The threshold comparison happens after the matrix is complete, which is why only one Floyd-Warshall run is needed. The tie-break (“largest index wins”) is worth writing down before coding, since the straightforward scan returns the smallest index when no tie logic exists. The matrix space is the price of this approach, and the scoring check makes the value of all-pairs clear: without the full table, every query would recompute the graph.

Hard

6. Swim in Rising Water

LeetCode 778 | Difficulty: Hard

Brief: water rises at one unit per minute, and an elevation becomes passable only when the water covers it. Return the earliest time you can reach the bottom-right cell from the top-left cell if you can move only through covered elevation.

Why this pattern: the cost of a path is the highest elevation on it, not the sum. That changed definition breaks BFS and plain sum-Dijkstra, but the update rule of Dijkstra adapts: a path through a neighbor costs max(current so far, neighbor’s elevation).

Key Insight: minimize the max, not the total. The heap now pops the path with the lowest peak elevation reached, and the first time the target cell leaves the heap is the answer.

Visual:

    graph TD
    A["grid: 0 2 / 1 3"] --> B["start (0,0) elev 0, t = 0"]
    B --> C["(1,0) elev 1 -> t = 1"]
    B --> D["(0,1) elev 2 -> t = 2"]
    C --> E["(1,1) elev 3 -> t = 3"]
    D --> E

Code:

class MinHeap {
    constructor() { this.items = []; }
    push(item) {
        this.items.push(item);
        let i = this.items.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.items[p][0] <= this.items[i][0]) break;
            [this.items[p], this.items[i]] = [this.items[i], this.items[p]];
            i = p;
        }
    }
    pop() {
        const top = this.items[0];
        const last = this.items.pop();
        if (this.items.length > 0) {
            this.items[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < this.items.length && this.items[l][0] < this.items[s][0]) s = l;
                if (r < this.items.length && this.items[r][0] < this.items[s][0]) s = r;
                if (s === i) break;
                [this.items[i], this.items[s]] = [this.items[s], this.items[i]];
                i = s;
            }
        }
        return top;
    }
    get size() { return this.items.length; }
}

var swimInWater = function(grid) {
    const n = grid.length;
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    // t[r][c] is the lowest water level at which (r,c) is reachable
    const t = Array.from({ length: n }, () => new Array(n).fill(Infinity));
    t[0][0] = grid[0][0];

    const heap = new MinHeap();
    heap.push([grid[0][0], 0, 0]);

    while (heap.size > 0) {
        const [level, r, c] = heap.pop();
        if (level > t[r][c]) continue; // stale entry
        if (r === n - 1 && c === n - 1) return level;

        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            // entering a cell raises the level to that cell's elevation
            const next = Math.max(level, grid[nr][nc]);
            if (next < t[nr][nc]) {
                t[nr][nc] = next;
                heap.push([next, nr, nc]);
            }
        }
    }
    return -1;
};

import heapq

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # level[r][c] = smallest water level that opens (r, c)
        level = [[float('inf')] * n for _ in range(n)]
        level[0][0] = grid[0][0]

        heap = [(grid[0][0], 0, 0)]

        while heap:
            cur, r, c = heapq.heappop(heap)
            if cur > level[r][c]:
                continue  # better route found already
            if r == n - 1 and c == n - 1:
                return cur

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    # water level for this step is the max so far
                    nxt = max(cur, grid[nr][nc])
                    if nxt < level[nr][nc]:
                        level[nr][nc] = nxt
                        heapq.heappush(heap, (nxt, nr, nc))

        return -1

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] level = new int[n][n];
        for (int[] row : level) Arrays.fill(row, Integer.MAX_VALUE);
        level[0][0] = grid[0][0];

        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        heap.offer(new int[]{grid[0][0], 0, 0});

        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int lvl = cur[0], r = cur[1], c = cur[2];
            if (lvl > level[r][c]) continue;
            if (r == n - 1 && c == n - 1) return lvl;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                // the water level for this cell is the max of the trail
                int next = Math.max(lvl, grid[nr][nc]);
                if (next < level[nr][nc]) {
                    level[nr][nc] = next;
                    heap.offer(new int[]{next, nr, nc});
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> level(n, vector<int>(n, INT_MAX));
        level[0][0] = grid[0][0];

        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> heap;
        heap.push({grid[0][0], 0, 0});
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        while (!heap.empty()) {
            auto [lvl, r, c] = heap.top();
            heap.pop();
            if (lvl > level[r][c]) continue;
            if (r == n - 1 && c == n - 1) return lvl;

            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                int next = max(lvl, grid[nr][nc]);
                if (next < level[nr][nc]) {
                    level[nr][nc] = next;
                    heap.push({next, nr, nc});
                }
            }
        }
        return -1;
    }
};

import (
    "container/heap"
    "math"
)

type cell struct {
    level, r, c int
}

type cellHeap []cell

func (h cellHeap) Len() int            { return len(h) }
func (h cellHeap) Less(i, j int) bool  { return h[i].level < h[j].level }
func (h cellHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *cellHeap) Push(x interface{}) { *h = append(*h, x.(cell)) }
func (h *cellHeap) Pop() interface{} {
    old := *h
    item := old[len(old)-1]
    *h = old[:len(old)-1]
    return item
}

func swimInWater(grid [][]int) int {
    n := len(grid)
    level := make([][]int, n)
    for i := range level {
        level[i] = make([]int, n)
        for j := range level[i] {
            level[i][j] = math.MaxInt32
        }
    }
    level[0][0] = grid[0][0]

    h := &cellHeap{}
    heap.Init(h)
    heap.Push(h, cell{grid[0][0], 0, 0})
    dirs := [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for h.Len() > 0 {
        cur := heap.Pop(h).(cell)
        if cur.level > level[cur.r][cur.c] {
            continue
        }
        if cur.r == n-1 && cur.c == n-1 {
            return cur.level
        }
        for _, d := range dirs {
            nr, nc := cur.r+d[0], cur.c+d[1]
            if nr < 0 || nr >= n || nc < 0 || nc >= n {
                continue
            }
            next := cur.level
            if grid[nr][nc] > next {
                next = grid[nr][nc]
            }
            if next < level[nr][nc] {
                level[nr][nc] = next
                heap.Push(h, cell{next, nr, nc})
            }
        }
    }
    return -1
}

class MinHeap
    def initialize
        @items = []
    end

    def push(item)
        @items.push(item)
        i = @items.length - 1
        while i > 0
            p = (i - 1) / 2
            break if @items[p][0] <= @items[i][0]
            @items[p], @items[i] = @items[i], @items[p]
            i = p
        end
    end

    def pop
        top = @items[0]
        last = @items.pop
        unless @items.empty?
            @items[0] = last
            i = 0
            loop do
                s = i
                l = 2 * i + 1
                r = 2 * i + 2
                s = l if l < @items.length && @items[l][0] < @items[s][0]
                s = r if r < @items.length && @items[r][0] < @items[s][0]
                break if s == i
                @items[i], @items[s] = @items[s], @items[i]
                i = s
            end
        end
        top
    end

    def empty?
        @items.empty?
    end
end

def swim_in_water(grid)
    n = grid.length
    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

    level = Array.new(n) { Array.new(n, Float::INFINITY) }
    level[0][0] = grid[0][0]

    heap = MinHeap.new
    heap.push([grid[0][0], 0, 0])

    until heap.empty?
        lvl, r, c = heap.pop
        next if lvl > level[r][c]  # a better route beat this one
        return lvl if r == n - 1 && c == n - 1

        dirs.each do |dr, dc|
            nr = r + dr
            nc = c + dc
            next if nr < 0 || nr >= n || nc < 0 || nc >= n
            # entering (nr, nc) sets the level as the current max
            nxt = [lvl, grid[nr][nc]].max
            if nxt < level[nr][nc]
                level[nr][nc] = nxt
                heap.push([nxt, nr, nc])
            end
        end
    end

    -1
end

The same stale-entry guard from Dijkstra is what keeps this runtime honest. BFS cannot solve the problem because the queue has no cost ordering, and sum-Dijkstra fails because elevation is a max, not a sum. Keeping the relaxation rule opposite the weight type (“minimize the largest”) is a good interview habit to practice.

7. Shortest Path Visiting All Nodes

LeetCode 847 | Difficulty: Hard

Brief: given an undirected graph, return the length of the shortest path that starts at any node and visits every node at least once.

Why this pattern: the distances between pairs are irrelevant here. What matters is combinatorial progress, and the state (current node, set of visited nodes) is exactly what BFS over states explores step by step.

Key Insight: encode the visited set as a bitmask, one bit per node. A state is a (node, mask) pair, and two states with the same pair have identical futures, so only one of them needs exploring. That pruning is what keeps the search from exploding into a full permutation scan.

Visual:

    graph TD
    A["Start states: (0, 001), (1, 010), (2, 100)"] --> B["Pop (0, 001), step 0"]
    B --> C["go to 1: (1, 011), step 1"]
    C --> D["go to 2: (2, 111), step 2"]
    D --> E["mask 111 == all nodes, return 2"]

Code:

var shortestPathLength = function(graph) {
    const n = graph.length;
    const full = (1 << n) - 1;

    // try starting from every node at once; a state is (node, mask)
    const queue = [];
    const seen = new Set();
    for (let i = 0; i < n; i++) {
        queue.push([i, 1 << i, 0]);
        seen.add(i + "," + (1 << i));
    }

    while (queue.length > 0) {
        const [node, mask, steps] = queue.shift();
        if (mask === full) return steps;

        for (const next of graph[node]) {
            const nextMask = mask | (1 << next);
            const key = next + "," + nextMask;
            // re-visiting (node, mask) is dead work, so BFS ignores it
            if (!seen.has(key)) {
                seen.add(key);
                queue.push([next, nextMask, steps + 1]);
            }
        }
    }
    return -1;
};

from collections import deque

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        full = (1 << n) - 1

        # state = (current node, visited mask); seed all nodes
        queue = deque((i, 1 << i, 0) for i in range(n))
        seen = {(i, 1 << i) for i in range(n)}

        while queue:
            node, mask, steps = queue.popleft()
            if mask == full:
                return steps

            for nxt in graph[node]:
                next_mask = mask | (1 << nxt)
                if (nxt, next_mask) not in seen:
                    # nothing gains from repeating the same state
                    seen.add((nxt, next_mask))
                    queue.append((nxt, next_mask, steps + 1))

        return -1

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int full = (1 << n) - 1;

        // every node is a possible starting state (node, mask)
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] seen = new boolean[n][1 << n];
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{i, 1 << i, 0});
            seen[i][1 << i] = true;
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int node = cur[0], mask = cur[1], steps = cur[2];
            if (mask == full) return steps;

            for (int next : graph[node]) {
                int nextMask = mask | (1 << next);
                // the same (node, mask) visited twice never helps
                if (!seen[next][nextMask]) {
                    seen[next][nextMask] = true;
                    queue.offer(new int[]{next, nextMask, steps + 1});
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int full = (1 << n) - 1;

        queue<array<int, 3>> q; // (node, mask, steps)
        vector<vector<bool>> seen(n, vector<bool>(1 << n, false));
        for (int i = 0; i < n; i++) {
            q.push({i, 1 << i, 0});
            seen[i][1 << i] = true;
        }

        while (!q.empty()) {
            auto [node, mask, steps] = q.front();
            q.pop();
            if (mask == full) return steps;

            for (int next : graph[node]) {
                int nextMask = mask | (1 << next);
                if (!seen[next][nextMask]) {
                    seen[next][nextMask] = true; // deduplicate states
                    q.push({next, nextMask, steps + 1});
                }
            }
        }
        return -1;
    }
};

func shortestPathLength(graph [][]int) int {
    n := len(graph)
    full := (1 << n) - 1

    queue := make([][3]int, 0, n)
    seen := make([][]bool, n)
    for i := range seen {
        seen[i] = make([]bool, 1<<n)
        queue = append(queue, [3]int{i, 1 << i, 0})
        seen[i][1<<i] = true
    }

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        node, mask, steps := cur[0], cur[1], cur[2]
        if mask == full {
            return steps
        }
        for _, next := range graph[node] {
            nextMask := mask | (1 << next)
            if !seen[next][nextMask] {
                // skip repeats of identical (node, mask) states
                seen[next][nextMask] = true
                queue = append(queue, [3]int{next, nextMask, steps + 1})
            }
        }
    }
    return -1
}

require 'set'

def shortest_path_length(graph)
    n = graph.length
    full = (1 << n) - 1

    # each node can be the start; the mask is the visited set
    queue = (0...n).map { |i| [i, 1 << i, 0] }
    seen = Set.new((0...n).map { |i| [i, 1 << i] })

    until queue.empty?
        node, mask, steps = queue.shift
        return steps if mask == full

        graph[node].each do |nxt|
            next_mask = mask | (1 << nxt)
            state = [nxt, next_mask]
            # re-visiting the same (node, mask) state never helps
            next if seen.include?(state)
            seen.add(state)
            queue.push([nxt, next_mask, steps + 1])
        end
    end

    -1
end

The trick in this problem is that BFS no longer spreads over graph nodes. It spreads over graph states, a pair of a current node and a visited-mask, and the shortest path guarantee still works on that state graph. The first time the all-ones mask appears, its step count is the answer. The state count is n × 2^n, and the seen set is what keeps the search from re-exploring states it has already been to.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover the full runtime of the shortest path pattern. Start with BFS layers on the tree, move through grid BFS, then Dijkstra’s heap, then the Bellman-Ford budget version, then the all-pairs matrix, and finish with the two state-heavy hard problems. The progression closes the gap between “I can implement Dijkstra” and “I can spot the shortest path problem inside a word problem”.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .