1229. Shortest Path with Alternating Colors
My accepted Python solution to LeetCode problem 1229, Shortest Path with Alternating Colors, running in 2ms.
- Difficulty: Medium
- Python
- Runtime 2ms
- Memory 17.4MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 2ms, memory 17.4MB, accepted 2026-01-02.
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
from collections import deque, defaultdict
# Build adjacency lists for red and blue edges
red_graph = defaultdict(list)
blue_graph = defaultdict(list)
for u, v in redEdges:
red_graph[u].append(v)
for u, v in blueEdges:
blue_graph[u].append(v)
# BFS: state = (node, last_color)
# last_color: 0 = red, 1 = blue
result = [-1] * n
# Start with both colors from node 0
queue = deque([(0, 0, 0), (0, 1, 0)]) # (node, last_color, distance)
visited = set([(0, 0), (0, 1)])
result[0] = 0
while queue:
node, last_color, dist = queue.popleft()
# Next edges should be opposite color
if last_color == 0: # Last was red, next should be blue
for neighbor in blue_graph[node]:
if (neighbor, 1) not in visited:
visited.add((neighbor, 1))
if result[neighbor] == -1:
result[neighbor] = dist + 1
queue.append((neighbor, 1, dist + 1))
else: # Last was blue, next should be red
for neighbor in red_graph[node]:
if (neighbor, 0) not in visited:
visited.add((neighbor, 0))
if result[neighbor] == -1:
result[neighbor] = dist + 1
queue.append((neighbor, 0, dist + 1))
return result