1129. Shortest Path with Alternating Colors

MediumBreadth-First SearchGraph
Leetcode Link

Problem Description

In this problem, we have a directed graph of n nodes, labeled from 0 to n - 1. There are two types of directed edges in the graph: red edges and blue edges. A red edge connects two nodes in one direction, i.e., redEdges[i] = [a_i, b_i] represents a red edge from node a_i to node b_i. Similarly, blueEdges[j] = [u_j, v_j] represents a blue edge from node u_j to node v_j.

The objective is to find the shortest path from node 0 to every other node such that the colors of the edges alternate along the path. We need to return an array answer of length n, where answer[x] is the length of such shortest path to node x. If there is no path from node 0 to node x with alternating edge colors, we set answer[x] to -1.

The challenge lies in navigating the graph in a way that each edge color along the path alternates and ensuring we are tracking the shortest such path for each node.

Intuition

To solve this problem, we leverage Breadth First Search (BFS). BFS is a well-suited algorithm for finding the shortest path in an unweighted graph, which aligns with our goal of finding the shortest alternating paths.

The intuition behind using BFS for this problem stems from its level-by-level traversal, which allows us to keep track of the path length naturally. To account for the alternating colors, we modify the traditional BFS by keeping a separate queue for red and blue edges and toggling between them on each step.

Furthermore, we need to prevent revisiting the same node through the same color edge to avoid potential infinite loops. To do this, we maintain a visited set that records nodes visited through a specific color edge.

In the solution code, we have two different graph representations, g[0] for red edges and g[1] for blue edges. Then, we start BFS from node 0 using two entries, one for a red edge and one for a blue edge, assuming an imaginary edge of both colors leading to 0. We increment the distance d each time we finish a level in the BFS traversal.

The vis set keeps track of nodes we have visited with a specific color, and the q deque contains nodes to be visited with the associated color. We use the c variable to represent the color and toggle it using c ^= 1 (where 0 represents red and 1 represents blue). If we reach a new node, we update the answer, and each new edge found is added to the queue to continue the search.

By the end of the BFS procedure, we obtain an array ans where each ans[i] is the shortest alternating path length to node i or -1 if not reachable.

Learn more about Breadth-First Search and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

Solution Approach

The solution uses a modified Breadth-First Search (BFS) algorithm to ensure path length is minimized and the alternating color requirement is met. Below is an explanation of the various parts of the solution and how they implement this modified BFS strategy:

  • Graph Representation: We use two defaultdict(list) to represent the directed graph, one for red edges (g[0]) and one for blue edges (g[1]). This allows us to easily access all the outgoing edges of a particular color from any node.

  • Initialization: The ans array is initialized to -1 for each node. This signifies that initially, all nodes are considered unreachable from node 0 via an alternating path. We also initialize a set vis to keep track of visited (node, color) pairs to prevent reprocessing, and a double-ended queue q with two tuples representing the initial node 0 with both red and blue colors.

  • BFS Loop:

    • We only increase our distance counter d once we've looked at all nodes in our queue, essential for ensuring that BFS traverses the graph level-by-level and correctly calculates the shortest path lengths.
    • For each node we dequeue (i) and its associated color (c), we check if we have already recorded a path to that node. If not, we record the current distance d as the shortest path length to i.
    • We add the node to the visited set vis to avoid revisiting a node via the same color edge.
    • To enforce alternate coloring, we toggle the color c using c ^= 1, which switches 0 to 1 and 1 to 0.

  • Queue Management: We iterate over each outgoing edge of the toggled color from node i. If the adjacent node j through color c hasn't been visited, we add (j, c) to the queue q to visit it in subsequent iterations.

  • Result: After the BFS terminates, the ans array contains the shortest path lengths from node 0 to all others with alternating colors, or -1 if no path exists. This array is then returned as the result.

