LeetCode 1129 - Shortest Path with Alternating Colors

LeetCode Problem 1129

Difficulty: 🟡 Medium
Topics: Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem gives us a directed graph with n nodes labeled from 0 to n - 1. Every edge in the graph has a color, either red or blue. The graph is represented using two separate edge lists:

• redEdges, containing all red directed edges
• blueEdges, containing all blue directed edges

We need to compute the shortest path from node 0 to every other node, but with an additional constraint: consecutive edges in the path must alternate colors.

This means:

• If the previous edge was red, the next edge must be blue
• If the previous edge was blue, the next edge must be red

The path length is the number of edges used.

The output is an array answer where:

• answer[i] is the length of the shortest valid alternating-color path from node 0 to node i
• If no valid path exists, the value should be -1

A very important detail is that the starting node has no incoming edge, so the first edge can be either red or blue.

The constraints are relatively small:

• n <= 100
• At most 400 red edges and 400 blue edges

These limits suggest that graph traversal algorithms such as Breadth-First Search are more than efficient enough.

The graph may contain:

• Self-loops
• Parallel edges
• Cycles

These characteristics can easily create infinite traversal loops if visited states are not tracked correctly.

The key subtlety in this problem is that reaching the same node using different last-edge colors represents different states. For example:

• Reaching node 3 via a red edge
• Reaching node 3 via a blue edge

These are not equivalent because they affect which edges may be taken next.

A naive implementation that only tracks visited nodes will incorrectly prune valid paths.

Approaches

Brute Force Approach

A brute-force solution would attempt to explore all possible alternating-color paths starting from node 0.

One possible implementation would use Depth-First Search and recursively try every valid alternating edge sequence. For every node, we could track the shortest valid path discovered so far.

This approach is correct because it eventually enumerates every alternating path configuration. However, it becomes extremely inefficient in graphs with cycles and many branching possibilities.

Since the graph may contain cycles and repeated states, the number of possible alternating paths can grow exponentially. Even with pruning, DFS repeatedly explores redundant states.

The brute-force approach is therefore impractical.

Optimal Approach

The key observation is that this is fundamentally a shortest path problem on an unweighted graph.

Whenever we need the shortest number of edges in an unweighted graph, Breadth-First Search is usually the correct tool because BFS explores nodes level by level.

However, we must slightly redefine what a "state" means.

Normally, BFS state consists only of:

(node)

But here, the legality of future moves depends on the color of the previously used edge.

Therefore, the true state becomes:

(node, last_edge_color)

This allows us to distinguish:

• arriving at node u via a red edge
• arriving at node u via a blue edge

From a state:

(node, RED)

we may only traverse blue edges.

From:

(node, BLUE)

we may only traverse red edges.

BFS guarantees that the first time we reach a state, we have found the shortest path to that state.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^E) in worst case	O(E)	Explores many redundant alternating paths
Optimal BFS	O(V + E)	O(V + E)	Uses BFS with color-aware states

Algorithm Walkthrough

1. Build two adjacency lists, one for red edges and one for blue edges.

We separate edges by color because traversal rules depend on the previous edge color. This makes it easy to retrieve only the allowed next edges. 2. Initialize the result array.

Start with:

result = [-1] * n

The shortest distance to node 0 is always 0. 3. Initialize the BFS queue.

Since the first move may use either color, we start BFS with two states:

• (0, RED)
• (0, BLUE)

These represent that we are currently at node 0, and the next edge must be the opposite color. 4. Maintain a visited set.

The visited state must include both:

• current node
• previous edge color

Otherwise, we may incorrectly skip valid alternating paths. 5. Perform level-order BFS.

BFS naturally explores paths in increasing order of length.

For each state:

• If the previous edge was red, explore blue neighbors
• If the previous edge was blue, explore red neighbors

6. Update shortest distances.

The first time we encounter a node is guaranteed to be the shortest alternating path length because BFS processes states in increasing distance order. 7. Continue until the queue becomes empty.

Any node still marked -1 is unreachable under alternating-color constraints.

Why it works

Breadth-First Search guarantees shortest paths in unweighted graphs because nodes are explored level by level.

By expanding the BFS state to include the previous edge color, we correctly model the alternating constraint. Each BFS layer corresponds to paths of equal length, so the first time a node is reached represents the shortest alternating path to that node.

Python Solution

from collections import deque, defaultdict
from typing import List

