Shortest Path with Alternating Colors: Modified BFS Pattern

You are given a directed graph with n nodes labeled 0 to n - 1. Some edges are colored red and some are colored blue. You start at node 0 and want to find the shortest path to every other node, with one constraint: consecutive edges in the path must alternate in color. Return an array answer where answer[i] is the length of the shortest alternating-color path from node 0 to node i, or -1 if no such path exists.

This is LeetCode 1129: Shortest Path with Alternating Colors, and it is one of the cleanest examples of BFS with an expanded state. The technique it teaches, tracking extra information in your BFS state to enforce path constraints, appears in many graph problems where you cannot simply visit each node once.

Red edge

Blue edge

Why this problem matters

Standard BFS visits each node once and finds the shortest path in an unweighted graph. But what happens when the "shortest path" has a constraint? In this problem, you cannot take two red edges in a row or two blue edges in a row. A node might be reachable in 2 steps via a red-blue path but also reachable in 3 steps via a blue-red-blue path. You need to track which color you arrived with, not just whether you visited the node.

This "expanded state" BFS pattern shows up whenever the graph has constraints beyond simple reachability. Problems involving turns, fuel limits, or alternating conditions all use the same idea: your BFS state is not just the node, but the node plus the constraint variable.

The key insight

Instead of tracking visited[node], you track visited[node][last_color]. A node can be visited twice: once arriving via a red edge and once arriving via a blue edge. This means your BFS state is (node, last_color_used), and you only enqueue states you have not seen before.

From the source node 0, you have no "last color," so you can take either a red or a blue edge as the first step. After that, each step must use the opposite color of the previous one.

The algorithm:

1. Build two adjacency lists, one for red edges and one for blue edges.
2. Initialize BFS with (0, none) at distance 0. The source can start with either color.
3. For each state (node, last_color), explore edges of the opposite color. If (neighbor, new_color) has not been visited, enqueue it with distance + 1.
4. The first time you reach a node (regardless of which color you arrived with), record that distance as the answer. If a node is reached again via the other color at a longer distance, it does not improve the answer.

The solution

from collections import deque, defaultdict

def shortest_alternating_paths(n: int, red_edges: list[list[int]], blue_edges: list[list[int]]) -> list[int]:
    red_graph = defaultdict(list)
    blue_graph = defaultdict(list)

    for u, v in red_edges:
        red_graph[u].append(v)
    for u, v in blue_edges:
        blue_graph[u].append(v)

    answer = [-1] * n
    answer[0] = 0

    visited = set()
    visited.add((0, 0))
    visited.add((0, 1))

    queue = deque()
    queue.append((0, -1, 0))

    while queue:
        node, last_color, dist = queue.popleft()

        if last_color != 0:
            for neighbor in red_graph[node]:
                if (neighbor, 0) not in visited:
                    visited.add((neighbor, 0))
                    if answer[neighbor] == -1:
                        answer[neighbor] = dist + 1
                    queue.append((neighbor, 0, dist + 1))

        if last_color != 1:
            for neighbor in blue_graph[node]:
                if (neighbor, 1) not in visited:
                    visited.add((neighbor, 1))
                    if answer[neighbor] == -1:
                        answer[neighbor] = dist + 1
                    queue.append((neighbor, 1, dist + 1))

    return answer

Let's walk through the key design decisions.

We use -1 as the initial last_color for the source node, meaning "no color used yet." This lets the source explore both red and blue edges on the first step. After that, color 0 means "last edge was red" and color 1 means "last edge was blue."

The visited set stores (node, color) pairs. This is the critical difference from standard BFS. A node can appear in the queue twice, once for each arrival color. But each (node, color) pair is processed at most once, so the algorithm terminates.

We record the answer for a node the first time we reach it. Because BFS explores in order of increasing distance, the first arrival is guaranteed to be the shortest. Later arrivals via the other color might reach the same node, but they cannot have a shorter distance.

Visual walkthrough

Let's trace BFS on the example graph with n = 4, red edges [[0,1], [1,2], [2,3]], and blue edges [[0,2], [1,3]].

Notice how the BFS explores states, not just nodes. Node 3 is reached twice: once from (1, red) via a blue edge, and once from (2, blue) via a red edge. Both arrivals happen at distance 2. The first one to arrive sets the answer, and the second is still enqueued but does not change anything. This is the power of the expanded state: you never miss a valid alternating path because you track which color you came from.

