⚡Flashcard Drill➔
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

  1. BFS over edge counts: dist[v][0] is the fewest edges to reach v, and dist[v][1] the second fewest (strictly greater).
  2. Relax a neighbour when the new edge count improves either slot.
  3. 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.
  4. 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] + 1 as 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems