Review and Feedback: Minimum Bridges Between Island Cities

Reference implementation and multiple "almost right" solutions

Problem Recap

You are given n cities labeled from 0 to n−1.
Some pairs of cities are connected by roads, and some pairs are connected by bridges.

• Roads are free to use.

• Each bridge crossing costs 1 token, regardless of direction or distance.

You are also given a starting city start, a destination city target, and an integer k representing how many bridge tokens you have.

You can travel:

• Along any road edge at zero cost, unlimited times.

• Along any bridge edge, but in total you may use at most k bridges on your entire route.

Return the minimum number of steps (edges traversed, roads or bridges) needed to travel from start to target without using more than k bridges. If it is impossible, return -1.

A “step” is traversing a single edge (road or bridge) from one city to a directly connected city.

Input format

• n: integer, number of cities.

• roads: list of pairs [u, v] meaning there is an undirected road between u and v.

• bridges: list of pairs [u, v] meaning there is an undirected bridge between u and v.

• start: integer in [0, n-1].

• target: integer in [0, n-1].

• k: integer, maximum number of bridges you may use.

Assumptions:

• The graph can be disconnected.

• There may be both a road and a bridge between the same pair of cities.

• No self-loops are given, but your code should not rely on that.

• Constraints: 1≤n≤10^5, total edges up to 2⋅10^5, 0≤k≤300.

---

Think before you code

1. What is the graph?

   • How will you represent roads and bridges in a single adjacency list?

   • What information do you need for each edge?

2. What is a state?

   • Is “I am at city 7” enough, or do you also need to know something about how you got there?

   • When are two visits to the same city considered different?

3. What algorithm pattern fits?

   • Every move (road or bridge) costs exactly 1 step. Does this sound weighted or unweighted?

   • Between BFS and DFS, which one naturally gives you a shortest number of steps in an unweighted graph, and why?

4. How big is the state space?

   • Suppose your state is (city, usedBridges). How many such states are possible in the worst case?

   • What does that imply for time and space complexity?

5. Where can this go wrong?

   • If you only track visited[city], what kinds of valid paths might you accidentally prune?

   • Try to construct a small example where that mistake returns -1 even though a valid path exists.

---

Polished reference solution (Python, BFS)

from collections import deque
from typing import List, Tuple

ROAD = 0
BRIDGE = 1

def min_steps_with_bridges(
    n: int,
    roads: List[Tuple[int, int]],
    bridges: List[Tuple[int, int]],
    start: int,
    target: int,
    k: int
) -> int:
    # Build adjacency list: (neighbor, edge_type)
    adj: List[List[Tuple[int, int]]] = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append((v, ROAD))
        adj[v].append((u, ROAD))
    for u, v in bridges:
        adj[u].append((v, BRIDGE))
        adj[v].append((u, BRIDGE))

    # visited[city][used_bridges] = have we reached this state?
    visited = [[False] * (k + 1) for _ in range(n)]

    q = deque()
    q.append((start, 0, 0))  # (city, used_bridges, distance)
    visited[start][0] = True

    while q:
        city, used, dist = q.popleft()

        if city == target:
            return dist

        for nei, edge_type in adj[city]:
            next_used = used + (1 if edge_type == BRIDGE else 0)
            if next_used <= k and not visited[nei][next_used]:
                visited[nei][next_used] = True
                q.append((nei, next_used, dist + 1))

    return -1

• The graph is represented as adj[city] = list of (neighbor, type) where type distinguishes roads and bridges.

• The state for BFS is (city, used_bridges); we track dist separately for convenience.

• BFS over this expanded state space guarantees the shortest number of steps in an unweighted graph.

• visited[city][used] ensures we do not revisit the same state, while still allowing revisits to the same city with different bridge usage.

---

Polished Java version (for readers who prefer Java)

import java.util.*;

public class MinStepsWithBridges {

    private static final int ROAD = 0;
    private static final int BRIDGE = 1;

