758. Alternating Colour Routes
A theme park has n rides numbered 0 to n - 1 joined by one-way lanes of two paint colours. Every pair [a, b] in redEdges is a red lane from ride a to ride b, and every pair in blueEdges is a blue lane. Lanes may repeat and may loop back to the same ride.
A guest starts at ride 0 and wants to reach each ride using lanes whose colours strictly alternate, so two lanes of the same colour can never be taken one after the other. The first lane may be either colour.
Return an array answer of length n where answer[i] is the smallest number of lanes on such a trip from ride 0 to ride i, or -1 if no alternating trip exists. answer[0] is always 0.
Example 1
- Input:
- n = 4, redEdges = [[0,1],[2,3]], blueEdges = [[1,2]]
- Output:
- [0,1,2,3]
- Explanation:
Walk 0 to 1 on a red lane, then 1 to 2 on a blue lane, then 2 to 3 on a red lane, so the distances are 0, 1, 2, 3.
Example 2
- Input:
- n = 4, redEdges = [[0,1],[1,2]], blueEdges = [[3,0]]
- Output:
- [0,1,-1,-1]
- Explanation:
Town 2 needs two red lanes in a row (0 to 1 to 2), which breaks the alternation, and town 3 has no incoming lane, so both answers are -1.
Example 3
- Input:
- n = 3redEdges = [[0,1],[0,2]]blueEdges = [[0,1],[1,2]]
- Output:
- [0,1,1]
- Explanation:
Town 1 and town 2 are each one lane away from town 0 (blue works for 1, red works for 2), so the answer is [0, 1, 1].
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ redEdges.length, blueEdges.length ≤ 2 * 105
- 0 ≤ a, b < n for every lane
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)