We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Path with Alternating Colors

Difficulty: Medium

Problem Description

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] = [a_i, b_i] indicates that there is a directed red edge from node a_i to node b_i in the graph, and
  • blueEdges[j] = [u_j, v_j] indicates that there is a directed blue edge from node u_j to node v_j 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.

Key Insights

  • The graph contains directed edges of two colors (red and blue), and paths must alternate colors.
  • BFS (Breadth-First Search) is suitable for finding the shortest path in an unweighted graph.
  • Use a queue to explore nodes level by level while keeping track of the color of the last edge used to reach each node.
  • Maintain two distances for each node: one for the last edge being red and another for blue.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of nodes and m is the total number of edges (red + blue). Space Complexity: O(n), for storing distances and the queue.

Solution

We will use a Breadth-First Search (BFS) approach to explore the graph. We'll maintain a queue that stores pairs of nodes and the color of the last edge used to reach them. At each step, we'll check the possible edges that can be taken (red or blue) and update the distance if a shorter path is found.

We'll initialize the queue with the starting node (0) and the two possible starting colors (red and blue). As we process nodes from the queue, we'll add adjacent nodes of the opposite color to the queue, marking their distance if they haven't been visited yet.

Code Solutions

from collections import deque, defaultdict

def shortestAlternatingPaths(n, redEdges, blueEdges):
    # Create adjacency lists for red and blue edges
    red_graph = defaultdict(list)
    blue_graph = defaultdict(list)
    
    for u, v in redEdges:
        red_graph[u].append(v)
        
    for u, v in blueEdges:
        blue_graph[u].append(v)
    
    # Distance array initialized to -1
    answer = [-1] * n
    answer[0] = 0  # Distance to start node is 0
    
    # Queue for BFS: (node, color, distance)
    queue = deque([(0, 'R', 0), (0, 'B', 0)])  # Start with both colors
    
    # Visited nodes with last edge color (0 for red, 1 for blue)
    visited = [[False, False] for _ in range(n)]
    visited[0][0] = visited[0][1] = True
    
    while queue:
        node, color, dist = queue.popleft()
        
        # Explore neighbors
        if color == 'R':
            for neighbor in blue_graph[node]:
                if not visited[neighbor][1]:  # If last edge was blue
                    visited[neighbor][1] = True
                    if answer[neighbor] == -1:  # Update distance if not set
                        answer[neighbor] = dist + 1
                    queue.append((neighbor, 'B', dist + 1))
        else:
            for neighbor in red_graph[node]:
                if not visited[neighbor][0]:  # If last edge was red
                    visited[neighbor][0] = True
                    if answer[neighbor] == -1:  # Update distance if not set
                        answer[neighbor] = dist + 1
                    queue.append((neighbor, 'R', dist + 1))
    
    return answer
← Back to All Questions