> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Shortest Path with Alternating Colors

> Tested Python solution for LeetCode 1129 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 1129, [Medium](/catalog/medium). Topics: [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph](/catalog/topics/graph). [View on LeetCode](https://leetcode.com/problems/shortest-path-with-alternating-colors/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1129   # by problem number
lcpy gen -s shortest_path_with_alternating_colors   # by problem name
```

## Problem

You are given an integer \<code>n\</code>, the number of nodes in a directed graph where the nodes are labeled from \<code>0\</code> to \<code>n - 1\</code>. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays \<code>redEdges\</code> and \<code>blueEdges\</code> where:

* \<code>redEdges\[i] = \[a\<sub>i\</sub>, b\<sub>i\</sub>]\</code> indicates that there is a directed red edge from node \<code>a\<sub>i\</sub>\</code> to node \<code>b\<sub>i\</sub>\</code> in the graph, and
* \<code>blueEdges\[j] = \[u\<sub>j\</sub>, v\<sub>j\</sub>]\</code> indicates that there is a directed blue edge from node \<code>u\<sub>j\</sub>\</code> to node \<code>v\<sub>j\</sub>\</code> in the graph.

Return an array \<code>answer\</code> of length \<code>n\</code>, where each \<code>answer\[x]\</code> is the length of the shortest path from node \<code>0\</code> to node \<code>x\</code> such that the edge colors alternate along the path, or \<code>-1\</code> if such a path does not exist.

### Examples

```
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
```

```
Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
```

### Constraints

* \<code>1 \<= n \<= 100\</code>
* \<code>0 \<= redEdges.length, blueEdges.length \<= 400\</code>
* \<code>redEdges\[i].length == blueEdges\[j].length == 2\</code>
* \<code>0 \<= a\<sub>i\</sub>, b\<sub>i\</sub>, u\<sub>j\</sub>, v\<sub>j\</sub> \< n\</code>

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_path_with_alternating_colors/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_path_with_alternating_colors/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def shortest_alternating_paths(
        self, n: int, red_edges: list[list[int]], blue_edges: list[list[int]]
    ) -> list[int]:
        adj: list[dict[str, list[int]]] = [{"r": [], "b": []} for _ in range(n)]
        for a, b in red_edges:
            adj[a]["r"].append(b)
        for a, b in blue_edges:
            adj[a]["b"].append(b)

        ans = [-1] * n
        dist: dict[tuple[int, str], int] = {(0, "r"): 0, (0, "b"): 0}
        queue: deque[tuple[int, str]] = deque([(0, "r"), (0, "b")])
        while queue:
            node, color = queue.popleft()
            if ans[node] == -1:
                ans[node] = dist[(node, color)]
            nxt = "b" if color == "r" else "r"
            for nb in adj[node][nxt]:
                if (nb, nxt) not in dist:
                    dist[(nb, nxt)] = dist[(node, color)] + 1
                    queue.append((nb, nxt))
        return ans
```

## Complexity

| Time | Space |
| - | - |
| O(n + e) | O(n + e) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.