LeetCode Solutions Blog

Shortest Path with Alternating Colors

Number: 1229

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Find the shortest path from node 0 to every other node in a directed graph where edges are colored either red or blue. The path must alternate colors between consecutive edges. If no such path exists for a node, return -1 for that node.

Key Insights

Use Breadth-First Search (BFS) to ensure the shortest path is found.
Represent the state as a combination of the current node and the last edge color used.
Maintain two separate adjacency lists for red and blue edges.
Use a visited set to track (node, lastColor) combinations and avoid cycles.
Alternate the color when selecting the next edges in the BFS.

Space and Time Complexity

Time Complexity: O(n + r + b) where n is the number of nodes and r and b are the numbers of red and blue edges, since each state (node with a particular color) is processed once. Space Complexity: O(n + r + b) due to storage of the graph and the visited states used for BFS.

Solution

Use a BFS approach where each queue element contains the node, the distance from the start (node 0), and the last color of the edge that was used to reach this node. Maintain two graphs for red and blue edges. For every node, try to traverse the edges of the opposite color from the color used in the previous step. Mark combinations of nodes and colors as visited to prevent reprocessing. Update the answer array for each node with the smallest number of edges found that satisfy the alternating color requirement.

Code Solutions

from collections import deque, defaultdict

def shortestAlternatingPaths(n, redEdges, blueEdges):
    # Build two separate graphs for red and blue edges.
    graph = {'red': defaultdict(list), 'blue': defaultdict(list)}
    for u, v in redEdges:
        graph['red'][u].append(v)
    for u, v in blueEdges:
        graph['blue'][u].append(v)
    
    # Initialize the answer list; distance to starting node 0 is 0.
    answer = [-1] * n
    answer[0] = 0
    
    # BFS queue: store tuples (node, distance, lastColor)
    queue = deque([(0, 0, None)])
    visited = set()  # (node, lastColor) to avoid processing the same state multiple times
    
    while queue:
        current, dist, last_color = queue.popleft()
        # Try both colors; if last_color is defined, skip the same color.
        for color in ['red', 'blue']:
            if color == last_color:
                continue
            for neighbor in graph[color].get(current, []):
                if (neighbor, color) not in visited:
                    visited.add((neighbor, color))
                    if answer[neighbor] == -1:
                        answer[neighbor] = dist + 1
                    queue.append((neighbor, dist + 1, color))
    
    return answer

# Example usage:
if __name__ == "__main__":
    n = 3
    redEdges = [[0,1],[1,2]]
    blueEdges = []
    print(shortestAlternatingPaths(n, redEdges, blueEdges))