Shortest Path with Alternating Colors — Problem & Solution
Shortest Path with Alternating Colors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Shortest Path with Alternating Colors is a medium coding problem on breadth-first search and graph, asked in Amazon, Google, Microsoft and Sprinklr interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Graph
- Asked at: Amazon, Google, Microsoft, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A directed graph on n nodes has red edges and blue edges, each given as a list of [from, to] pairs. Edges may repeat, and a red and a blue edge may join the same pair.
Return an array where entry i is the length of the shortest path from node 0 to node i whose edge colours alternate, or -1 if no such path exists.
Example 1
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
Explanation: Reaching node 2 would need two reds in a row.
Example 2
Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
Example 3
Input: n = 3, redEdges = [[0,1]], blueEdges = [[1,2]]
Output: [0,1,2]
Constraints
1 <= n <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= redEdges[i][0], redEdges[i][1], blueEdges[j][0], blueEdges[j][1] < n
Hints for Shortest Path with Alternating Colors
Hint 1
A node's distance alone is not enough state — the colour you arrived by decides what you may use next.
Hint 2
So search over
(node, lastColour)pairs, doubling the state space.Hint 3
Node 0 starts in both states, since the first edge may be either colour.
How to solve Shortest Path with Alternating Colors
Breadth-first search over (node, colour-just-used) states. From a state the only legal moves use the other colour, so the alternation is built into the transition instead of being checked afterwards.
Approach
- Build two adjacency lists, one per colour.
- Seed the queue with
(0, red)and(0, blue), both at distance 0. - From
(u, c)follow edges of colour1 - cto unvisited states. - Each node's answer is the smaller of its two state distances, or
-1if neither was reached.
Why it works
Carrying the colour in the state is what keeps BFS correct here: on the plain node graph the first arrival at a node may leave it in the wrong colour to continue, so plain BFS can report a distance that cannot actually be extended. With the colour in the state each is explored independently, and BFS's layer order still gives shortest distances.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Visiting by node instead of by
(node, colour)throws away the state that matters. - Node 0 answers 0 regardless of colours.
- Duplicate and parallel edges are allowed and change nothing.
Reference solution
Python
from typing import List
from collections import deque
def shortestAlternatingPaths(n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
adj = [[[] for _ in range(n)], [[] for _ in range(n)]]
for u, v in redEdges:
adj[0][u].append(v)
for u, v in blueEdges:
adj[1][u].append(v)
dist = [[-1] * n, [-1] * n]
dist[0][0] = 0
dist[1][0] = 0
q = deque([(0, 0), (0, 1)])
while q:
u, c = q.popleft()
nc = 1 - c
for v in adj[nc][u]:
if dist[nc][v] >= 0:
continue
dist[nc][v] = dist[c][u] + 1
q.append((v, nc))
out = []
for i in range(n):
a, b = dist[0][i], dist[1][i]
if a < 0:
out.append(b)
elif b < 0:
out.append(a)
else:
out.append(min(a, b))
return outJava
public static int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
List<List<List<Integer>>> adj = new ArrayList<>();
for (int c = 0; c < 2; c++) {
List<List<Integer>> side = new ArrayList<>();
for (int i = 0; i < n; i++) side.add(new ArrayList<>());
adj.add(side);
}
for (int[] e : redEdges) adj.get(0).get(e[0]).add(e[1]);
for (int[] e : blueEdges) adj.get(1).get(e[0]).add(e[1]);
int[][] dist = new int[2][n];
for (int c = 0; c < 2; c++) Arrays.fill(dist[c], -1);
dist[0][0] = 0;
dist[1][0] = 0;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[] { 0, 0 });
q.add(new int[] { 0, 1 });
while (!q.isEmpty()) {
int[] cur = q.poll();
int u = cur[0], c = cur[1], nc = 1 - c;
for (int v : adj.get(nc).get(u)) {
if (dist[nc][v] >= 0) continue;
dist[nc][v] = dist[c][u] + 1;
q.add(new int[] { v, nc });
}
}
int[] out = new int[n];
for (int i = 0; i < n; i++) {
int a = dist[0][i], b = dist[1][i];
if (a < 0) out[i] = b;
else if (b < 0) out[i] = a;
else out[i] = Math.min(a, b);
}
return out;
}C++
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
vector<vector<vector<int>>> adj(2, vector<vector<int>>(n));
for (auto& e : redEdges) adj[0][e[0]].push_back(e[1]);
for (auto& e : blueEdges) adj[1][e[0]].push_back(e[1]);
vector<vector<int>> dist(2, vector<int>(n, -1));
dist[0][0] = 0;
dist[1][0] = 0;
vector<pair<int,int>> q = { { 0, 0 }, { 0, 1 } };
for (size_t head = 0; head < q.size(); head++) {
int u = q[head].first, c = q[head].second, nc = 1 - c;
for (int v : adj[nc][u]) {
if (dist[nc][v] >= 0) continue;
dist[nc][v] = dist[c][u] + 1;
q.push_back({ v, nc });
}
}
vector<int> out(n);
for (int i = 0; i < n; i++) {
int a = dist[0][i], b = dist[1][i];
if (a < 0) out[i] = b;
else if (b < 0) out[i] = a;
else out[i] = min(a, b);
}
return out;
}JavaScript
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
var i;
var adj = [[], []];
for (i = 0; i < n; i++) { adj[0].push([]); adj[1].push([]); }
for (i = 0; i < redEdges.length; i++) adj[0][redEdges[i][0]].push(redEdges[i][1]);
for (i = 0; i < blueEdges.length; i++) adj[1][blueEdges[i][0]].push(blueEdges[i][1]);
var dist = [[], []];
for (i = 0; i < n; i++) { dist[0].push(-1); dist[1].push(-1); }
dist[0][0] = 0;
dist[1][0] = 0;
var q = [0, 1];
var head = 0;
while (head < q.length) {
var key = q[head++];
var u = key >> 1, c = key & 1;
var nc = 1 - c;
for (i = 0; i < adj[nc][u].length; i++) {
var v = adj[nc][u][i];
if (dist[nc][v] >= 0) continue;
dist[nc][v] = dist[c][u] + 1;
q.push((v << 1) | nc);
}
}
var out = [];
for (i = 0; i < n; i++) {
var a = dist[0][i], b = dist[1][i];
if (a < 0) out.push(b);
else if (b < 0) out.push(a);
else out.push(a < b ? a : b);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Graph Data Structure