Complexity analysis

Time is O(n + E) where E is the total number of edges (red + blue). Each (node, color) state is processed at most once, and there are at most 2n states. For each state, you iterate over the adjacency list of the opposite color. The total work across all states is proportional to the number of edges.

Space is O(n + E). The adjacency lists store all edges. The visited set holds at most 2n entries. The queue holds at most 2n entries. The answer array has n entries.

The building blocks

1. Expanded-state BFS

The core technique: when a simple visited[node] set is not enough to enforce your constraint, expand the state to (node, constraint_variable). This transforms a constrained shortest-path problem into a standard BFS on a larger state space.

visited = set()
queue = deque()
queue.append((start_node, initial_constraint, 0))
visited.add((start_node, initial_constraint))

while queue:
    node, constraint, dist = queue.popleft()
    for neighbor, new_constraint in get_valid_transitions(node, constraint):
        if (neighbor, new_constraint) not in visited:
            visited.add((neighbor, new_constraint))
            queue.append((neighbor, new_constraint, dist + 1))

You will reuse this pattern in problems like "Shortest Path to Get All Keys" (LeetCode 864), where the state is (position, keys_held), and "Open the Lock" (LeetCode 752), where the state is a 4-digit combination. The idea is always the same: define your state, enumerate transitions, and let BFS find the shortest path.

2. Dual adjacency lists for colored edges

When edges have categories (colors, types, weights), build separate data structures for each category so you can selectively traverse:

red_graph = defaultdict(list)
blue_graph = defaultdict(list)

for u, v in red_edges:
    red_graph[u].append(v)
for u, v in blue_edges:
    blue_graph[u].append(v)

This separation makes the alternating constraint easy to enforce. When your last color was red, you only look at blue_graph[node]. When it was blue, you only look at red_graph[node]. No filtering or conditional checks are needed inside the BFS loop.

3. First-arrival recording

In BFS, the first time you reach a node is always via the shortest path. You can use this property to simplify your answer tracking:

if answer[neighbor] == -1:
    answer[neighbor] = dist + 1

This check ensures you only record the distance once per node, even though the node might be reached multiple times via different color states. It is a common pattern in multi-state BFS problems where you care about the minimum distance across all states.

Edge cases

Before submitting, think through these scenarios:

• No edges at all: every node except 0 gets -1. Node 0 always has distance 0.
• Self-loops: a red edge [0, 0] creates a self-loop. This is valid but does not help reach other nodes faster. The visited set prevents infinite loops.
• Parallel edges of different colors: red edge [0, 1] and blue edge [0, 1]. Node 1 is reachable in 1 step via either color. Both states (1, red) and (1, blue) get enqueued, which matters for extending paths beyond node 1.
• Node only reachable via one color: if all edges into a node are red, you can only reach it after a blue edge. If no blue edge leads to a predecessor, the node may be unreachable.
• Single node (n = 1): the answer is [0]. No edges to traverse.

From understanding to recall

You have seen how expanded-state BFS works: add (node, last_color) to your state, build dual adjacency lists, and let BFS do the rest. The logic is clean and the code is short. But reproducing it under interview pressure requires remembering specific details. Do you use -1 or None for the initial color? Do you check answer[neighbor] == -1 before or after enqueueing? Do you add (0, 0) and (0, 1) to visited at the start, or just (0, -1)?

These are not conceptual gaps. They are recall gaps, and spaced repetition is how you close them. You practice writing the dual adjacency list construction, the expanded-state BFS loop, and the first-arrival check from scratch at increasing intervals. After a few rounds, you see "alternating constraint" in a problem description and the BFS template flows out without hesitation.

Related posts

• Rotting Oranges - Multi-source BFS on a grid, the foundational BFS pattern this problem builds on
• Network Delay Time - Dijkstra's algorithm for weighted shortest paths, the weighted cousin of this unweighted BFS
• Course Schedule - Graph traversal with topological sort, another core graph BFS/DFS pattern

CodeBricks breaks Shortest Path with Alternating Colors into its expanded-state BFS and dual adjacency list building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained BFS problem shows up in your interview, you do not think about it. You just write it.