Shortest Path with Alternating Colors
01 · Problem
You have a directed graph with n nodes labelled 0 to n - 1. Every edge is coloured red or blue. redEdges[i] = [a, b] is a red edge from a to b, and blueEdges[j] = [u, v] is a blue edge from u to v. The graph may contain self-loops and parallel edges.
A path is alternating if no two consecutive edges on it share a colour (red, blue, red, ... or blue, red, blue, ...). The path may start with either colour.
Return an array answer of length n where answer[x] is the number of edges on the shortest alternating path from node 0 to node x, or -1 if no such path exists. answer[0] is always 0.
02 · Examples
n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
[0,1,-1]
Node 1 is reached with one red edge. Reaching node 2 would need two red edges in a row, which is not allowed.
n = 3, redEdges = [[0,1]], blueEdges = [[1,2]]
[0,1,2]
Red 0 -> 1, then blue 1 -> 2 alternates correctly.
n = 4, redEdges = [[0,1],[2,3]], blueEdges = [[1,2],[0,2]]
[0,1,1,2]
Node 1: red 0 -> 1 (1 edge). Node 2: blue 0 -> 2 (1 edge). Node 3: blue 0 -> 2 then red 2 -> 3 (2 edges).
03 · Constraints
- 011 <= n <= 100
- 020 <= redEdges.length, blueEdges.length <= 400
- 03redEdges[i].length == blueEdges[j].length == 2
- 040 <= a, b, u, v < n
04 · Optimal complexity
- Time
- O(n + r + b)
- Space
- O(n + r + b)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.