Skip to main content
Talentd

Shortest Path with Alternating Colors - Solution & Explanation

MediumBreadth-First SearchGraph20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
  • blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj 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 <= ai, bi, uj, vj < n

Approach Overview

Problem Overview: Given a directed graph with red and blue edges, compute the shortest distance from node 0 to every other node such that the path alternates colors at each step. If no alternating path exists, return -1 for that node.

Approach 1: BFS with State Tracking (O(n + r + b) time, O(n) space)

This problem behaves like a shortest path search on a graph where the state includes both the node and the color of the edge used to reach it. Use Breadth-First Search starting from node 0. Instead of marking only nodes as visited, track (node, lastColor) to enforce alternation. Build two adjacency lists for red and blue edges, push both starting states into the queue, and expand only edges of the opposite color. BFS guarantees the first time you reach a node with a valid color sequence is the shortest alternating distance. This approach is simple and works efficiently because each state is processed at most once.

Approach 2: Layered BFS with Two Queues (O(n + r + b) time, O(n) space)

Another way to enforce color alternation is to maintain two queues: one for paths that ended with a red edge and one for paths that ended with a blue edge. During each BFS layer, process nodes from one queue and expand only edges of the opposite color into the other queue. Distances are updated level by level, similar to standard BFS on an unweighted graph. This structure separates transitions clearly and avoids repeatedly checking edge colors inside the same queue. The algorithm still processes each edge at most once per color state, keeping the complexity linear.

Recommended for interviews: BFS with state tracking is the most common interview solution. It directly models the constraint by extending the BFS state to include the previous edge color. Explaining this transition clearly shows you understand how to adapt BFS for constrained shortest-path problems.

Approach 1: BFS with State Tracking

Use a Breadth-First Search (BFS) to traverse the graph, keeping track of the last edge color used (red or blue). This can be done using a queue where each element is a tuple containing the current node, distance traveled, and the color of the edge used to arrive at this node. We need two visited arrays to track if a node has been visited with a red edge or a blue edge to avoid re-processing.

The solution first constructs adjacency lists for red and blue edges. A deque is used for BFS which starts from node 0 with a distance of 0. For each node, it checks the next possible nodes via red or blue edges, ensuring no repeated visits are made using the same edge color. It updates the shortest distance for each node when it is first reached, ensuring paths alternate between red and blue.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n + redEdges.length + blueEdges.length) - This accounts for the BFS traversal and the construction of adjacency lists.
Space Complexity: O(n) - This is the space required for visited sets and the BFS queue.

Try this approach in the editor →

Approach 2: Layered BFS with Two Queues

This approach involves using two separate BFS queues to handle paths starting with red and blue edges. By maintaining distinct queues for red and blue path exploration, the solution ensures color alternation by construction, processing nodes layer by layer from each starting color queue separately.

This Java implementation operates with two BFS queues dedicated for red and blue starting paths. The strategy processes node connections based on the opposite color adjacency list, alternatively updating shortest paths. Each queue contributes towards a layer of nodes processed, ensuring paths alternate colors efficiently with minimized total distances computed.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n + redEdges.length + blueEdges.length) - The layer processing replicates BFS traversal cost.
Space Complexity: O(n) - Needed for separate visitation states and queue management.

Try this approach in the editor →

Approach 3: BFS

The problem is essentially a shortest path problem, which we can consider solving using BFS.

First, we preprocess all the edges, categorizing all the edges by color and storing them in a multi-dimensional array g. Where g[0] stores all red edges, and g[1] stores all blue edges.

Next, we define the following data structures or variables:

  • Queue q: used to store the currently searched node and the color of the current edge;
  • Set vis: used to store the nodes that have been searched and the color of the current edge;
  • Variable d: used to represent the current search level, i.e., the distance from the currently searched node to the starting point;
  • Array ans: used to store the shortest distance from each node to the starting point. Initially, we initialize all elements in the ans array to -1, indicating that the distance from all nodes to the starting point is unknown.

We first enqueue the starting point 0 and the color of the starting edge 0 or 1, indicating that we start from the starting point and the current edge is red or blue.

Next, we start the BFS search. Each time we take out a node (i, c) from the queue, if the answer of the current node has not been updated, then we update the answer of the current node to the current level d, i.e., ans[i] = d. Then, we flip the color of the current edge c, i.e., if the current edge is red, we change it to blue, and vice versa. We take out all edges corresponding to the color, if the other end node j of the edge has not been searched, then we enqueue it.

After the search is over, return the answer array.

The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of nodes and edges, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
BFS with State Tracking

Time Complexity: O(n + redEdges.length + blueEdges.length) - This accounts for the BFS traversal and the construction of adjacency lists.
Space Complexity: O(n) - This is the space required for visited sets and the BFS queue.

Layered BFS with Two Queues

Time Complexity: O(n + redEdges.length + blueEdges.length) - The layer processing replicates BFS traversal cost.
Space Complexity: O(n) - Needed for separate visitation states and queue management.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with State TrackingO(n + r + b)O(n)General solution for alternating edge constraints; clean and commonly expected in interviews
Layered BFS with Two QueuesO(n + r + b)O(n)Useful when separating states by edge color improves clarity or simplifies implementation

Video Solution

Shortest Path with Alternating Colors - Leetcode 1129 - Python • NeetCodeIO • 19,055 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Shortest Path with Alternating Colors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Same Tree

Next

Symmetric Tree