class Solution:
    def shortestAlternatingPaths(
        self,
        n: int,
        redEdges: List[List[int]],
        blueEdges: List[List[int]]
    ) -> List[int]:

        RED = 0
        BLUE = 1

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

        for src, dst in redEdges:
            red_graph[src].append(dst)

        for src, dst in blueEdges:
            blue_graph[src].append(dst)

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

        queue = deque([
            (0, RED),
            (0, BLUE)
        ])

        visited = {
            (0, RED),
            (0, BLUE)
        }

        distance = 0

        while queue:

            level_size = len(queue)

            for _ in range(level_size):

                node, prev_color = queue.popleft()

                if result[node] == -1:
                    result[node] = distance

                if prev_color == RED:
                    next_neighbors = blue_graph[node]
                    next_color = BLUE
                else:
                    next_neighbors = red_graph[node]
                    next_color = RED

                for neighbor in next_neighbors:

                    state = (neighbor, next_color)

                    if state in visited:
                        continue

                    visited.add(state)
                    queue.append(state)

            distance += 1

        return result

The implementation begins by constructing two adjacency lists:

• red_graph
• blue_graph

Separating the graphs by color simplifies traversal because we can directly select the correct neighbor list based on the previously used edge color.

The BFS queue stores tuples:

(node, previous_color)

This is essential because reaching the same node with different incoming edge colors creates different future possibilities.

The queue is initialized with both colors at node 0. This effectively allows the first real edge to be either red or blue.

The visited set prevents revisiting identical states and avoids infinite loops in cyclic graphs.

The BFS proceeds level by level. Each BFS level corresponds to path length distance.

For every state:

• If the previous edge was red, we may only traverse blue edges
• If the previous edge was blue, we may only traverse red edges

Whenever a node is first discovered, we record its shortest distance.

Go Solution

package main

import "container/list"

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {

	const (
		RED  = 0
		BLUE = 1
	)

	redGraph := make([][]int, n)
	blueGraph := make([][]int, n)

	for _, edge := range redEdges {
		src, dst := edge[0], edge[1]
		redGraph[src] = append(redGraph[src], dst)
	}

	for _, edge := range blueEdges {
		src, dst := edge[0], edge[1]
		blueGraph[src] = append(blueGraph[src], dst)
	}

	result := make([]int, n)

	for i := range result {
		result[i] = -1
	}

	result[0] = 0

	type State struct {
		node      int
		prevColor int
	}

	queue := list.New()

	queue.PushBack(State{0, RED})
	queue.PushBack(State{0, BLUE})

	visited := make(map[[2]int]bool)

	visited[[2]int{0, RED}] = true
	visited[[2]int{0, BLUE}] = true

	distance := 0

	for queue.Len() > 0 {

		levelSize := queue.Len()

		for i := 0; i < levelSize; i++ {

			front := queue.Front()
			queue.Remove(front)

			current := front.Value.(State)

			node := current.node
			prevColor := current.prevColor

			if result[node] == -1 {
				result[node] = distance
			}

			var neighbors []int
			var nextColor int

			if prevColor == RED {
				neighbors = blueGraph[node]
				nextColor = BLUE
			} else {
				neighbors = redGraph[node]
				nextColor = RED
			}

			for _, neighbor := range neighbors {

				stateKey := [2]int{neighbor, nextColor}

				if visited[stateKey] {
					continue
				}

				visited[stateKey] = true

				queue.PushBack(State{
					node:      neighbor,
					prevColor: nextColor,
				})
			}
		}

		distance++
	}

	return result
}

The Go implementation mirrors the Python logic closely.

Instead of Python tuples, Go uses a State struct to store BFS state information.

The queue is implemented using container/list, which provides efficient front removals for BFS traversal.

Go does not have native tuple hashing like Python, so the visited states are stored using:

map[[2]int]bool

where the array contains:

[node, color]

This provides an efficient and compact representation of visited states.

Worked Examples

Example 1

n = 3
redEdges = [[0,1],[1,2]]
blueEdges = []

Graph

0 --red--> 1 --red--> 2

Since there are no blue edges, we cannot take two consecutive red edges.

Initial State

Queue	Distance	Result
[(0,RED), (0,BLUE)]	0	[0,-1,-1]

BFS Level 0

Process (0, RED):

• Must take blue edge
• None available

Process (0, BLUE):

• Must take red edge
• Reach node 1

Queue becomes:

Queue	Distance
[(1,RED)]	1

Result becomes:

Result
[0,1,-1]

BFS Level 1

Process (1, RED):

• Must take blue edge
• None available

Traversal ends.

Final answer:

[0,1,-1]

Example 2

n = 3
redEdges = [[0,1]]
blueEdges = [[2,1]]

Graph

0 --red--> 1
2 --blue--> 1

Initial State

| Queue | Distance | Result |

|---|---|

| [(0,RED), (0,BLUE)] | 0 | [0,-1,-1] |

BFS Level 0

Process (0, RED):

• Need blue edge
• None available

Process (0, BLUE):

• Need red edge
• Reach node 1

Queue:

Queue	Distance
[(1,RED)]	1

Result:

Result
[0,1,-1]

