Is Shortest Path with Alternating Colors easy or hard?

The problem is rated Medium on LeetCode. The BFS traversal itself is straightforward, but the challenge comes from modeling the alternating color constraint using state tracking or separate queues.

Shortest Path with Alternating Colors Python/Java solution

Most implementations use BFS with a queue and adjacency lists. Python and Java versions maintain a queue of (node, color) states and update distances when a node is first reached with a valid alternating sequence. The same logic works across Python, Java, JavaScript, and C++ with O(n + r + b) complexity.

How to solve Shortest Path with Alternating Colors in O(n)?

Use BFS starting from node 0 and track the previous edge color as part of the state. Build separate adjacency lists for red and blue edges. From a state that ended with a red edge, only explore blue edges next, and vice versa. This ensures each transition respects the alternation rule while BFS guarantees shortest distances.

What is the best approach for Shortest Path with Alternating Colors?

The most effective approach uses Breadth-First Search with state tracking. Each BFS state includes both the node and the color of the last edge used, ensuring the next edge alternates. This guarantees the shortest valid path because BFS explores nodes level by level. The complexity is O(n + r + b), where r and b are the number of red and blue edges.

Is Shortest Path with Alternating Colors asked at Google/Amazon/Meta?

Graph traversal problems using BFS are common at companies like Google, Amazon, and Meta. Variants involving constraints such as alternating edges or multi-state nodes appear in technical interviews because they test understanding of graph modeling and BFS adaptations.

What data structure is used in Shortest Path with Alternating Colors?

The core data structure is a queue used for Breadth-First Search. The graph is stored using adjacency lists for red and blue edges, and a visited structure tracks states like (node, lastEdgeColor). This combination ensures efficient traversal and avoids revisiting invalid states.

What is the time complexity of Shortest Path with Alternating Colors?

The optimal solution runs in O(n + r + b) time. BFS processes each node with two possible states (arrived via red or blue edge), and each edge is explored at most once per valid state. Space complexity is O(n) for the queue and visited states.

Description Hints 1 Solution Video 13:43

1129. Shortest Path with Alternating Colors

Medium48.4% acceptance5 companies

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

redEdges[i] = [a_i, b_i] indicates that there is a directed red edge from node a_i to node b_i in the graph, and
blueEdges[j] = [u_j, v_j] indicates that there is a directed blue edge from node u_j to node v_j in the graph.

Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

Constraints:

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= a_i, b_i, u_j, v_j < n

Asked at 5 companies

Sprinklr Amazon

Google Microsoft Meta

Topics

Breadth-First Search Graph

Hints open one at a time

Hint 1

Do a breadth-first search, where the "nodes" are actually (Node, color of last edge taken).

13:43

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

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

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

3
[[0,1],[1,2]]
[]

Input

3
[[0,1]]
[[2,1]]

Your code is saved on this device.Solution