Second Minimum Time to Reach Destination

Hard
1533.

Second Minimum Time to Reach Destination

Second Minimum Time to Reach Destination is a hard coding problem on breadth-first search, graph and shortest path, asked in Amazon and Google interviews.

A city has n junctions labelled 1 to n, joined by the two-way roads in edges (each [ui, vi]). The road network is connected, has no duplicate roads and no road from a junction to itself. Crossing any road takes exactly time minutes.

Every junction has a traffic signal. All signals switch together every change minutes, alternating green and red, and they all turn green at minute 0. You may arrive at a junction at any moment, but you may leave it only while its signal is green — and if it is green you must leave at once rather than wait.

The second minimum time is the smallest journey time from junction 1 to junction n that is strictly larger than the minimum. Junctions (including 1 and n) may be revisited. Return the second minimum time.

Example 1

Input
n = 4, edges = [[1,2],[2,4],[1,3],[3,4],[2,3]], time = 2, change = 3
Output
8
Explanation
The fastest route 1 → 2 → 4 takes 4 minutes. The next is 1 → 2 → 3 → 4: you reach 3 at minute 4, while signals are red (minutes 3–5), leave at 6 and arrive at 8.

Example 2

Input
n = 2, edges = [[1,2]], time = 4, change = 7
Output
18
Explanation
Go 1 → 2 → 1 → 2: arrive at 4 and 8, wait for green until 14, arrive at 18.

Constraints

  • 2 <= n <= 10^4
  • n - 1 <= edges.length <= min(2 * 10^4, n * (n - 1) / 2)
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • no duplicate edges; the graph is connected
  • 1 <= time, change <= 10^3
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} time
 * @param {number} change
 * @return {number}
 */
var secondMinimum = function(n, edges, time, change) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Second Minimum Time to Reach Destination — Solution

Second Minimum Time to Reach Destination solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Second Minimum Time to Reach Destination is a hard coding problem on breadth-first search, graph and shortest path, asked in Amazon and Google interviews.

Problem statement

A city has n junctions labelled 1 to n, joined by the two-way roads in edges (each [ui, vi]). The road network is connected, has no duplicate roads and no road from a junction to itself. Crossing any road takes exactly time minutes.

Every junction has a traffic signal. All signals switch together every change minutes, alternating green and red, and they all turn green at minute 0. You may arrive at a junction at any moment, but you may leave it only while its signal is green — and if it is green you must leave at once rather than wait.

The second minimum time is the smallest journey time from junction 1 to junction n that is strictly larger than the minimum. Junctions (including 1 and n) may be revisited. Return the second minimum time.

Example 1

Input: n = 4, edges = [[1,2],[2,4],[1,3],[3,4],[2,3]], time = 2, change = 3
Output: 8
Explanation: The fastest route 1 → 2 → 4 takes 4 minutes. The next is 1 → 2 → 3 → 4: you reach 3 at minute 4, while signals are red (minutes 3–5), leave at 6 and arrive at 8.

Example 2

Input: n = 2, edges = [[1,2]], time = 4, change = 7
Output: 18
Explanation: Go 1 → 2 → 1 → 2: arrive at 4 and 8, wait for green until 14, arrive at 18.

Constraints

  • 2 <= n <= 10^4
  • n - 1 <= edges.length <= min(2 * 10^4, n * (n - 1) / 2)
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • no duplicate edges; the graph is connected
  • 1 <= time, change <= 10^3

Hints for Second Minimum Time to Reach Destination

  1. Hint 1

    Every road takes the same time and the signals are global, so the journey time depends only on the number of roads crossed — and it grows with that number.

  2. Hint 2

    So find the second smallest number of roads on a walk from 1 to n (strictly more than the smallest). It is always at most the smallest plus 2, by stepping back and forth on a road.

  3. Hint 3

    Run a BFS that records up to two distinct distances per junction (the best and the strictly second best), then simulate the signals for that many roads.

How to solve Second Minimum Time to Reach Destination

Because all roads cost the same and the signals are synchronised, the arrival time is a strictly increasing function of the number of roads used. The problem becomes: find the second-smallest walk length from 1 to n, then convert it to minutes.

Approach

  1. BFS from junction 1 keeping two labels per node: d1 (shortest) and d2 (smallest length strictly greater than d1).
  2. When relaxing a neighbour with length L: if L < d1, set d1 = L and enqueue; else if d1 < L < d2, set d2 = L and enqueue.
  3. Take k = d2[n] and simulate: before each road, if floor(t / change) is odd the signal is red, so jump to the next multiple of change; then add time.
  4. Return the resulting t.

