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 < nIn #1129 Shortest Path with Alternating Colors, the key challenge is ensuring that consecutive edges in a path alternate between red and blue. A natural way to explore shortest paths in an unweighted graph is Breadth-First Search (BFS), but here we must track the color of the last edge used.
The idea is to represent each state as (node, lastColor). From a node reached via a red edge, you only explore blue edges next, and vice versa. By pushing these states into a BFS queue, you ensure that the first time a node is reached with a valid color sequence corresponds to the shortest alternating path.
To avoid revisiting the same state, maintain a visited[node][color] structure. This ensures the traversal remains efficient while exploring valid alternating transitions. Since BFS processes nodes level by level, it naturally yields the minimum number of steps required to reach each node with alternating colors.
Time Complexity: O(n + e). Space Complexity: O(n + e) due to adjacency lists, queue states, and visited tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search with color state tracking | O(n + e) | O(n + e) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Do a breadth-first search, where the "nodes" are actually (Node, color of last edge taken).
Use a Breadth-First Search (BFS) to traverse the graph, keeping track of the last edge color used (red or blue). This can be done using a queue where each element is a tuple containing the current node, distance traveled, and the color of the edge used to arrive at this node. We need two visited arrays to track if a node has been visited with a red edge or a blue edge to avoid re-processing.
Time Complexity: O(n + redEdges.length + blueEdges.length) - This accounts for the BFS traversal and the construction of adjacency lists.
Space Complexity: O(n) - This is the space required for visited sets and the BFS queue.
1from collections import deque
2
3class Solution:
4 def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
5 adj_red = [[] for _ in range(n)]
6 adj_blue = [[] for _ in range(n)]
7 for u, v in redEdges:
8 adj_red[u].append(v)
9 for u, v in blueEdges:
10 adj_blue[u].append(v)
11
12 answer = [-1] * n
13 answer[0] = 0
14 queue = deque([(0, 0, None)])
15 visited_red = set()
16 visited_blue = set()
17
18 while queue:
19 node, dist, last_color = queue.popleft()
20
21 if last_color != 'red':
22 for nei in adj_red[node]:
23 if nei not in visited_red:
24 visited_red.add(nei)
25 if answer[nei] == -1:
26 answer[nei] = dist + 1
27 queue.append((nei, dist + 1, 'red'))
28
29 if last_color != 'blue':
30 for nei in adj_blue[node]:
31 if nei not in visited_blue:
32 visited_blue.add(nei)
33 if answer[nei] == -1:
34 answer[nei] = dist + 1
35 queue.append((nei, dist + 1, 'blue'))
36
37 return answerThe solution first constructs adjacency lists for red and blue edges. A deque is used for BFS which starts from node 0 with a distance of 0. For each node, it checks the next possible nodes via red or blue edges, ensuring no repeated visits are made using the same edge color. It updates the shortest distance for each node when it is first reached, ensuring paths alternate between red and blue.
This approach involves using two separate BFS queues to handle paths starting with red and blue edges. By maintaining distinct queues for red and blue path exploration, the solution ensures color alternation by construction, processing nodes layer by layer from each starting color queue separately.
Time Complexity: O(n + redEdges.length + blueEdges.length) - The layer processing replicates BFS traversal cost.
Space Complexity: O(n) - Needed for separate visitation states and queue management.
1import java.util.*;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Tracking the previous edge color ensures that the next edge chosen alternates correctly. Without storing this information, the algorithm might incorrectly traverse two edges of the same color in sequence.
Yes, graph traversal problems like this frequently appear in technical interviews at large tech companies. Variations of BFS with state tracking are commonly used to test problem-solving and graph modeling skills.
A queue is used for BFS traversal, along with adjacency lists to represent red and blue edges. Additionally, a visited structure like visited[node][color] helps avoid revisiting the same node with the same previous edge color.
The optimal approach uses Breadth-First Search while tracking the color of the last edge used. Each state is represented as (node, lastColor), ensuring the next step uses the opposite color. This guarantees the shortest alternating path in an unweighted graph.
This Java implementation operates with two BFS queues dedicated for red and blue starting paths. The strategy processes node connections based on the opposite color adjacency list, alternatively updating shortest paths. Each queue contributes towards a layer of nodes processed, ensuring paths alternate colors efficiently with minimized total distances computed.