In short, the key to this solution is managing a queue that tracks the next node to explore and the color of the edge we used to reach it, while also toggling the color on each step to ensure the alternation of red and blue edges.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's take a small directed graph as an example with 5 nodes (0 to 4) and alternating red and blue edges as follows:

Red edges: redEdges = [[0, 1], [1, 2], [2, 3]] Blue edges: blueEdges = [[1, 0], [2, 1], [3, 4]]

We start searching from node 0 with the objective to find the shortest alternating path from node 0 to all other nodes.

Initialization:

  • Start with ans array as [-1, -1, -1, -1, -1], since initially we have not found any paths.
  • The queue q is initialized with two tuples: [(0, 0), (0, 1)] indicating node 0 reachable by both red and blue edges.
  • The visited set vis is empty.

BFS Loop:

  1. Dequeue (0, 0), representing the starting node with a red edge. There is no actual red edge, but conceptually we use this to start the search.
  2. We mark node 0 as visited with a red edge by adding (0, 0) to vis.
  3. Since 0 is the starting node, ans[0] is set to 0.
  4. We look at blue edges from 0 since we need to alternate, but there are none.
  5. Dequeue the next element (0, 1), representing the starting node with a blue edge.
  6. We mark node 0 as visited with a blue edge by adding (0, 1) to vis.
  7. Similar to before, ans[0] is 0.
  8. We look for red edges from 0 and find 0 -> 1. Since (1, 0) is not visited, we add (1, 0) to q.
  9. Increment d to 1 since we've finished all nodes at the current level.

Next level:

  1. Dequeue (1, 0); we note that node 1 hasn't been visited from a red edge, so we add it to vis as (1, 0) and set ans[1] to d, which is 1.
  2. We toggle the color to blue and look for blue edges from 1, which is 1 -> 0. However, this leads back to node 0, which has already been visited by a blue edge.

Level d = 2:

  1. We keep processing the remaining nodes in the queue similarly, ensuring that we only move to the next level once all nodes in q from the previous level are processed.
  2. Eventually, we discover 2 -> 1 and 3 -> 4, so ans[2] is set to 2 and ans[3] to 2 as well. Node 4 is reached by a blue edge from node 3, so ans[4] is set to 3.

The BFS loop continues until all possible nodes have been visited via alternating paths or the queue is empty.

Final ans array after running the BFS will be [0, 1, 2, 2, 3]. This array indicates the shortest paths available from node 0 to all other nodes via alternating red and blue edges, with the corresponding lengths of those paths. If we had not been able to reach a node with alternating paths, that value would remain as -1.

Solution Implementation

