Shortest Path with Alternating Colors

Med

#1065Time: O(n + E). Each state `(node, color)` is processed once due to the memoization check (`distances[u][color] + 1 < distances[v][next_color]`). From each state, we iterate through its outgoing edges. The total number of states is `2n` and transitions is `E`.Space: O(n + E), where `n` is the number of nodes and `E` is the total number of edges. This is for storing the adjacency lists (`O(n + E)`), the `distances` array (`O(n)`), and the recursion stack (`O(n)` in the worst case).

Algorithms

Breadth-First Search

Data structures

Graph

Prompt

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.

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 <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= a_i, b_i, u_j, v_j < n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem as finding the shortest path in an expanded graph where each state is a pair (node, color). The color represents the color of the edge used to arrive at the node. We use a Depth-First Search (DFS) to explore all possible alternating paths starting from node 0. To avoid recomputing paths and to ensure we find the shortest one, we use memoization (a form of dynamic programming) to store the length of the shortest path found so far for each state (node, color).

Algorithm

State Representation: Define a state as a tuple (node, color), where color is the color of the edge used to arrive at node. This expands the graph into a state graph with 2*n vertices.
Data Structures:
- Adjacency lists for red and blue edges (redAdj, blueAdj).
- A 2D array distances[n][2] to memoize the shortest distance to each state (node, color). Initialize with infinity.
DFS Function: Create a recursive function dfs(u, color).
- This function explores paths from node u, assuming the incoming edge had color.
- It iterates through neighbors reachable by an edge of the opposite color.
- For each neighbor v, if a shorter path is found (i.e., distances[u][color] + 1 < distances[v][next_color]), it updates the distance and makes a recursive call dfs(v, next_color).
Initialization:
- Build the adjacency lists.
- Initialize distances array. Set distances[0][RED] = 0 and distances[0][BLUE] = 0, as node 0 is the start with a path of length 0.
- Start the search by calling dfs(0, RED) and dfs(0, BLUE).
Result: After the DFS completes, for each node i, the shortest path is min(distances[i][RED], distances[i][BLUE]). If the minimum is still infinity, no such path exists.

Walkthrough

The core idea is to transform the graph problem. Instead of nodes, we think about states (u, c), which means we've reached node u via an edge of color c. The goal is to find the shortest path from a starting state to all other states.

We can use a recursive DFS to traverse this state graph. To make it efficient and correct for finding the shortest path, we must store the results to avoid re-computation and cycles. This is done using a distances array which acts as a memoization table.

First, we parse the input redEdges and blueEdges into a more usable format, like two separate adjacency lists, redAdj and blueAdj.
We initialize a distances[n][2] array. distances[i][0] will store the shortest path to node i ending with a red edge, and distances[i][1] for a path ending with a blue edge. All entries are initialized to a large value (infinity).
The path to the starting node 0 has length 0. We can consider it reachable by a 'virtual' red or blue edge, so we set distances[0][0] = 0 and distances[0][1] = 0.
We define a recursive function, dfs(u, color), which will explore all paths starting from state (u, color). Inside the function, we find the next valid neighbors (e.g., if color is red, we look at blue neighbors) and check if we can find a shorter path to them. If distances[u][color] + 1 is less than the current distances[v][next_color], we update the distance and recurse on dfs(v, next_color).
We initiate the search from the source node 0 for both possibilities: dfs(0, RED) and dfs(0, BLUE).
Finally, we compile the answer array. For each node i, the shortest path is the minimum of distances[i][0] and distances[i][1]. If this minimum is still infinity, it means the node is unreachable, so we set its answer to -1.

