Shortest Path With Alternating Colors - Leetcode Solution

Problem Statement

The problem asks us to find the shortest path between two nodes in a graph where edges are of two colors, red and blue. We can only traverse edges of a specific color at a time, i.e., if we traverse a red edge, we can only traverse the next edge of blue color, and vice versa.

Approach

To solve the problem, we can use Breadth First Search (BFS) algorithm where we would keep track of the current color while traversing the graph. For this, we can maintain two queues, one for blue color edges, and the other for red color edges. We would also maintain two distance arrays, one for the blue color edges, and the other for red color edges.

We would start by traversing the graph from the given start node and initialize the distance arrays for both colors. We would then push the start node to both queues and set its distance as zero.

As we traverse the graph using BFS, we would keep track of the current color. If we traverse a node using a red color edge, we would push its adjacent nodes to the blue queue with distance as the current distance + 1 (since we have to traverse a blue edge after we traverse the current red edge). Similarly, if we traverse a node using a blue color edge, we would push its adjacent nodes to the red queue with distance as the current distance + 1.

We would continue the BFS until we reach the target node or both queues become empty (which implies that we have traversed the entire graph and the target node is not reachable).

If we reach the target node, we would return the minimum distance from the both the distance arrays (as we can reach the target node using either red or blue edges). If the target node is not reachable, we would return -1.

Code Implementation

We would start by creating a graph using adjacency list representation.

graph = [[] for _ in range(n)]

for u, v, color in red_edges + blue_edges: if color == 1: graph[u].append((v, True)) # adding red color edge else: graph[u].append((v, False)) # adding blue color edge

We would then define two queues, two distance arrays, and a set to keep track of visited nodes.

red_queue = collections.deque([(start, 0)]) blue_queue = collections.deque([(start, 0)])

red_dist = [float('inf')] * n blue_dist = [float('inf')] * n

visited = set()

We would then start the BFS from the start node.

while red_queue or blue_queue: # process red queue while red_queue: node, dist = red_queue.popleft() if node not in visited: visited.add(node) red_dist[node] = min(red_dist[node], dist) for adj_node, color in graph[node]: if not color: blue_queue.append((adj_node, dist+1))

# process blue queue
while blue_queue:
    node, dist = blue_queue.popleft()
    if node not in visited:
        visited.add(node)
        blue_dist[node] = min(blue_dist[node], dist)
        for adj_node, color in graph[node]:
            if color:
                red_queue.append((adj_node, dist+1))

As we traverse the graph using BFS, we keep pushing nodes to the respective queues and updating the distance arrays. We also keep track of the visited nodes.

Once we have finished the BFS traversal, we would check if the target node is reachable. If it is reachable, we would return the minimum distance from the distance arrays. Otherwise, we would return -1.

if red_dist[dest] != float('inf') or blue_dist[dest] != float('inf'): return min(red_dist[dest], blue_dist[dest]) else: return -1

Complete Code

Here is the complete code for the problem:

import collections

class Solution: def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:

    # create graph
    graph = [[] for _ in range(n)]
    for u, v, color in red_edges + blue_edges:
        if color == 1:
            graph[u].append((v, True))  # adding red color edge
        else:
            graph[u].append((v, False))  # adding blue color edge
            
    # initialize queues and distance arrays
    red_queue = collections.deque([(0, 0)])
    blue_queue = collections.deque([(0, 0)])
    red_dist = [float('inf')] * n
    blue_dist = [float('inf')] * n
    visited = set()
    
    # start BFS traversal
    while red_queue or blue_queue:
        # process red queue
        while red_queue:
            node, dist = red_queue.popleft()
            if node not in visited:
                visited.add(node)
                red_dist[node] = min(red_dist[node], dist)
                for adj_node, color in graph[node]:
                    if not color:
                        blue_queue.append((adj_node, dist+1))
                        
        # process blue queue
        while blue_queue:
            node, dist = blue_queue.popleft()
            if node not in visited:
                visited.add(node)
                blue_dist[node] = min(blue_dist[node], dist)
                for adj_node, color in graph[node]:
                    if color:
                        red_queue.append((adj_node, dist+1))
    
    # check if target node is reachable
    if red_dist[n-1] != float('inf') or blue_dist[n-1] != float('inf'):
        return min(red_dist[n-1], blue_dist[n-1])
    else:
        return -1

Time Complexity

The time complexity of the solution is O(E + V), where E is the number of edges and V is the number of vertices in the graph. This is because we are traversing each edge and vertex once using Breadth First Search algorithm.

Space Complexity

The space complexity of the solution is O(E + V), which is the maximum amount of space used by the visited set, distance arrays, and queues.

1