NeetCode #650LC-2045HardAdvanced Graphs
← Back to All Problems#650 · #2045 · Second Minimum Time to Reach Destination(到达目的地的第二短时间)
📌 Problem Statement & Constraints
There are
n intersections connected by bidirectional roads, each traversal taking time minutes. Traffic lights change every change minutes: green first, then red, alternating. You may only leave a node during a green light. Return the second minimum time to reach node n from node 1. Constraints: 2 <= n <= 10^4, n-1 <= edges.length <= min(2*10^4, n*(n-1)/2), 1 <= time, change <= 10^3.💡 Core Algorithmic Approaches
- BFS over edge counts:
dist[v][0]is the fewest edges to reachv, anddist[v][1]the second fewest (strictly greater). - Relax a neighbour when the new edge count improves either slot.
- Then convert the second-smallest edge count into a time by simulating the traffic lights: if we are in a red phase, wait until the next green.
- The parity of the two counts matters -- the second minimum is not simply one more edge.
💻 Benchmark Python3 Implementation
class Solution:
def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
from collections import defaultdict, deque
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
# dist[v][0] = fewest edges, dist[v][1] = second fewest (strictly larger)
INF = float("inf")
dist = [[INF, INF] for _ in range(n + 1)]
dist[1][0] = 0
q = deque([(1, 0)])
while q:
node, d = q.popleft()
for nxt in g[node]:
nd = d + 1
if nd < dist[nxt][0]:
dist[nxt][0] = nd
q.append((nxt, nd))
elif dist[nxt][0] < nd < dist[nxt][1]:
dist[nxt][1] = nd # strictly between -> the second best
q.append((nxt, nd))
# convert the second-smallest edge count into a time
t = 0
for _ in range(dist[n][1]):
if (t // change) % 2 == 1: # red -> wait for the next green
t = (t // change + 1) * change
t += time
return t⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node is enqueued at most twice.
💾 Space Complexity
O(V + E) for the graph and the distance table.
⚠️ Interview Pitfalls & Follow-ups
- Using
dist[n][0] + 1as the second minimum: the second-smallest edge count is not necessarily one more. - Not requiring
nd > dist[nxt][0]: the second slot must be strictly larger than the first. - Ignoring the traffic lights: the wait must be simulated when converting edges to time.
- Using a weighted shortest path: all edges have equal weight, so BFS on edge counts is correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.