1class Solution {2    private java.util.List<java.util.List<Integer>> redAdj;3    private java.util.List<java.util.List<Integer>> blueAdj;4    private int[][] distances;5    private final int RED = 0;6    private final int BLUE = 1;7 8    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {9        redAdj = new java.util.ArrayList<>();10        blueAdj = new java.util.ArrayList<>();11        for (int i = 0; i < n; i++) {12            redAdj.add(new java.util.ArrayList<>());13            blueAdj.add(new java.util.ArrayList<>());14        }15        for (int[] edge : redEdges) {16            redAdj.get(edge[0]).add(edge[1]);17        }18        for (int[] edge : blueEdges) {19            blueAdj.get(edge[0]).add(edge[1]);20        }21 22        distances = new int[n][2];23        for (int i = 0; i < n; i++) {24            java.util.Arrays.fill(distances[i], Integer.MAX_VALUE);25        }26        27        distances[0][RED] = 0;28        distances[0][BLUE] = 0;29 30        dfs(0, RED);31        dfs(0, BLUE);32 33        int[] answer = new int[n];34        for (int i = 0; i < n; i++) {35            int dist = Math.min(distances[i][RED], distances[i][BLUE]);36            answer[i] = (dist == Integer.MAX_VALUE) ? -1 : dist;37        }38        return answer;39    }40 41    private void dfs(int u, int color) {42        if (color == RED) { // Last edge was red, next must be blue43            int currentDist = distances[u][RED];44            for (int v : blueAdj.get(u)) {45                if (currentDist + 1 < distances[v][BLUE]) {46                    distances[v][BLUE] = currentDist + 1;47                    dfs(v, BLUE);48                }49            }50        } else { // Last edge was blue, next must be red51            int currentDist = distances[u][BLUE];52            for (int v : redAdj.get(u)) {53                if (currentDist + 1 < distances[v][RED]) {54                    distances[v][RED] = currentDist + 1;55                    dfs(v, RED);56                }57            }58        }59    }60}

Complexity

Time

O(n + E). Each state `(node, color)` is processed once due to the memoization check (`distances[u][color] + 1 < distances[v][next_color]`). From each state, we iterate through its outgoing edges. The total number of states is `2n` and transitions is `E`.

Space

O(n + E), where `n` is the number of nodes and `E` is the total number of edges. This is for storing the adjacency lists (`O(n + E)`), the `distances` array (`O(n)`), and the recursion stack (`O(n)` in the worst case).

Trade-offs

Pros

Solves the problem correctly by exploring the entire reachable state space.
The logic is a direct application of DFS to a graph problem, which can be intuitive for those familiar with recursion.

Cons

Can be less efficient than BFS due to function call overhead from recursion.
May cause a StackOverflowError on graphs that allow for very long alternating paths, even if they are not the shortest.
The depth-first nature means it might explore a very long path before finding a shorter one, making it computationally more intensive than a breadth-first search which explores layer by layer.

This is the most suitable and efficient approach for finding the shortest path in what is effectively an unweighted graph. We adapt the standard Breadth-First Search (BFS) algorithm to handle the alternating color constraint. The key idea is to expand the graph's state representation. Instead of just tracking the current node, we track the state as a pair (node, color), where color is the color of the edge that led to the current node. BFS naturally explores the graph layer by layer, guaranteeing that we find the shortest path in terms of the number of edges.

Algorithm

State Representation: As with the DFS approach, a state is (node, color).
Data Structures:
- Adjacency lists for red and blue edges (redAdj, blueAdj).
- A 2D array distances[n][2] to store the shortest distance to each state. Initialize with infinity.
- A queue to manage states to visit in BFS order.
BFS Algorithm:
- Build the adjacency lists.
- Initialize distances array. Set distances[0][RED] = 0 and distances[0][BLUE] = 0.
- Add the initial states (0, RED) and (0, BLUE) to the queue.
- While the queue is not empty, dequeue a state (u, color).
- If color is RED, the next edge must be BLUE. Iterate through v in blueAdj[u]. If a shorter path to (v, BLUE) is found (distances[u][RED] + 1 < distances[v][BLUE]), update distances[v][BLUE] and enqueue (v, BLUE).
- If color is BLUE, do the same for RED edges.
Result: After the BFS completes, the distances array holds the shortest path lengths. The final answer for node i is min(distances[i][RED], distances[i][BLUE]) or -1 if unreachable.

Walkthrough

BFS is the canonical algorithm for shortest paths in unweighted graphs. By redefining our search space, we can apply it here.

The states in our search are (node, color), representing reaching a node via an edge of a specific color. The distance to a node x will be the minimum distance to reach state (x, RED) or (x, BLUE).

We begin by constructing adjacency lists for red and blue edges from the input arrays.
We use a distances[n][2] array, initialized to infinity, to store the shortest path length to each state. distances[0][RED] and distances[0][BLUE] are set to 0.
A queue, fundamental to BFS, is initialized. We add the starting states [0, RED] and [0, BLUE] to it. These represent being at node 0, ready to take either a red or blue edge next.
The main loop of the BFS continues as long as the queue is not empty. In each iteration, we dequeue a state [u, color].
Based on the color of the last edge, we determine the required color for the next edge. If the last edge was red (color == RED), we must now traverse a blue edge. We iterate through all of u's blue neighbors v.
For each neighbor v, we check if we've found a shorter path. The condition distances[u][RED] + 1 < distances[v][BLUE] serves this purpose. Since BFS explores level by level, this check is equivalent to seeing if the state (v, BLUE) has been visited. If it's a shorter path (or the first time visiting), we update distances[v][BLUE] and enqueue the new state [v, BLUE].
A symmetric step is performed if the last edge was blue.
After the queue is empty, the distances array is fully populated. The final answer for each node i is the minimum of distances[i][0] and distances[i][1]. If a node was never reached, its distance remains infinity, and we output -1.

1class Solution {2    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {3        final int RED = 0;4        final int BLUE = 1;5 6        java.util.List<java.util.List<Integer>> redAdj = new java.util.ArrayList<>();7        java.util.List<java.util.List<Integer>> blueAdj = new java.util.ArrayList<>();8        for (int i = 0; i < n; i++) {9            redAdj.add(new java.util.ArrayList<>());10            blueAdj.add(new java.util.ArrayList<>());11        }12        for (int[] edge : redEdges) {13            redAdj.get(edge[0]).add(edge[1]);14        }15        for (int[] edge : blueEdges) {16            blueAdj.get(edge[0]).add(edge[1]);17        }18 19        int[][] distances = new int[n][2];20        for (int i = 0; i < n; i++) {21            java.util.Arrays.fill(distances[i], Integer.MAX_VALUE);22        }23 24        java.util.Queue<int[]> queue = new java.util.LinkedList<>();25        26        distances[0][RED] = 0;27        distances[0][BLUE] = 0;28        queue.offer(new int[]{0, RED}); 29        queue.offer(new int[]{0, BLUE});30 31        while (!queue.isEmpty()) {32            int[] current = queue.poll();33            int u = current[0];34            int color = current[1];35 36            if (color == RED) { // Last edge was red, next must be blue37                for (int v : blueAdj.get(u)) {38                    if (distances[u][RED] + 1 < distances[v][BLUE]) {39                        distances[v][BLUE] = distances[u][RED] + 1;40                        queue.offer(new int[]{v, BLUE});41                    }42                }43            } else { // Last edge was blue, next must be red44                for (int v : redAdj.get(u)) {45                    if (distances[u][BLUE] + 1 < distances[v][0]) {46                        distances[v][0] = distances[u][BLUE] + 1;47                        queue.offer(new int[]{v, RED});48                    }49                }50            }51        }52 53        int[] answer = new int[n];54        for (int i = 0; i < n; i++) {55            int dist = Math.min(distances[i][RED], distances[i][BLUE]);56            answer[i] = (dist == Integer.MAX_VALUE) ? -1 : dist;57        }58        return answer;59    }60}

Complexity

Time

O(n + E). BFS on the state graph visits each state `(node, color)` and each transition (edge) at most once. The number of states is `2n` and the number of transitions is `E`.

Space

O(n + E), where `n` is the number of nodes and `E` is the total number of edges. This space is used for the adjacency lists (`O(n + E)`), the `distances` array (`O(n)`), and the queue (`O(n)` in the worst case).

Trade-offs

Pros

Guaranteed to find the shortest path because of the level-by-level nature of BFS.
Generally more efficient than a recursive DFS for shortest path problems on unweighted graphs due to its iterative nature.
Avoids the risk of stack overflow that can occur with deep recursion in DFS.

Cons

The state representation (node, color) can be slightly more complex to conceptualize than a standard BFS on a simple graph.

Solutions

Solution

1class Solution {2public3  int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {4    List<Integer>[][] g = new List[2][n];5    for (var f : g) {6      Arrays.setAll(f, k->new ArrayList<>());7    }8    for (var e : redEdges) {9      g[0][e[0]].add(e[1]);10    }11    for (var e : blueEdges) {12      g[1][e[0]].add(e[1]);13    }14    Deque<int[]> q = new ArrayDeque<>();15    q.offer(new int[]{0, 0});16    q.offer(new int[]{0, 1});17    boolean[][] vis = new boolean[n][2];18    int[] ans = new int[n];19    Arrays.fill(ans, -1);20    int d = 0;21    while (!q.isEmpty()) {22      for (int k = q.size(); k > 0; --k) {23        var p = q.poll();24        int i = p[0], c = p[1];25        if (ans[i] == -1) {26          ans[i] = d;27        }28        vis[i][c] = true;29        c ^= 1;30        for (int j : g[c][i]) {31          if (!vis[j][c]) {32            q.offer(new int[]{j, c});33          }34        }35      }36      ++d;37    }38    return ans;39  }40}

1class Solution {2public:3  vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges,4                                       vector<vector<int>> &blueEdges) {5    vector<vector<vector<int>>> g(2, vector<vector<int>>(n));6    for (auto &e : redEdges) {7      g[0][e[0]].push_back(e[1]);8    }9    for (auto &e : blueEdges) {10      g[1][e[0]].push_back(e[1]);11    }12    queue<pair<int, int>> q;13    q.emplace(0, 0);14    q.emplace(0, 1);15    bool vis[n][2];16    memset(vis, false, sizeof vis);17    vector<int> ans(n, -1);18    int d = 0;19    while (!q.empty()) {20      for (int k = q.size(); k; --k) {21        auto [i, c] = q.front();22        q.pop();23        if (ans[i] == -1) {24          ans[i] = d;25        }26        vis[i][c] = true;27        c ^= 1;28        for (int &j : g[c][i]) {29          if (!vis[j][c]) {30            q.emplace(j, c);31          }32        }33      }34      ++d;35    }36    return ans;37  }38};

1class Solution:2    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]: g = [defaultdict(list), defaultdict(list)] for i, j in redEdges: g[0][i]. append(j) for i, j in blueEdges: g[1][i]. append(j) ans = [- 1] * n vis = set() q = deque([(0, 0), (0, 1)]) d = 0 while q: for _ in range(len(q)): i, c = q . popleft() if ans[i] == - 1: ans[i] = d vis . add((i, c)) c ^= 1 for j in g[c][i]: if (j, c) not in vis: q . append((j, c)) d += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem