0-1 BFS Interview Questions: Deque Ordering, Relaxation, and Minimum-Cost Paths

“The route with the fewest edges costs one; a longer route costs zero. Would ordinary BFS find the cheaper one?” That is the central 0-1 BFS interview question. Ordinary BFS minimizes edge count when every edge has the same cost. If weights are only 0 or 1, a deque can process nodes in nondecreasing tentative cost: push a zero-cost improvement to the front and a one-cost improvement to the back. The result is a minimum-cost path without a general priority queue.

This guide uses an original five-node counterexample, a step-by-step deque trace, and a Python oracle check. Evidence boundary: AtCoder's official 0-1 BFS editorial supports the deque method and its shortest-path interpretation. The graph, code, tests, and interview rubric here are original editorial work. No candidate report is used for a process claim.

The graph that breaks ordinary BFS

Let directed edges be S→A with weight 1, S→B with weight 0, B→C with weight 0, C→A with weight 0, and A→T with weight 0. The two-edge route S→A→T costs 1. The four-edge route S→B→C→A→T costs 0. If the objective is minimum total weight, the longer route wins. Plain FIFO BFS can visit A through the direct edge first and, if it marks A visited on discovery, never reconsider the cheaper path through C.

The exercise makes three assumptions explicit. Edges are directed; every weight is exactly 0 or 1; and cost is the sum of weights, not the number of vertices. If an interviewer changes an edge to weight 2, the deque rule no longer has the same guarantee; use Dijkstra for arbitrary nonnegative weights. If a negative edge appears, Dijkstra also becomes invalid and the problem needs a different method or additional structure. Ask those questions before coding.

Notice that a zero-cost edge is not the same as a zero-cost node. A grid problem may say entering a charged cell costs 0 and entering an empty cell costs 1; then the edge weight depends on the destination cell. Decide whether the starting cell's cost is included. A one-cell grid can expose that convention immediately. The graph representation should encode the contract rather than hide it in the traversal.

Trace the deque, not just the final distance

Start with dist[S]=0 and all other distances infinite. Assume S's outgoing edges are considered in the order A, then B.

Pop and relaxation	Deque after updates	Best known distances
Start	[S:0]	S=0
Pop S; add A at back, B at front	[B:0, A:1]	A=1, B=0
Pop B; add C at front	[C:0, A:1]	C=0
Pop C; improve A and add it at front	[A:0, A:1]	A=0
Pop A:0; add T at front	[T:0, A:1]	T=0

The older A:1 entry is stale. The implementation below stores a distance snapshot with each deque entry, so it skips that entry when popped. This is a clean way to explain duplicates. Alternatively, a correct implementation can use a finalized set when popping in nondecreasing order, but never mark a node permanently visited merely when it is first enqueued. The first path discovered to A was not optimal.

The deque invariant gives the algorithm its speed. At any moment, pending entries have costs equal to the current front cost or one greater, aside from stale entries that are ignored. Processing an edge of weight 0 keeps the new candidate at the current cost, so it belongs at the front. Weight 1 puts it in the next cost layer, so it belongs at the back. AtCoder's official editorial describes this deque placement as playing the role of a priority queue for the two allowed edge lengths.

Do not say “zero edges are always explored before one edges” without a reference point. A zero-cost edge from a node at cost 5 is not globally ahead of a one-cost edge from a node at cost 0. The invariant is about total tentative distance as the deque advances. The appendleft/append rule works because only the increment can be zero or one and because lower-distance nodes are processed first.

Implement relaxation correctly

Here is a compact Python implementation for nonnegative integer node IDs. It returns the minimum cost, or None if the target is unreachable. The snapshot check rejects outdated entries after a better path is found.

from collections import deque
from math import inf

def zero_one_bfs(graph, start, target):
    n = len(graph)
    dist = [inf] * n
    dist[start] = 0
    queue = deque([(start, 0)])

    while queue:
        node, queued_cost = queue.popleft()
        if queued_cost != dist[node]:
            continue
        if node == target:
            return queued_cost

        for neighbor, weight in graph[node]:
            if weight not in (0, 1):
                raise ValueError("0-1 BFS requires weights 0 or 1")
            candidate = queued_cost + weight
            if candidate < dist[neighbor]:
                dist[neighbor] = candidate
                if weight == 0:
                    queue.appendleft((neighbor, candidate))
                else:
                    queue.append((neighbor, candidate))

    return None

For the example, use IDs S=0, A=1, B=2, C=3, T=4 and adjacency lists [(1,1),(2,0)], [(4,0)], [(3,0)], [(1,0)], []. The function returns 0. The candidate < dist[neighbor] condition is strict; equal-cost re-enqueues would add work without improving the answer. Checking the weight prevents silent misuse if requirements change.

