Watch 10 video solutions for Shortest Path with Alternating Colors, a medium level problem involving Breadth-First Search, Graph. This walkthrough by NeetCodeIO has 18,400 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, andblueEdges[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 <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= ai, bi, uj, vj < nProblem 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 | Time | Space | When to Use |
|---|---|---|---|
| BFS with State Tracking | O(n + r + b) | O(n) | General solution for alternating edge constraints; clean and commonly expected in interviews |
| Layered BFS with Two Queues | O(n + r + b) | O(n) | Useful when separating states by edge color improves clarity or simplifies implementation |