Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Second Minimum Time to Reach Destination solution and explanation

HardBreadth-First SearchGraphShortest Path7 min read62.3% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Second Minimum Time to Reach Destination
22:59
Second Minimum Time to Reach Destination - Leetcode 2045 - PythonNeetCodeIO · 22:59 · 12K viewsWatch on YouTube
9 more videos on this problem
  1. Second Minimum Time to Reach Destination - Leetcode 2045 - PythonNeetCodeIO · 22:59 · 12K views
  2. Second Minimum Time to Reach Destination | 2 Approaches | FULL DRY RUN | Leetcode 2045codestorywithMIK · 1:05:58 · 12K views
  3. LeetCode Weekly 263 | Second Minimum Time to Reach Destination [Hard] (Discussion)soluchan · 12:32 · 2K views
  4. 2045. Second Minimum Time to Reach Destination (Leetcode Hard)Programming Live with Larry · 30:18 · 2K views
  5. Leetcode - 2045. Second Minimum Time to Reach Destination | Dijkstra's AlgorithmRaman Bhari · 38:04 · 1K views
  6. 2045. Second Minimum Time to Reach Destination | graph | Leetcode Daily Challenge | DSA | HindiShashCode · 38:51 · 1K views
  7. 【每日一题】LeetCode 2045. Second Minimum Time to Reach DestinationHuifeng Guan · 25:03 · 1K views
  8. 2045. Second Minimum Time to Reach Destination | Hard | Leetcode Daily (POTD) 28 July 2024 | JavaAlgorithmHQ · 27:47 · 1K views
  9. Daily Leetcode #1580: Jul 28, 2024 - 2045. Second Minimum Time to Reach DestinationProgramming Live with Larry · 22:40 · 758 views
  10. LeetCode 2045 - Second Minimum Time to Reach Destination - JavaAlpha-Code · 25:47 · 231 views

The problem

A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes.

Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.

