Shortest Path with Alternating Colors

Shortest Path with Alternating Colors

What is this problem about?

The Shortest Path with Alternating Colors interview question gives you a directed graph with edges colored either red or blue. Find the shortest path from node 0 to every other node using paths where edge colors strictly alternate (red-blue-red-blue... or blue-red-blue-red...). If a node is unreachable via any alternating-color path, return -1 for that node.

Why is this asked in interviews?

Sprinklr, Microsoft, and Amazon ask this problem because it tests BFS with edge-color state augmentation — a clean extension of standard BFS where the state includes both the current node AND the last edge color used. This models real-world alternating-constraint routing: time-division multiplexed networks, alternating protocol communication, and multi-layer network path validation.

Algorithmic pattern used

The pattern is BFS with state (node, last_color). Initialize the queue with (0, RED) and (0, BLUE) at distance 0 (node 0 is reachable from itself with either color as the next edge). For each state, traverse only edges of the OPPOSITE color. Mark visited states as (node, color) — not just (node) — since a node may be reachable with different remaining-color constraints. Track minimum distance for each node across both color entry states.

Example explanation

Graph: red edges 0→1, 1→2. Blue edges 0→2, 2→1.

BFS:

• Start: (0, R, dist=0), (0, B, dist=0).
• From (0,R): take blue edges from 0 → (2,B,dist=1).
• From (0,B): take red edges from 0 → (1,R,dist=1).
• From (1,R): take blue edges from 1 → none. From (2,B): take red edges from 2 → (1,R,dist=2). But (1,R) already visited.
• From (2,B): take red... from (1,R, dist=1): blue from 1 → none.

Result: node 0=0, node 1=1, node 2=1.

Common mistakes candidates make

• Using BFS state (node) only — without color state, nodes reachable only via a specific alternating sequence are missed.
• Not initializing BFS with both starting colors (RED and BLUE) — the path can begin with either color as the first edge.
• Treating undirected edges as directed — the problem uses directed edges; don't traverse edges in reverse.
• Marking a node as globally visited after first reach, blocking alternate-color paths that arrive later.

Interview preparation tip

For the Shortest Path with Alternating Colors coding problem, the BFS graph interview pattern with state augmentation is the approach. The state (node, last_color) is the critical extension — it allows BFS to correctly track which edges can be traversed next. Microsoft and Amazon interviewers test whether candidates immediately identify the need for color in the state. Practice augmented-state BFS — it generalizes to any graph traversal where transitions depend on historical context (last move, remaining resources, etc.).