The early return on pop is sound because the deque processes current best costs in nondecreasing order. An early return when the target is first enqueued can be wrong: the first route to T might later be improved. If you need the full distance map instead of one target, remove the early return and return dist, converting infinite entries to an unreachable marker as the API requires.

The standard 0-1 BFS bound is O(V+E) time and O(V+E) space for adjacency lists plus a deque with possible duplicate entries; for a grid with implicit neighbors, E=O(V). Explain the bound using the two-level ordering and bounded successful relaxations rather than saying “deque operations are O(1), therefore the whole algorithm is O(V).” You still inspect edges and store graph input. In dense directed graphs, E can dominate.

Check it against Dijkstra, not against itself

A good interview test oracle is ordinary Dijkstra with a heap. It solves the same nonnegative-weight shortest-path problem without relying on the deque invariant. Compare results on hand-picked cases: the counterexample above, a zero-cost cycle, unreachable target, parallel 0/1 edges, and a one-node graph. Then enumerate small directed graphs or use a fixed-seed randomized generator to compare many inputs. Two copies of the same 0-1 BFS implementation are a poor oracle because they can share the same mistake.

For the five-node example, plain BFS by edge count returns two hops to T, which is true but answers the wrong objective. A test that asserts the returned cost is 0 catches this. A graph with S→T cost 1 and S→A→T weights 0,0 catches an implementation that returns when T is enqueued. A zero-cost cycle catches an implementation that re-enqueues on equal distances and never stops. A parallel edge with a later cheaper weight catches “visited on enqueue.”

You can reconstruct a path by storing a predecessor whenever a strict relaxation improves a distance. Reconstruct only after the target has been finalized/popped (or after the full run). If equal-cost paths need a stable tie-break, specify it separately; the deque algorithm guarantees minimum cost, not a unique path or fewest edges among equal-cost paths. Edge iteration order may change which optimal path you get.

Convert a grid without an off-by-one cost bug

Suppose a grid cell already has a bridge (1), is empty (0), or is blocked (2). Crossing an existing bridge cell costs 0; filling an empty cell costs 1; a blocked cell cannot be entered. Add directed transitions between allowed orthogonal neighbors with weight equal to the destination cell's fill cost. Seed every allowed top-row cell with its own cost if the goal counts filling the starting cell; then minimize over bottom-row cells. A single-row grid checks whether top and bottom are the same row under the problem's rule.

This is not the same as ordinary shortest path by number of moves. A winding route through existing bridges can be cheaper than a short route requiring several new cells. The 0-1 BFS deque handles that exactly. But a grid with costs 0, 1, and 5 needs Dijkstra; using append for weight 5 loses the two-layer ordering. Before adapting code, state how cell values map to edge weights and whether walls, diagonal moves, or multiple sources exist.

Mistakes to catch in code review

First, appendleft for weight 1 or append for weight 0 reverses the cost layers. Second, using a boolean visited array on enqueue discards later improvements. Third, returning as soon as the target appears in a neighbor list can return a nonoptimal cost. Fourth, treating a grid cell's value as the cost to leave instead of enter shifts the charge to the wrong route, including the destination or start. Fifth, accepting a weight 2 without switching algorithms removes the proof.

Another subtle issue is stale work. An entry for A:1 can remain after A improves to 0. Without the snapshot check, processing it with an obsolete queued distance may enqueue useless paths. If code reads the current dist[A] instead of the stored distance, it may still be correct but do extra work; be explicit about the chosen invariant. Prefer the snapshot pattern because it makes the trace auditable.

For a large implicit graph, do not preconstruct every adjacency list if neighbors can be generated cheaply. Still count the possible edge examinations in complexity. If the target is unreachable, return the contract's sentinel, not inf accidentally serialized to JSON. If the graph can have negative weights or changing edge costs during traversal, this fixed shortest-path model is insufficient; clarify the problem rather than patching the deque.

Fast interview answers to follow-ups

Why not ordinary BFS? FIFO order minimizes hops only under equal edge costs. A longer zero-cost path can beat a short cost-one path.

Why not Dijkstra? Dijkstra works and is a good oracle, but 0/1 weights permit a deque with linear graph work instead of a heap. Choose clarity and constraints over memorized speed claims.

Why push zero to the front? It preserves the current total-distance layer. A one-edge moves to the next layer at the back.

When is a node final? When popped with its current best distance under the deque invariant, not when first discovered. Skip stale entries after improvements.

What if edges cost 0, 1, or 2? This exact two-layer deque proof no longer applies. A bucketed shortest-path method can exploit small bounded integer weights, or use Dijkstra for a straightforward correct answer.

Sources and further reading

• AtCoder official editorial: Bishop 2 and 0-1 BFS
• AtCoder official editorial: 0-1 BFS on a maze
• AtCoder official editorial: Wizard in Maze and two-cost movement