    public static int minStepsWithBridges(
            int n,
            List<int[]> roads,
            List<int[]> bridges,
            int start,
            int target,
            int k
    ) {
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int[] e : roads) {
            int u = e[0], v = e[1];
            adj[u].add(new int[]{v, ROAD});
            adj[v].add(new int[]{u, ROAD});
        }

        for (int[] e : bridges) {
            int u = e[0], v = e[1];
            adj[u].add(new int[]{v, BRIDGE});
            adj[v].add(new int[]{u, BRIDGE});
        }

        boolean[][] visited = new boolean[n][k + 1];
        Queue<int[]> q = new ArrayDeque<>();
        // state: {city, usedBridges, distance}
        q.offer(new int[]{start, 0, 0});
        visited[start][0] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int city = cur[0];
            int used = cur[1];
            int dist = cur[2];

            if (city == target) {
                return dist;
            }

            for (int[] edge : adj[city]) {
                int nei = edge[0];
                int type = edge[1];
                int nextUsed = used + (type == BRIDGE ? 1 : 0);

                if (nextUsed <= k && !visited[nei][nextUsed]) {
                    visited[nei][nextUsed] = true;
                    q.offer(new int[]{nei, nextUsed, dist + 1});
                }
            }
        }

        return -1;
    }
}

This follows the standard BFS template described in many interview resources for shortest paths in unweighted graphs.

---

Weaker solution 1: Wrong visited definition

This is the mistake most people make first: they track visited only per city.

from collections import deque

def min_steps_wrong_visited(
    n, roads, bridges, start, target, k
):
    ROAD, BRIDGE = 0, 1
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append((v, ROAD))
        adj[v].append((u, ROAD))
    for u, v in bridges:
        adj[u].append((v, BRIDGE))
        adj[v].append((u, BRIDGE))

    visited = [False] * n  # <== only per city
    q = deque()
    q.append((start, 0, 0))  # city, used_bridges, dist
    visited[start] = True

    while q:
        city, used, dist = q.popleft()
        if city == target:
            return dist

        for nei, edge_type in adj[city]:
            next_used = used + (1 if edge_type == BRIDGE else 0)
            if next_used <= k and not visited[nei]:
                visited[nei] = True
                q.append((nei, next_used, dist + 1))

    return -1

Why it’s wrong:

• This approach treats “I reached city 5 with 0 bridges used” and “I reached city 5 with 3 bridges used” as the same situation.

• In reality, the first is strictly better: you have more flexibility for the rest of the path.

• Because it sets visited[nei] = True regardless of bridge usage, it can prune away valid solutions.

---

Weaker solution 2: DFS backtracking instead of BFS

This version uses DFS with pruning; it can work on small inputs but doesn’t naturally guarantee shortest paths or good performance.

def min_steps_dfs_wrong(
    n, roads, bridges, start, target, k
):
    ROAD, BRIDGE = 0, 1
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append((v, ROAD))
        adj[v].append((u, ROAD))
    for u, v in bridges:
        adj[u].append((v, BRIDGE))
        adj[v].append((u, BRIDGE))

    best = [float('inf')]
    visited = set()  # tracks only city

    def dfs(city, used, dist):
        if dist >= best[0]:
            return
        if used > k:
            return
        if city == target:
            best[0] = min(best[0], dist)
            return

        visited.add(city)
        for nei, edge_type in adj[city]:
            if nei in visited:
                continue
            dfs(nei,
                used + (1 if edge_type == BRIDGE else 0),
                dist + 1)
        visited.remove(city)

    dfs(start, 0, 0)
    return -1 if best[0] == float('inf') else best[0]

• DFS explores one path deeply before trying alternatives, so you can easily walk a long suboptimal path before discovering a shorter one elsewhere.

• The pruning condition dist >= best[0] only works once best[0] is set; until then you might do a ton of unnecessary work.

• This still uses a “city-only” visited set, so it conflates different resource usages just like the first weak solution.

