0891HardBreadth-First SearchGraph TheoryShortest PathDijkstra's AlgorithmK Shortest Path

Second-Quickest Run Past Timed Gates

Tracked in this browser only

Trains the technique from

LeetCode 2045Second Minimum Time to Reach Destination

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A yard has n depots numbered 1 through n. Each entry of edges is a pair of depots joined by a two-way run, and every run takes time minutes to travel. The yard is connected, so any depot can be reached from any other, and no run is listed twice.

Every depot has a gate that is open for change minutes, then shut for change minutes, over and over, starting open at minute 0. You may set off from a depot only while its gate is open; arriving is always allowed, and if you arrive while the gate is shut you wait for it to open again. Passing through a depot means leaving it, so the gate applies there too.

You set off from depot 1 at minute 0. Return the second smallest number of minutes in which depot n can be reached, counting only totals strictly larger than the smallest.

Examples

Example 1

Input: n = 7, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5], [5, 6], [6, 7], [5, 7]], time = 7, change = 9
Output: 43

Depot 7 is four runs away at the quickest and five runs away next, so the answer follows the five-run route. The clock reaches 21 after three runs, which lands in a shut stretch, so it waits until 27 before the fourth run and again before the fifth.

Example 2

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

The one run reaches depot 2 at minute 3. Going back and forth takes three runs, and the waits at the shut gates push that total out further.

Example 3

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

Every depot joins every other, so depot 4 is one run away and next two runs away. The gate shuts for the whole of minute 1, so the second run cannot start until minute 2.

Constraints

2 <= n <= 10^4
n - 1 <= edges.length <= 2 * 10^4
edges[i].length == 2
1 <= edges[i][0] <= n
1 <= edges[i][1] <= n
The two depots on a run are different
No run is listed twice
Every depot can be reached from every other
1 <= time <= 10^3
1 <= change <= 10^3

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def second_minimum(n: int, edges: list[list[int]], time: int, change: int) -> int:

Java

public int secondMinimum(int n, int[][] edges, int time, int change)

The intended approach

Time O(n + e) for n depots and e runs: each depot is expanded at most twice.Space O(n + e) for the adjacency lists and the two run counts per depot.

Every run costs the same, and waiting at a gate depends only on when you arrive, so a route's total is decided entirely by how many runs it uses: more runs can never come out quicker. That turns the question into a count. Sweep outwards from depot 1 in layers, recording for each depot the two smallest distinct numbers of runs that reach it, and stop expanding a depot once it has both. The second smallest total is then the total for the second smallest run count reaching depot `n`, which always exists because you can always step onto a neighbour and back. Turn that count into minutes by walking it: at each depot, if the clock currently sits in a shut stretch, push it forward to the next opening, then add the run's minutes. Whether the clock is in a shut stretch is decided by whether the number of whole `change` spans elapsed is odd.

Pythonentry point: second_minimum

def second_minimum(n, edges, time, change):
    from collections import deque
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    best = [-1] * (n + 1)      # fewest runs reaching this depot
    second = [-1] * (n + 1)    # next distinct number of runs reaching it
    best[1] = 0
    queue = deque([(1, 0)])
    while queue:
        node, runs = queue.popleft()
        for nxt in adj[node]:
            step = runs + 1
            if best[nxt] == -1:
                best[nxt] = step
                queue.append((nxt, step))
            elif second[nxt] == -1 and best[nxt] != step:
                second[nxt] = step
                queue.append((nxt, step))
    runs = second[n]
    clock = 0
    for _ in range(runs):
        if (clock // change) % 2 == 1:
            clock = (clock // change + 1) * change
        clock += time
    return clock

The obvious version

Search over arrival times instead of over run counts: keep the two smallest distinct arrival times for every depot and settle them in increasing order, working out the wait at each gate as the route is extended. Makes no use of the runs all costing the same.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_second_minimum(n, edges, time, change):
    import heapq
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    first = [None] * (n + 1)
    other = [None] * (n + 1)
    first[1] = 0
    heap = [(0, 1)]
    while heap:
        at, node = heapq.heappop(heap)
        if other[node] is not None and at > other[node]:
            continue
        leave = at
        if (leave // change) % 2 == 1:
            leave = (leave // change + 1) * change
        for nxt in adj[node]:
            arrive = leave + time
            if first[nxt] is None:
                first[nxt] = arrive
                heapq.heappush(heap, (arrive, nxt))
            elif arrive < first[nxt]:
                if other[nxt] is None or first[nxt] < other[nxt]:
                    other[nxt] = first[nxt]
                first[nxt] = arrive
                heapq.heappush(heap, (arrive, nxt))
            elif arrive > first[nxt] and (other[nxt] is None or arrive < other[nxt]):
                other[nxt] = arrive
                heapq.heappush(heap, (arrive, nxt))
    return other[n]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in