MediumNo. 1129
Shortest Path with Alternating Colors — LeetCode 1129 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Breadth-First Search, Graph
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- Input
- n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
- Output
- [0,1,-1]
Python solution
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 ansComplexity
- Time
- O(n + m)
- Space · auxiliary
- O(n + m)
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1129. Shortest Path with Alternating Colors is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
Frequently asked questions
- How hard is LeetCode 1129. Shortest Path with Alternating Colors?
LeetCode 1129. Shortest Path with Alternating Colors is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1129. Shortest Path with Alternating Colors?
The Python solution on this page runs in O(n + m).
- What is the space complexity of LeetCode 1129. Shortest Path with Alternating Colors?
The Python solution on this page uses O(n + m) auxiliary space.
- What topics does LeetCode 1129. Shortest Path with Alternating Colors cover?
LeetCode 1129. Shortest Path with Alternating Colors is tagged Breadth-First Search and Graph on LeetCode.