---

Weaker solution 3: Correct but potential state explosion / timeouts

from collections import deque

def min_steps_slow(
    n, roads, bridges, start, target, k
):
    ROAD, BRIDGE = 0, 1
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append((v, ROAD))
        adj[v].append((u, ROAD))
    for u, v in bridges:
        adj[u].append((v, BRIDGE))
        adj[v].append((u, BRIDGE))

    visited = set()
    q = deque()
    q.append((start, 0, 0))  # city, used_bridges, dist
    visited.add((start, 0))

    while q:
        city, used, dist = q.popleft()
        if city == target:
            return dist

        for nei, edge_type in adj[city]:
            next_used = used + (1 if edge_type == BRIDGE else 0)
            if next_used <= k:
                state = (nei, next_used)
                if state not in visited:
                    visited.add(state)
                    q.append((nei, next_used, dist + 1))

    return -1

• This uses the right state (city, usedBridges) and is functionally correct.

• However, because it doesn’t do any additional dominance pruning (e.g., recognizing that reaching (city, used=1) makes (city, used=2) uninteresting for the same or longer distance), it may explore more states than necessary when k is large.

---

Tying everything together

At first glance, this problem looks like a standard shortest-path question on an unweighted graph. Every move—road or bridge—costs exactly one step, so the natural tool is breadth-first search (BFS), which is known to find shortest paths in unweighted graphs in O(n+m) time.courses.

The twist is the bridge budget k. Reaching a city is no longer a single event; it matters how many bridges you’ve spent getting there. Reaching city 5 after using 0 bridges is strictly better than reaching city 5 after using 3. To capture this, our BFS state is not just city, but (city, usedBridges).

Once we make that modeling decision, everything else falls into place. Our graph of states has at most n * (k + 1) nodes—each original city, expanded across all possible usedBridges values from 0 to k. From a state (city, used) we push neighbors:

• If the edge is a road, we move to (neighbor, used).

• If the edge is a bridge, we move to (neighbor, used + 1) as long as used + 1 ≤ k.

Now we can run a completely standard BFS on this expanded graph. We initialize the queue with (start, 0, 0) where the third component is the number of steps so far. We keep a visited[city][usedBridges] table so we never re-enqueue the same state twice. Because every transition costs exactly 1 step, BFS’s level-order property guarantees that the first time we pop a state whose city == target, we’ve reached it with the minimum possible number of steps.

The first weak solution illustrates a classic pitfall: tracking visited only per city. That works when the only thing that matters is which node you’re in, but breaks as soon as there’s an extra resource dimension like “bridges used,” “walls broken,” or “keys collected.” By marking visited[city] = True unconditionally, that solution may discard a later visit to the same city with fewer bridges spent, even though that later visit might lead to the only feasible path to the target.

The DFS variant shows a different kind of mistake: choosing the wrong traversal pattern. DFS explores one path to the bitter end before trying alternatives, so it’s a poor fit for shortest-path problems in general graphs. You can try to patch it with a global best distance and pruning, but there’s no structural guarantee that you’ll explore paths in increasing-length order. On larger inputs, this degenerates into expensive backtracking with fragile heuristics, which is exactly why most interview references recommend BFS (or Dijkstra, for weighted graphs) for shortest paths.

Finally, the “slow but correct” BFS reminds us that correctness is only part of the story. It uses the right state and will produce the right answer, but a naive state-space treatment can be unnecessarily heavy. Thinking about the size and structure of your state space—how many distinct (city, usedBridges) pairs exist, and which ones are actually worth exploring—is an important part of designing scalable graph algorithms. This is the same kind of reasoning that leads from plain BFS to 0–1 BFS or more general resource-constrained shortest path algorithms in advanced settings.

Taken together, these versions trace a progression that’s common in strong interview performances: first get the modeling right, then choose the right traversal pattern, and finally reason about the complexity of the state space, not just the graph’s raw node count.