# Shortest Path with Alternating Colors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-path-with-alternating-colors)
Canonical: https://scaleengineer.com/dsa/problems/shortest-path-with-alternating-colors
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
---
## Problem
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] = [ai, bi]` indicates that there is a directed red edge from node `ai` to node `bi` in the graph, and
* `blueEdges[j] = [uj, vj]` indicates that there is a directed blue edge from node `uj` to node `vj` 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 <= ai, bi, uj, vj < n`

# Approaches
## DFS with Memoization
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)`.
**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).
**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.
### Explanation
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.

1.  First, we parse the input `redEdges` and `blueEdges` into a more usable format, like two separate adjacency lists, `redAdj` and `blueAdj`.
2.  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).
3.  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`.
4.  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)`.
5.  We initiate the search from the source node 0 for both possibilities: `dfs(0, RED)` and `dfs(0, BLUE)`.
6.  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.

```java
class Solution {
    private java.util.List<java.util.List<Integer>> redAdj;
    private java.util.List<java.util.List<Integer>> blueAdj;
    private int[][] distances;
    private final int RED = 0;
    private final int BLUE = 1;

    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        redAdj = new java.util.ArrayList<>();
        blueAdj = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            redAdj.add(new java.util.ArrayList<>());
            blueAdj.add(new java.util.ArrayList<>());
        }
        for (int[] edge : redEdges) {
            redAdj.get(edge[0]).add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            blueAdj.get(edge[0]).add(edge[1]);
        }

        distances = new int[n][2];
        for (int i = 0; i < n; i++) {
            java.util.Arrays.fill(distances[i], Integer.MAX_VALUE);
        }
        
        distances[0][RED] = 0;
        distances[0][BLUE] = 0;

        dfs(0, RED);
        dfs(0, BLUE);

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int dist = Math.min(distances[i][RED], distances[i][BLUE]);
            answer[i] = (dist == Integer.MAX_VALUE) ? -1 : dist;
        }
        return answer;
    }

    private void dfs(int u, int color) {
        if (color == RED) { // Last edge was red, next must be blue
            int currentDist = distances[u][RED];
            for (int v : blueAdj.get(u)) {
                if (currentDist + 1 < distances[v][BLUE]) {
                    distances[v][BLUE] = currentDist + 1;
                    dfs(v, BLUE);
                }
            }
        } else { // Last edge was blue, next must be red
            int currentDist = distances[u][BLUE];
            for (int v : redAdj.get(u)) {
                if (currentDist + 1 < distances[v][RED]) {
                    distances[v][RED] = currentDist + 1;
                    dfs(v, RED);
                }
            }
        }
    }
}
```
### 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.

## Breadth-First Search (BFS) on State Graph
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.
**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).
**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.
### Explanation
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)`.

1.  We begin by constructing adjacency lists for red and blue edges from the input arrays.
2.  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.
3.  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.
4.  The main loop of the BFS continues as long as the queue is not empty. In each iteration, we dequeue a state `[u, color]`.
5.  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`.
6.  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]`.
7.  A symmetric step is performed if the last edge was blue.
8.  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.

```java
class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        final int RED = 0;
        final int BLUE = 1;

        java.util.List<java.util.List<Integer>> redAdj = new java.util.ArrayList<>();
        java.util.List<java.util.List<Integer>> blueAdj = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            redAdj.add(new java.util.ArrayList<>());
            blueAdj.add(new java.util.ArrayList<>());
        }
        for (int[] edge : redEdges) {
            redAdj.get(edge[0]).add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            blueAdj.get(edge[0]).add(edge[1]);
        }

        int[][] distances = new int[n][2];
        for (int i = 0; i < n; i++) {
            java.util.Arrays.fill(distances[i], Integer.MAX_VALUE);
        }

        java.util.Queue<int[]> queue = new java.util.LinkedList<>();
        
        distances[0][RED] = 0;
        distances[0][BLUE] = 0;
        queue.offer(new int[]{0, RED}); 
        queue.offer(new int[]{0, BLUE});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int u = current[0];
            int color = current[1];

            if (color == RED) { // Last edge was red, next must be blue
                for (int v : blueAdj.get(u)) {
                    if (distances[u][RED] + 1 < distances[v][BLUE]) {
                        distances[v][BLUE] = distances[u][RED] + 1;
                        queue.offer(new int[]{v, BLUE});
                    }
                }
            } else { // Last edge was blue, next must be red
                for (int v : redAdj.get(u)) {
                    if (distances[u][BLUE] + 1 < distances[v][0]) {
                        distances[v][0] = distances[u][BLUE] + 1;
                        queue.offer(new int[]{v, RED});
                    }
                }
            }
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int dist = Math.min(distances[i][RED], distances[i][BLUE]);
            answer[i] = (dist == Integer.MAX_VALUE) ? -1 : dist;
        }
        return answer;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
    List<Integer>[][] g = new List[2][n];
    for (var f : g) {
      Arrays.setAll(f, k->new ArrayList<>());
    }
    for (var e : redEdges) {
      g[0][e[0]].add(e[1]);
    }
    for (var e : blueEdges) {
      g[1][e[0]].add(e[1]);
    }
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{0, 0});
    q.offer(new int[]{0, 1});
    boolean[][] vis = new boolean[n][2];
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    int d = 0;
    while (!q.isEmpty()) {
      for (int k = q.size(); k > 0; --k) {
        var p = q.poll();
        int i = p[0], c = p[1];
        if (ans[i] == -1) {
          ans[i] = d;
        }
        vis[i][c] = true;
        c ^= 1;
        for (int j : g[c][i]) {
          if (!vis[j][c]) {
            q.offer(new int[]{j, c});
          }
        }
      }
      ++d;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges,
                                       vector<vector<int>> &blueEdges) {
    vector<vector<vector<int>>> g(2, vector<vector<int>>(n));
    for (auto &e : redEdges) {
      g[0][e[0]].push_back(e[1]);
    }
    for (auto &e : blueEdges) {
      g[1][e[0]].push_back(e[1]);
    }
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    q.emplace(0, 1);
    bool vis[n][2];
    memset(vis, false, sizeof vis);
    vector<int> ans(n, -1);
    int d = 0;
    while (!q.empty()) {
      for (int k = q.size(); k; --k) {
        auto [i, c] = q.front();
        q.pop();
        if (ans[i] == -1) {
          ans[i] = d;
        }
        vis[i][c] = true;
        c ^= 1;
        for (int &j : g[c][i]) {
          if (!vis[j][c]) {
            q.emplace(j, c);
          }
        }
      }
      ++d;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```