#2045

Hard

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Second Minimum Time to Reach Destination

Find the second minimum time to reach a destination using BFS while accounting for traffic signal delays in a graph traversal.

breadth first search graph shortest path

Problem Statement

You are given a bi-directional connected graph with n vertices labeled from 1 to n. The edges array edges contains edges[i] = [ui, vi] representing an edge between ui and vi. Traversing any edge takes a fixed number of minutes given by time. Each vertex has a traffic signal that alternates between green and red every change minutes. You can leave a vertex only when the signal is green, and waiting is mandatory if it is red.

Compute the second minimum time to reach vertex n starting from vertex 1. The second minimum is defined as the smallest time strictly greater than the minimum time. Ensure to account for both traversal time and signal waiting periods when calculating paths. Every vertex can be reached directly or indirectly from every other vertex.

Examples

Example 1

Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5

Output: 13

The figure on the left shows the given graph. The blue path in the figure on the right is the minimum time path. The time taken is:

Start at 1, time elapsed=0
1 -> 4: 3 minutes, time elapsed=3
4 -> 5: 3 minutes, time elapsed=6 Hence the minimum time needed is 6 minutes.

The red path shows the path to get the second minimum time.

Start at 1, time elapsed=0
1 -> 3: 3 minutes, time elapsed=3
3 -> 4: 3 minutes, time elapsed=6
Wait at 4 for 4 minutes, time elapsed=10
4 -> 5: 3 minutes, time elapsed=13 Hence the second minimum time is 13 minutes.

Example 2

Input: n = 2, edges = [[1,2]], time = 3, change = 2

Output: 11

The minimum time path is 1 -> 2 with time = 3 minutes. The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.

Constraints

2 <= n <= 104
n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)
edges[i].length == 2
1 <= ui, vi <= n
ui != vi
There are no duplicate edges.
Each vertex can be reached directly or indirectly from every other vertex.
1 <= time, change <= 103

Solution Approach

Use BFS with state tracking

Perform a BFS from vertex 1, storing the first and second minimum arrival times for each node. Each BFS state should include the current vertex and the time at which it is reached, allowing proper tracking of paths for the second minimum calculation.

Handle traffic signals

Before moving from a vertex, check the signal state using current time modulo change * 2. If the signal is red, calculate the waiting time until green and add it to the current path time. This ensures all moves respect signal constraints and prevents undercounting total time.

Identify the second minimum time

Continue BFS until reaching vertex n at least twice. The first arrival gives the minimum time, while the next valid arrival strictly larger than the minimum is the second minimum time. Track visited times carefully to avoid revisiting a path that does not improve the second minimum.

Complexity Analysis

Metric	Value
Time	O(N + E)
Space	O(N + E)

Time complexity is O(N + E) because BFS visits each node and edge at most twice for minimum and second minimum times. Space complexity is O(N + E) for storing adjacency lists and the arrival times for BFS states.

What Interviewers Usually Probe

Expect candidates to handle graph traversal and BFS correctly with dual timing states per node.
Check if the solution accounts for traffic signals and mandatory waiting periods.
Look for correct identification of the second minimum rather than just the shortest path.

Common Pitfalls or Variants

Common pitfalls

Ignoring traffic signal delays when calculating edge traversal time.
Assuming the second minimum is always the second shortest path without considering signal waits.
Failing to track both minimum and second minimum times per vertex correctly.

Follow-up variants

Calculate the third minimum time with the same BFS pattern extended to track three arrival times per node.
Modify traversal times per edge and still find the second minimum respecting signal cycles.
Apply the problem to weighted graphs where edge times differ and traffic signals still apply.

FAQ

What is the second minimum time in this problem?

It is the smallest time strictly larger than the minimum time needed to reach vertex n from vertex 1, accounting for both traversal and signal waits.

How do traffic signals affect BFS traversal?

Each vertex has a signal that may force waiting. BFS must check if the signal is green before moving and add wait time if red.

Can edges be traversed multiple times?

Yes, but only if it leads to a valid second minimum time. BFS should track first and second arrivals at each vertex.

What are the key constraints for edges and vertices?

2 <= n <= 104, edges.length between n-1 and min(2 104, n(n-1)/2), no duplicate edges, each vertex reachable from any other.

Which algorithm pattern best fits this problem?

Graph traversal with breadth-first search using dual timing states to handle minimum and second minimum paths.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def secondMinimum(
        self, n: int, edges: List[List[int]], time: int, change: int
    ) -> int:
        g = defaultdict(set)
        for u, v in edges:
            g[u].add(v)
            g[v].add(u)
        q = deque([(1, 0)])
        dist = [[inf] * 2 for _ in range(n + 1)]
        dist[1][1] = 0
        while q:
            u, d = q.popleft()
            for v in g[u]:
                if d + 1 < dist[v][0]:
                    dist[v][0] = d + 1
                    q.append((v, d + 1))
                elif dist[v][0] < d + 1 < dist[v][1]:
                    dist[v][1] = d + 1
                    if v == n:
                        break
                    q.append((v, d + 1))
        ans = 0
        for i in range(dist[n][1]):
            ans += time
            if i < dist[n][1] - 1 and (ans // change) % 2 == 1:
                ans = (ans + change) // change * change
        return ans

Continue Practicing

#2290 minimum obstacle removal to reach corner #2577 minimum time to visit a cell in a grid #1368 minimum cost to make at least one valid path in a grid