1from collections import deque, defaultdict
2from typing import List
3
4class Solution:
5    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
6        # Create adjacency lists for red and blue edges separately using default dictionaries
7        graph = [defaultdict(list) for _ in range(2)]
8        for start, end in red_edges:
9            graph[0][start].append(end)
10        for start, end in blue_edges:
11            graph[1][start].append(end)
12
13        # Initialize the answer list with -1, indicating unreachable nodes
14        distances = [-1] * n
15        # Initialize a set to keep track of visited (node, color) pairs
16        visited = set()
17        # Doubly-ended queue to store the current node and the color of the edge used to reach it
18        queue = deque([(0, 0), (0, 1)])
19        # Distance from the source node (node 0)
20        distance = 0
21
22        # Iterate until there are no more nodes to visit
23        while queue:
24            for _ in range(len(queue)):
25                # Pop the node and its edge color from the queue
26                node, color = queue.popleft()
27                # If this node's distance hasn't been set yet, set it to the current distance
28                if distances[node] == -1:
29                    distances[node] = distance
30                # Mark this (node, color) as visited
31                visited.add((node, color))
32                # Alternate the color for the next edges to consider (0 -> 1 or 1 -> 0)
33                color ^= 1
34                # Enqueue all the adjacent nodes of the alternated color
35                for neighbor in graph[color][node]:
36                    if (neighbor, color) not in visited:
37                        queue.append((neighbor, color))
38            # After exploring the nodes at the current distance, increment for the next level
39            distance += 1
40
41        # Return the list of minimum distances to each node
42        return distances
43
1class Solution {
2    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
3
4        // Create an adjacency list for red edges (0) and blue edges (1)
5        List<Integer>[][] graph = new List[2][n];
6        for (List<Integer>[] edges : graph) {
7            Arrays.setAll(edges, element -> new ArrayList<>());
8        }
9        // Populate the adjacency list with red edges
10        for (int[] edge : redEdges) {
11            graph[0][edge[0]].add(edge[1]);
12        }
13        // Populate the adjacency list with blue edges
14        for (int[] edge : blueEdges) {
15            graph[1][edge[0]].add(edge[1]);
16        }
17
18        // Initialize a queue for BFS
19        Deque<int[]> queue = new ArrayDeque<>();
20        // Starting from node 0 with red edge (0) and blue edge (1)
21        queue.offer(new int[]{0, 0});
22        queue.offer(new int[]{0, 1});
23      
24        // Keep track of visited nodes with color (red or blue)
25        boolean[][] visited = new boolean[n][2];
26        // Initialize answer array with -1, to signify that some nodes are not reachable
27        int[] answer = new int[n];
28        Arrays.fill(answer, -1);
29      
30        // Depth or distance from the starting node
31        int depth = 0;
32
33        // Standard BFS loop
34        while (!queue.isEmpty()) {
35            // Loop through nodes at current depth
36            for (int i = queue.size(); i > 0; --i) {
37                int[] current = queue.poll();
38                int node = current[0], color = current[1];
39
40                // Update the answer for the node if it has not been reached before
41                if (answer[node] == -1) {
42                    answer[node] = depth;
43                }
44
45                // Mark the node as visited with the current color
46                visited[node][color] = true;
47                // Switch color for the next level (0 -> 1, 1 -> 0)
48                color ^= 1;
49
50                // Traverse the neighbors with the alternative color
51                for (int neighbor : graph[color][node]) {
52                    if (!visited[neighbor][color]) {
53                        // Add the neighbor to the queue with the switched color
54                        queue.offer(new int[]{neighbor, color});
55                    }
56                }
57            }
58            // Increment the depth after each level
59            ++depth;
60        }
61
62        return answer;
63    }
64}
65
1#include <vector>
2#include <queue>
3#include <cstring>
4
5class Solution {
6public:
7    std::vector<int> shortestAlternatingPaths(int n, std::vector<std::vector<int>>& redEdges, 
8                                              std::vector<std::vector<int>>& blueEdges) {
9        // Create a two-layer graph where g[0] is for red edges and g[1] for blue edges
10        std::vector<std::vector<std::vector<int>>> graph(2, std::vector<std::vector<int>>(n));
11      
12        // Fill the graph with red edges
13        for (const auto& edge : redEdges) {
14            graph[0][edge[0]].push_back(edge[1]);
15        }
16      
17        // Fill the graph with blue edges
18        for (const auto& edge : blueEdges) {
19            graph[1][edge[0]].push_back(edge[1]);
20        }
21      
22        // Queue for BFS, containing pairs of (node index, color index)
23        std::queue<std::pair<int, int>> queue;
24      
25        // Start BFS from node 0, with both red and blue colors
26        queue.emplace(0, 0); // Red path
27        queue.emplace(0, 1); // Blue path
28      
29        // Visited array to keep track of visited (node, color) pairs
30        bool visited[n][2];
31        memset(visited, false, sizeof visited); // Initialize all to not visited
32      
33        // Distance array, to hold the shortest path length to each node
34        std::vector<int> distances(n, -1); // Initialize all distances to -1 (unreachable)
35      
36        // BFS traversal distance from the starting node
37        int level = 0;
38      
39        while (!queue.empty()) {
40            // Process nodes at the current level
41            for (int size = queue.size(); size > 0; --size) {
42                // Dequeue a node/color pair
43                auto [node, color] = queue.front();
44                queue.pop();
45              
46                // If first time visiting this node, set the distance
47                if (distances[node] == -1) {
48                    distances[node] = level;
49                }
50              
51                // Mark the node as visited for the current color
52                visited[node][color] = true;
53              
54                // Alternate color for the next level
55                color ^= 1;
56              
57                // Visit all adjacent nodes for the alternate color
58                for (int neighbor : graph[color][node]) {
59                    if (!visited[neighbor][color]) {
60                        queue.emplace(neighbor, color);
61                    }
62                }
63            }
64          
65            // Increment level after processing current level
66            ++level;
67        }
68      
69        return distances;
70    }
71};
72
1type Edge = [number, number];
2
3// Define a queue item type to hold both a node index and the color index
4type QueueItem = { node: number; color: number };
5
6// This method computes the shortest alternating paths from the first node to all other nodes
7function shortestAlternatingPaths(n: number, redEdges: Edge[], blueEdges: Edge[]): number[] {
8    // Create a two-layer adjacency list where graph[0] tracks red edges and graph[1] blue edges
9    const graph: number[][][] = Array.from({ length: 2 }, () => Array.from({ length: n }, () => []));
10
11    // Populate the graph with red edges
12    redEdges.forEach(([from, to]) => {
13        graph[0][from].push(to);
14    });
15
16    // Populate the graph with blue edges
17    blueEdges.forEach(([from, to]) => {
18        graph[1][from].push(to);
19    });
20
21    // Initialize the queue for BFS with both red and blue starting paths
22    const queue: QueueItem[] = [{ node: 0, color: 0 }, { node: 0, color: 1 }];
23
24    // Visited array to keep track of visited (node, color) pairs
25    const visited: boolean[][] = Array.from({ length: n }, () => [false, false]);
26
27    // Distance array to hold the shortest path length to each node, initialized to -1 (unreachable)
28    const distances: number[] = Array(n).fill(-1);
29
30    // BFS traversal distance from the starting node is initially 0
31    let level = 0;
32
33    // Perform BFS until the queue is empty
34    while (queue.length > 0) {
35        // Number of elements (node, color pairs) at the current level
36        let size = queue.length;
37
38        while (size-- > 0) {
39            // Dequeue a node/color pair
40            const { node, color } = queue.shift()!; // TypeScript 'non-null assertion operator' used here
41
42            // If this is the first time visiting this node, update the distance
43            if (distances[node] === -1) {
44                distances[node] = level;
45            }
46
47            // Skip if this node/color pair has been visited
48            if (visited[node][color]) continue;
49
50            // Mark this node as visited for the current color
51            visited[node][color] = true;
52
53            // Alternate color for visiting adjacent nodes
54            const nextColor = color ^ 1;
55
56            // Visit all adjacent nodes with the alternate color
57            for (const neighbor of graph[nextColor][node]) {
58                if (!visited[neighbor][nextColor]) {
59                    queue.push({ node: neighbor, color: nextColor });
60                }
61            }
62        }
63
64        // Increment level after processing the nodes at the current level
65        level++;
66    }
67
68    return distances;
69}
70
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(V + E) where V is the number of vertices (nodes) and E is the number of edges. This is because each node is enqueued and dequeued at most once for each color (since the algorithm keeps track of the color of the paths). The inner loop, which iterates over the queue q, runs for each edge at most once for each color as well because an edge will only be followed if it provides a path of the opposite color from the current node.

Space Complexity

The space complexity is O(V + E) as well. This comes from the storage required for:

  • g: adjacency lists for both red and blue edges, each of which contains at most E pairs.
  • ans: an array containing n elements.
  • vis: a set containing tuples for visited nodes with a particular color; at most 2V tuples will be stored because each node can be visited with at most two colors (red and blue).
  • q: a deque that can contain at most 2V elements, since it holds pairs of node indices and color.

In summary, the structures proportional to E in the worst-case scenario dominate the space complexity, and hence it is O(V + E).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