The second minimum value is defined as the smallest value strictly larger than the minimum value.

  • For example the second minimum value of [2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.

Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.

Notes:

  • You can go through any vertex any number of times, including 1 and n.
  • You can assume that when the journey starts, all signals have just turned green.

Example 1:

        
Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
Output: 13
Explanation:
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
Explanation:
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

Approach overview

Problem Overview: You are given an undirected graph where each edge takes the same travel time, but intersections have traffic signals that alternate between green and red every change minutes. The goal is to reach node n from node 1, not with the shortest travel time, but with the second minimum arrival time while respecting signal delays.

Approach 1: Breadth-First Search with Traffic Signal Simulation (Time: O(E), Space: O(V))

This approach uses Breadth-First Search on the graph while tracking the first and second arrival times for every node. Instead of storing only one distance, maintain two values: the shortest and second shortest arrival time. Each time you move along an edge, compute whether you must wait for the signal. If the current time falls in a red phase ((time / change) % 2 == 1), wait until the next green phase before traveling. Push new arrival times into the BFS queue only if they improve the first or second best time for that node. The algorithm stops once the second arrival time for node n is discovered.

The key insight is that BFS works because all edges have equal traversal time. The additional logic handles signal waiting and ensures each node records up to two unique arrival times.

Approach 2: Modified Dijkstra's Algorithm (Time: O(E log V), Space: O(V))

This method models the problem as a shortest path search where each node can be visited twice with different arrival times. Use a priority queue to always expand the smallest current time. When exploring neighbors, calculate the departure time considering signal cycles: if the light is red, wait until the next green interval before adding edge travel time. Maintain two best arrival times per node and ignore any candidate that is not among the top two.

The modified Dijkstra structure guarantees correct ordering of times, which simplifies reasoning about when the second minimum path is finalized. It works well when you want strict ordering of states and deterministic expansion of earliest arrival times.

Recommended for interviews: The BFS-based solution is usually preferred because all edges have equal weight. Interviewers expect you to recognize that this is a graph traversal problem with multiple valid distances per node. Showing the two-distance tracking technique demonstrates strong understanding of BFS and shortest-path variations, while the Dijkstra variant proves you can generalize the idea when edge weights or timing rules become more complex.

Approach 1: Modified Dijkstra's Algorithm

This approach involves using a priority queue to simulate a modified version of Dijkstra's algorithm, aiming to track both the shortest and second shortest path times to the last node. The cost of each step is affected by traffic signal delays, calculated based on the cumulative time spent traveling.

from heapq import heappop, heappush
from collections import defaultdict

def secondMinimum(n, edges, time, change):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    pq = [(0, 1)] # (current_time, node)
    min_time = [float('inf')] * (n + 1)
    second_min_time = [float('inf')] * (n + 1)
    min_time[1] = 0

    while pq:
        curr_time, node = heappop(pq)

        for neighbor in graph[node]:
            # Calculate the time to wait if traffic light is red
            wait_time = 0
            if (curr_time // change) % 2 == 1:
                wait_time = change - (curr_time % change)
            new_time = curr_time + wait_time + time

            if new_time < min_time[neighbor]:
                second_min_time[neighbor] = min_time[neighbor]
                min_time[neighbor] = new_time
                heappush(pq, (new_time, neighbor))
            elif min_time[neighbor] < new_time < second_min_time[neighbor]:
                second_min_time[neighbor] = new_time
                heappush(pq, (new_time, neighbor))

    return second_min_time[n]
import java.util.*;

public class SecondMinimumTime {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, 1}); // (current_time, node)
        int[] minTime = new int[n + 1];
        int[] secondMinTime = new int[n + 1];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        Arrays.fill(secondMinTime, Integer.MAX_VALUE);
        minTime[1] = 0;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currTime = current[0], node = current[1];

            for (int neighbor : graph[node]) {
                int waitTime = 0;
                if ((currTime / change) % 2 == 1) {
                    waitTime = change - (currTime % change);
                }
                int newTime = currTime + waitTime + time;

                if (newTime < minTime[neighbor]) {
                    secondMinTime[neighbor] = minTime[neighbor];
                    minTime[neighbor] = newTime;
                    pq.offer(new int[]{newTime, neighbor});
                } else if (newTime < secondMinTime[neighbor] && newTime > minTime[neighbor]) {
                    secondMinTime[neighbor] = newTime;
                    pq.offer(new int[]{newTime, neighbor});
                }
            }
        }

        return secondMinTime[n];
    }
}
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
    vector<vector<int>> graph(n + 1);
    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    vector<int> first_min(n + 1, INT_MAX);
    vector<int> second_min(n + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.emplace(0, 1);
    first_min[1] = 0;

    while (!pq.empty()) {
        auto [curr_time, node] = pq.top();
        pq.pop();

        for (int neighbor : graph[node]) {
            int wait_time = 0;
            if ((curr_time / change) % 2 == 1) {
                wait_time = change - (curr_time % change);
            }
            int new_time = curr_time + wait_time + time;

            if (new_time < first_min[neighbor]) {
                second_min[neighbor] = first_min[neighbor];
                first_min[neighbor] = new_time;
                pq.emplace(new_time, neighbor);
            } else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
                second_min[neighbor] = new_time;
                pq.emplace(new_time, neighbor);
            }
        }
    }

    return second_min[n];
}
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int *data;
    int size;
    int capacity;
} intVector;

void push(intVector *vec, int val) {
    if (vec->size == vec->capacity) {
        vec->capacity *= 2;
        vec->data = realloc(vec->data, vec->capacity * sizeof(int));
    }
    vec->data[vec->size++] = val;
}

int pop(intVector *vec) {
    return vec->data[--vec->size];
}

