NeetCode #587LC-1129MediumGraphs
← Back to All Problems#587 · #1129 · Shortest Path with Alternating Colors(颜色交替的最短路径)
📌 Problem Statement & Constraints
You are given a directed graph with red edges and blue edges. Return the shortest path length from node 0 to each node such that the edge colours alternate; return -1 for unreachable nodes. Constraints:
1 <= n <= 100, 0 <= redEdges.length, blueEdges.length <= 400.💡 Core Algorithmic Approaches
- The state is
(node, colour of the last edge used), since the next edge must be the opposite colour. - So BFS over
2nstates rather thannnodes. - Start with both colours at distance 0 from node 0 (no edge has been used yet).
- The answer per node is the minimum of its two state distances, or -1 if both are unreachable.
💻 Benchmark Python3 Implementation
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
from collections import defaultdict, deque
g = [defaultdict(list), defaultdict(list)] # 0 = red, 1 = blue
for a, b in redEdges:
g[0][a].append(b)
for a, b in blueEdges:
g[1][a].append(b)
dist = [[-1, -1] for _ in range(n)] # dist[node][last colour]
dist[0][0] = dist[0][1] = 0
q = deque([(0, 0), (0, 1)])
while q:
node, col = q.popleft()
for nxt in g[1 - col][node]: # must use the opposite colour
if dist[nxt][1 - col] == -1:
dist[nxt][1 - col] = dist[node][col] + 1
q.append((nxt, 1 - col))
res = []
for d in dist:
cands = [x for x in d if x != -1]
res.append(min(cands) if cands else -1)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((V + E) * 2): each state is visited once.
💾 Space Complexity
O(V * 2) for the distance table plus the graph.
⚠️ Interview Pitfalls & Follow-ups
- Tracking only the node: the alternation constraint requires the last edge's colour in the state.
- Starting with only one colour: both are valid starting states.
- Using the same colour for the next edge: the transition must use
1 - col. - Returning the first colour's distance: the minimum over both states is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.