Shortest Path with Alternating Colors
MediumUpdated: Jul 29, 2025
Practice on:
Problem
You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to node 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 nodeaito nodebiin the graph, andblueEdges[j] = [uj, vj]indicates that there is a directed blue edge from nodeujto nodevjin 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.
Examples
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]
Solution
Method 1 - BFS with Color State
Intuition
The shortest path with alternating colors can be found using BFS, but we must track the color of the last edge used to ensure alternation. By exploring both red and blue edges from each node, and keeping track of the color used to reach each node, we avoid revisiting the same state and ensure the shortest path is found.
Approach
- Build two adjacency lists: one for red edges and one for blue edges.
- Use a queue for BFS, where each state is (node, last_color). Start from node 0 with both colors.
- Track visited states as (node, color) to avoid cycles.
- For each node, try to traverse edges of the opposite color from the last edge used.
- Record the shortest distance to each node for both colors, and at the end, take the minimum for each node.
- If a node is unreachable, return -1 for that node.
Code
C++
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
vector<vector<int>> red(n), blue(n);
for (auto& e : redEdges) red[e[0]].push_back(e[1]);
for (auto& e : blueEdges) blue[e[0]].push_back(e[1]);
vector<vector<int>> dist(n, vector<int>(2, 1e9));
queue<pair<int, int>> q;
dist[0][0] = dist[0][1] = 0;
q.push({0, 0}); // 0: red, 1: blue
q.push({0, 1});
while (!q.empty()) {
auto [u, c] = q.front(); q.pop();
auto& next = c == 0 ? blue : red;
for (int v : next[u]) {
if (dist[v][1-c] == 1e9) {
dist[v][1-c] = dist[u][c] + 1;
q.push({v, 1-c});
}
}
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
int d = min(dist[i][0], dist[i][1]);
ans[i] = d == 1e9 ? -1 : d;
}
return ans;
}
};
Go
type pair struct{u, c, d int}
func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
red := make([][]int, n)
blue := make([][]int, n)
for _, e := range redEdges { red[e[0]] = append(red[e[0]], e[1]) }
for _, e := range blueEdges { blue[e[0]] = append(blue[e[0]], e[1]) }
dist := make([][2]int, n)
for i := range dist { dist[i][0], dist[i][1] = 1e9, 1e9 }
dist[0][0], dist[0][1] = 0, 0
q := []pair{{0,0,0},{0,1,0}}
for len(q) > 0 {
p := q[0]; q = q[1:]
next := red
if p.c == 0 { next = blue }
for _, v := range next[p.u] {
if dist[v][1-p.c] == 1e9 {
dist[v][1-p.c] = p.d + 1
q = append(q, pair{v,1-p.c,p.d+1})
}
}
}
ans := make([]int, n)
for i := range ans {
d := dist[i][0]
if dist[i][1] < d { d = dist[i][1] }
if d == 1e9 { ans[i] = -1 } else { ans[i] = d }
}
return ans
}
Java
class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
List<Integer>[] red = new List[n], blue = new List[n];
for (int i = 0; i < n; ++i) red[i] = new ArrayList<>();
for (int i = 0; i < n; ++i) blue[i] = new ArrayList<>();
for (int[] e : redEdges) red[e[0]].add(e[1]);
for (int[] e : blueEdges) blue[e[0]].add(e[1]);
int[][] dist = new int[n][2];
for (int[] d : dist) Arrays.fill(d, Integer.MAX_VALUE);
dist[0][0] = dist[0][1] = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0,0});
q.offer(new int[]{0,1});
while (!q.isEmpty()) {
int[] cur = q.poll();
int u = cur[0], c = cur[1];
List<Integer>[] next = c == 0 ? blue : red;
for (int v : next[u]) {
if (dist[v][1-c] == Integer.MAX_VALUE) {
dist[v][1-c] = dist[u][c] + 1;
q.offer(new int[]{v,1-c});
}
}
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int d = Math.min(dist[i][0], dist[i][1]);
ans[i] = d == Integer.MAX_VALUE ? -1 : d;
}
return ans;
}
}
Kotlin
class Solution {
fun shortestAlternatingPaths(n: Int, redEdges: Array<IntArray>, blueEdges: Array<IntArray>): IntArray {
val red = Array(n) { mutableListOf<Int>() }
val blue = Array(n) { mutableListOf<Int>() }
for (e in redEdges) red[e[0]].add(e[1])
for (e in blueEdges) blue[e[0]].add(e[1])
val dist = Array(n) { IntArray(2) { Int.MAX_VALUE } }
dist[0][0] = 0; dist[0][1] = 0
val q = ArrayDeque<Pair<Int,Int>>()
q.add(0 to 0); q.add(0 to 1)
while (q.isNotEmpty()) {
val (u, c) = q.removeFirst()
val next = if (c == 0) blue else red
for (v in next[u]) {
if (dist[v][1-c] == Int.MAX_VALUE) {
dist[v][1-c] = dist[u][c] + 1
q.add(v to 1-c)
}
}
}
return IntArray(n) {
val d = minOf(dist[it][0], dist[it][1])
if (d == Int.MAX_VALUE) -1 else d
}
}
}
Python
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
red = [[] for _ in range(n)]
blue = [[] for _ in range(n)]
for u, v in redEdges: red[u].append(v)
for u, v in blueEdges: blue[u].append(v)
dist = [[float('inf')] * 2 for _ in range(n)]
dist[0][0] = dist[0][1] = 0
from collections import deque
q = deque([(0,0),(0,1)])
while q:
u, c = q.popleft()
next_edges = blue if c == 0 else red
for v in next_edges[u]:
if dist[v][1-c] == float('inf'):
dist[v][1-c] = dist[u][c] + 1
q.append((v,1-c))
ans = []
for d0, d1 in dist:
d = min(d0, d1)
ans.append(-1 if d == float('inf') else d)
return ans
Rust
impl Solution {
pub fn shortest_alternating_paths(n: i32, red_edges: Vec<Vec<i32>>, blue_edges: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let mut red = vec![vec![]; n];
let mut blue = vec![vec![]; n];
for e in red_edges { red[e[0] as usize].push(e[1] as usize); }
for e in blue_edges { blue[e[0] as usize].push(e[1] as usize); }
let mut dist = vec![[i32::MAX; 2]; n];
dist[0][0] = 0; dist[0][1] = 0;
let mut q = std::collections::VecDeque::new();
q.push_back((0,0)); q.push_back((0,1));
while let Some((u, c)) = q.pop_front() {
let next = if c == 0 { &blue } else { &red };
for &v in &next[u] {
if dist[v][1-c] == i32::MAX {
dist[v][1-c] = dist[u][c] + 1;
q.push_back((v,1-c));
}
}
}
dist.into_iter().map(|d| {
let m = d[0].min(d[1]);
if m == i32::MAX { -1 } else { m }
}).collect()
}
}
TypeScript
class Solution {
shortestAlternatingPaths(n: number, redEdges: number[][], blueEdges: number[][]): number[] {
const red: number[][] = Array.from({length: n}, () => []);
const blue: number[][] = Array.from({length: n}, () => []);
for (const [u, v] of redEdges) red[u].push(v);
for (const [u, v] of blueEdges) blue[u].push(v);
const dist: number[][] = Array.from({length: n}, () => [Infinity, Infinity]);
dist[0][0] = dist[0][1] = 0;
const q: [number, number][] = [[0,0],[0,1]];
while (q.length) {
const [u, c] = q.shift()!;
const next = c === 0 ? blue : red;
for (const v of next[u]) {
if (dist[v][1-c] === Infinity) {
dist[v][1-c] = dist[u][c] + 1;
q.push([v,1-c]);
}
}
}
return dist.map(([d0, d1]) => {
const d = Math.min(d0, d1);
return d === Infinity ? -1 : d;
});
}
}
Complexity
- ⏰ Time complexity:
O(n + e), where n is the number of nodes and e is the total number of edges. Each edge is processed at most once for each color. - 🧺 Space complexity:
O(n + e), for adjacency lists and distance tracking for each node and color.