int secondMinimum(int n, int edges[][2], int edgesSize, int time, int change) {
    intVector *graph = malloc((n + 1) * sizeof(intVector));
    for (int i = 1; i <= n; ++i) {
        graph[i].data = malloc(10 * sizeof(int));
        graph[i].size = 0;
        graph[i].capacity = 10;
    }
    
    for (int i = 0; i < edgesSize; ++i) {
        push(&graph[edges[i][0]], edges[i][1]);
        push(&graph[edges[i][1]], edges[i][0]);
    }

    int *first_min = malloc((n + 1) * sizeof(int));
    int *second_min = malloc((n + 1) * sizeof(int));
    
    for (int i = 1; i <= n; ++i) {
        first_min[i] = INT_MAX;
        second_min[i] = INT_MAX;
    }
    first_min[1] = 0;

    int pq[200000][2];
    int pq_size = 0;
    pq[pq_size][0] = 0;
    pq[pq_size++][1] = 1;

    while (pq_size > 0) {
        int curr_time = pq[--pq_size][0];
        int node = pq[pq_size][1];

        for (int i = 0; i < graph[node].size; ++i) {
            int neighbor = graph[node].data[i];
            int wait_time = 0;
            if ((curr_time / change) % 2 == 1) {
                wait_time = change - (curr_time % change);
            }
            int new_time = curr_time + wait_time + time;

            if (new_time < first_min[neighbor]) {
                second_min[neighbor] = first_min[neighbor];
                first_min[neighbor] = new_time;
                pq[pq_size][0] = new_time;
                pq[pq_size++][1] = neighbor;
            } else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
                second_min[neighbor] = new_time;
                pq[pq_size][0] = new_time;
                pq[pq_size++][1] = neighbor;
            }
        }
    }

    free(first_min);
    free(second_min);
    for (int i = 1; i <= n; ++i) {
        free(graph[i].data);
    }
    free(graph);
    return second_min[n];
}

This solution builds a graph using an adjacency list. We use a priority queue to explore paths encapsulated by their current time and destination node. For each node, we maintain two arrays to keep track of the first and second minimum time taken to reach it. The algorithm updates these values by considering wait times if a traffic light is red. We return the second minimum time to reach the destination node.

Complexity

The time complexity is O(E log V), where E is the number of edges, and V is the number of vertices, due to the priority queue operations. The space complexity is O(V + E) due to the storage of the adjacency list and the min_time/second_min_time arrays.

Try this approach in the editor

Approach 2: Breadth-First Search with Traffic Signal Consideration

This approach leverages a Breadth-First Search (BFS) to explore paths in level order, carefully managing path times with respect to traffic signal cycles. Time values are stored to identify both the shortest and second shortest paths throughout the search.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int secondMinimumBFS(int n, vector<vector<int>>& edges, int time, int change) {
    vector<vector<int>> graph(n + 1);
    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    vector<int> first_min(n + 1, INT_MAX);
    vector<int> second_min(n + 1, INT_MAX);
    queue<pair<int, int>> q;
    q.push({0, 1});
    first_min[1] = 0;

    while (!q.empty()) {
        auto [curr_time, node] = q.front();
        q.pop();

        for (int neighbor : graph[node]) {
            int wait_time = 0;
            if ((curr_time / change) % 2 == 1) {
                wait_time = change - (curr_time % change);
            }
            int new_time = curr_time + wait_time + time;

            if (new_time < first_min[neighbor]) {
                second_min[neighbor] = first_min[neighbor];
                first_min[neighbor] = new_time;
                q.push({new_time, neighbor});
            } else if (new_time > first_min[neighbor] && new_time < second_min[neighbor]) {
                second_min[neighbor] = new_time;
                q.push({new_time, neighbor});
            }
        }
    }

    return second_min[n];
}
const secondMinimum = (n, edges, time, change) => {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }

    const firstMinTime = Array(n + 1).fill(Infinity);
    const secondMinTime = Array(n + 1).fill(Infinity);
    firstMinTime[1] = 0;
    const queue = [[0, 1]];

    while (queue.length) {
        const [currTime, currNode] = queue.shift();

        for (const neighbor of graph[currNode]) {
            let waitTime = 0;
            if (Math.floor(currTime / change) % 2 === 1) {
                waitTime = change - (currTime % change);
            }
            const newTime = currTime + waitTime + time;

            if (newTime < firstMinTime[neighbor]) {
                secondMinTime[neighbor] = firstMinTime[neighbor];
                firstMinTime[neighbor] = newTime;
                queue.push([newTime, neighbor]);
            } else if (newTime > firstMinTime[neighbor] && newTime < secondMinTime[neighbor]) {
                secondMinTime[neighbor] = newTime;
                queue.push([newTime, neighbor]);
            }
        }
    }

    return secondMinTime[n];
};
using System;
using System.Collections.Generic;