Why it works

Lengths are popped in non-decreasing order, so each node is finalised with its two smallest distinct walk lengths after at most two visits. The waiting rule depends only on the current minute, so k roads always take the same total time, and more roads never take less time; hence the second minimum time comes from the second minimum walk length.

Complexity

  • Time — O(n + m)
  • Space — O(n + m)

Pitfalls

  • The second length must be strictly greater — record a node a second time only for a different length.
  • Walks may revisit nodes, so the second shortest can be the shortest plus 2 (bounce on a road).
  • Do not wait at the destination: the time counts when you arrive at n, so only signals before each departure matter.

Reference solution

Python

from typing import List
from collections import deque

def secondMinimum(n: int, edges: List[List[int]], time: int, change: int) -> int:
    adj = [[] for _ in range(n + 1)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    INF = 10 ** 9
    d1 = [INF] * (n + 1)
    d2 = [INF] * (n + 1)
    d1[1] = 0
    q = deque([(1, 0)])
    while q:
        u, d = q.popleft()
        nd = d + 1
        for v in adj[u]:
            if nd < d1[v]:
                d1[v] = nd
                q.append((v, nd))
            elif d1[v] < nd < d2[v]:
                d2[v] = nd
                q.append((v, nd))
    t = 0
    for _ in range(d2[n]):
        if (t // change) % 2 == 1:
            t = (t // change + 1) * change
        t += time
    return t

Java

public static int secondMinimum(int n, int[][] edges, int time, int change) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    final int INF = Integer.MAX_VALUE;
    int[] d1 = new int[n + 1], d2 = new int[n + 1];
    Arrays.fill(d1, INF);
    Arrays.fill(d2, INF);
    d1[1] = 0;
    int[] qn = new int[2 * n + 2], qd = new int[2 * n + 2];
    int head = 0, tail = 0;
    qn[tail] = 1;
    qd[tail++] = 0;
    while (head < tail) {
        int u = qn[head], nd = qd[head] + 1;
        head++;
        for (int v : adj.get(u)) {
            if (nd < d1[v]) { d1[v] = nd; qn[tail] = v; qd[tail++] = nd; }
            else if (nd > d1[v] && nd < d2[v]) { d2[v] = nd; qn[tail] = v; qd[tail++] = nd; }
        }
    }
    int t = 0;
    for (int s = 0; s < d2[n]; s++) {
        if ((t / change) % 2 == 1) t = (t / change + 1) * change;
        t += time;
    }
    return t;
}

C++

int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
    vector<vector<int>> adj(n + 1);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    const int INF = INT_MAX;
    vector<int> d1(n + 1, INF), d2(n + 1, INF), qn, qd;
    d1[1] = 0;
    qn.push_back(1);
    qd.push_back(0);
    for (size_t h = 0; h < qn.size(); h++) {
        int u = qn[h], nd = qd[h] + 1;
        for (int v : adj[u]) {
            if (nd < d1[v]) { d1[v] = nd; qn.push_back(v); qd.push_back(nd); }
            else if (nd > d1[v] && nd < d2[v]) { d2[v] = nd; qn.push_back(v); qd.push_back(nd); }
        }
    }
    int t = 0;
    for (int s = 0; s < d2[n]; s++) {
        if ((t / change) % 2 == 1) t = (t / change + 1) * change;
        t += time;
    }
    return t;
}

JavaScript

var secondMinimum = function(n, edges, time, change) {
    var adj = [];
    for (var i = 0; i <= n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    var INF = 1000000000;
    var d1 = [], d2 = [];
    for (var k = 0; k <= n; k++) { d1.push(INF); d2.push(INF); }
    d1[1] = 0;
    var qn = [1], qd = [0];
    for (var h = 0; h < qn.length; h++) {
        var u = qn[h], nd = qd[h] + 1;
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (nd < d1[v]) { d1[v] = nd; qn.push(v); qd.push(nd); }
            else if (nd > d1[v] && nd < d2[v]) { d2[v] = nd; qn.push(v); qd.push(nd); }
        }
    }
    var t = 0;
    for (var s = 0; s < d2[n]; s++) {
        if (Math.floor(t / change) % 2 === 1) t = (Math.floor(t / change) + 1) * change;
        t += time;
    }
    return t;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Graph Data Structure