BFS Level 1

Process (1, RED):

• Need blue edge
• None available

Traversal ends.

Final answer:

[0,1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V + E)	Each state and edge is processed at most once
Space	O(V + E)	Adjacency lists, queue, and visited set

The graph contains at most V nodes and E edges.

Each BFS state is uniquely identified by:

(node, color)

Since there are only two possible colors, the total number of states is at most 2V.

Each edge is examined at most once for each relevant color state, so the total traversal cost remains linear in the size of the graph.

Test Cases

from typing import List

class Solution:
    def shortestAlternatingPaths(
        self,
        n: int,
        redEdges: List[List[int]],
        blueEdges: List[List[int]]
    ) -> List[int]:

        from collections import deque, defaultdict

        RED = 0
        BLUE = 1

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

        for u, v in redEdges:
            red_graph[u].append(v)

        for u, v in blueEdges:
            blue_graph[u].append(v)

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

        queue = deque([(0, RED), (0, BLUE)])
        visited = {(0, RED), (0, BLUE)}

        distance = 0

        while queue:

            for _ in range(len(queue)):

                node, prev_color = queue.popleft()

                if result[node] == -1:
                    result[node] = distance

                if prev_color == RED:
                    neighbors = blue_graph[node]
                    next_color = BLUE
                else:
                    neighbors = red_graph[node]
                    next_color = RED

                for neighbor in neighbors:

                    state = (neighbor, next_color)

                    if state in visited:
                        continue

                    visited.add(state)
                    queue.append(state)

            distance += 1

        return result

sol = Solution()

assert sol.shortestAlternatingPaths(
    3,
    [[0, 1], [1, 2]],
    []
) == [0, 1, -1]  # example 1

assert sol.shortestAlternatingPaths(
    3,
    [[0, 1]],
    [[2, 1]]
) == [0, 1, -1]  # example 2

assert sol.shortestAlternatingPaths(
    1,
    [],
    []
) == [0]  # single node graph

assert sol.shortestAlternatingPaths(
    3,
    [[0, 1]],
    [[1, 2]]
) == [0, 1, 2]  # proper alternation

assert sol.shortestAlternatingPaths(
    3,
    [[0, 1], [1, 2]],
    [[0, 2]]
) == [0, 1, 1]  # direct blue edge shorter

assert sol.shortestAlternatingPaths(
    4,
    [[0, 1], [2, 3]],
    [[1, 2]]
) == [0, 1, 2, 3]  # alternating chain

assert sol.shortestAlternatingPaths(
    3,
    [[0, 0], [0, 1]],
    [[1, 2]]
) == [0, 1, 2]  # self-loop handling

assert sol.shortestAlternatingPaths(
    5,
    [],
    [[0, 1], [1, 2]]
) == [0, 1, -1, -1, -1]  # only blue edges

assert sol.shortestAlternatingPaths(
    3,
    [[0, 1]],
    [[1, 0]]
) == [0, 1, -1]  # cycle handling

assert sol.shortestAlternatingPaths(
    4,
    [[0, 1], [0, 2]],
    [[1, 3], [2, 3]]
) == [0, 1, 1, 2]  # multiple shortest paths

Test Summary

Test	Why
Example 1	Verifies inability to take consecutive same-color edges
Example 2	Verifies unreachable nodes
Single node graph	Smallest possible input
Proper alternation chain	Basic alternating traversal
Direct blue shortcut	Ensures shortest path chosen
Alternating chain length 3	Verifies BFS layering
Self-loop graph	Tests cycle and self-edge handling
Only blue edges	Verifies first edge flexibility
Red-blue cycle	Ensures visited states prevent infinite loops
Multiple shortest paths	Verifies BFS correctness with branching

Edge Cases

One important edge case is a graph containing only one color of edges. For example, if every edge is red, then paths longer than one edge become impossible because alternating colors are required. A naive BFS that ignores color constraints may incorrectly continue traversal. The implementation handles this correctly by explicitly switching required edge colors after every step.

Another critical edge case involves cycles and self-loops. Consider a node with an edge back to itself or a red-blue cycle between two nodes. Without tracking visited states using both node and color, BFS could revisit states indefinitely. The implementation avoids this by storing (node, color) pairs in the visited set.

A third subtle edge case occurs when the same node is reachable using different incoming colors. Reaching node u via a red edge is not equivalent to reaching it via a blue edge because the next valid moves differ. A simplistic visited array indexed only by node would incorrectly discard valid future paths. The solution correctly treats these as separate BFS states.

A final edge case is the starting node itself. Since no edge has been used initially, the first move may legally use either color. The implementation handles this by inserting two initial BFS states:

(0, RED)
(0, BLUE)

This effectively simulates allowing either red or blue as the first actual edge in the path.