public class Solution {
    public int SecondMinimum(int n, int[][] edges, int time, int change) {
        var graph = new List<int>[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new List<int>();

        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        var firstMinTime = new int[n + 1];
        var secondMinTime = new int[n + 1];
        Array.Fill(firstMinTime, int.MaxValue);
        Array.Fill(secondMinTime, int.MaxValue);
        firstMinTime[1] = 0;

        var queue = new Queue<(int, int)>(); // (current_time, node)
        queue.Enqueue((0, 1));

        while (queue.Count > 0) {
            var (currTime, currNode) = queue.Dequeue();

            foreach (var neighbor in graph[currNode]) {
                int waitTime = 0;
                if ((currTime / change) % 2 == 1) {
                    waitTime = change - (currTime % change);
                }
                int newTime = currTime + waitTime + time;

                if (newTime < firstMinTime[neighbor]) {
                    secondMinTime[neighbor] = firstMinTime[neighbor];
                    firstMinTime[neighbor] = newTime;
                    queue.Enqueue((newTime, neighbor));
                } else if (newTime > firstMinTime[neighbor] && newTime < secondMinTime[neighbor]) {
                    secondMinTime[neighbor] = newTime;
                    queue.Enqueue((newTime, neighbor));
                }
            }
        }

        return secondMinTime[n];
    }
}

This C++ adaptation employs breadth-first search, focusing on level-order operations enhanced by queue structures. It updates node transition times efficiently across iterations to tally and compare shortest available routes effectively.

Complexity

The algorithm features a time complexity of O(E) as it proceeds through all edges within the BFS proximity and a space complexity of O(V + E) due to adjacency and time tracking storage requirements.

Try this approach in the editor

Complexity comparison

ApproachComplexity
Modified Dijkstra's Algorithm

The time complexity is O(E log V), where E is the number of edges, and V is the number of vertices, due to the priority queue operations. The space complexity is O(V + E) due to the storage of the adjacency list and the min_time/second_min_time arrays.

Breadth-First Search with Traffic Signal Consideration

The algorithm features a time complexity of O(E) as it proceeds through all edges within the BFS proximity and a space complexity of O(V + E) due to adjacency and time tracking storage requirements.

Complexity analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search with Signal SimulationO(E)O(V)Best when all edges have equal travel time and you only need the first and second arrival times.
Modified Dijkstra's AlgorithmO(E log V)O(V)Useful when reasoning about ordered arrival times or when extending to weighted edges.

Frequently asked questions

Is Second Minimum Time to Reach Destination easy or hard?

Second Minimum Time to Reach Destination is classified as a Hard problem. The challenge comes from combining graph traversal with traffic signal timing and tracking the second shortest arrival instead of the first.

Second Minimum Time to Reach Destination Python/Java solution

Implement the BFS approach using an adjacency list and a queue. Maintain two distances for every node and simulate traffic signal delays before traversing edges. The same logic translates directly across Python, Java, and C++ with minor syntax differences.

How to solve Second Minimum Time to Reach Destination in O(E)?

Use BFS on the graph while storing two distinct arrival times for every node. During traversal, compute signal waiting time before moving across an edge. Only push a new state if it improves either the shortest or second shortest time for that node. Once the destination receives its second arrival time, return it.

What is the best approach for Second Minimum Time to Reach Destination?

Breadth-First Search with two arrival times per node is the most efficient approach when all edges have equal travel time. The algorithm tracks the shortest and second shortest times for each node while simulating traffic signal delays. This runs in O(E) time and O(V) space and directly returns the second arrival time at the destination.

Is Second Minimum Time to Reach Destination asked at Google/Amazon/Meta?

This problem represents a typical hard graph traversal question similar to those used in interviews at companies like Amazon, Google, and Meta. Variants involving second shortest paths, traffic signals, or multiple distance tracking frequently appear in senior-level algorithm interviews.

What data structure is used in Second Minimum Time to Reach Destination?

The core data structures are an adjacency list to represent the graph and a queue for BFS traversal. Each node stores two arrival times to track the shortest and second shortest paths. The Dijkstra variant additionally uses a min-heap priority queue.

What is the time complexity of Second Minimum Time to Reach Destination?

The BFS-based solution runs in O(E) time because each edge is processed a limited number of times while maintaining two arrival times per node. A modified Dijkstra implementation takes O(E log V) due to the priority queue operations. Space complexity for both approaches is O(V).

Comments

Next problem · similarNetwork Delay TimeMedium
Now write it yourselfClose this page and solve Second Minimum Time to Reach Destination in the editor, without looking.
Practise Second Minimum Time to Reach Destination