2045. Second Minimum Time to Reach Destination

Second Minimum Time to Reach Destination (LeetCode 2045) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

How to solve Second Minimum Time to Reach Destination

Second Minimum Time to Reach Destination is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Work towards the solution in these steps:

1. How much is change actually necessary while calculating the required path?
2. How many extra edges do we need to add to the shortest path?

The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.

The Second Minimum Time to Reach Destination solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Breadth-First Search, Graph, Shortest Path.

How to practise Second Minimum Time to Reach Destination on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.

Open Second Minimum Time to Reach Destination in the code editor, or read the Second Minimum Time to Reach Destination editorial for a worked solution with its approach and complexity analysis.

Where Second Minimum Time to Reach Destination sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Dijkstra's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Second Minimum Time to Reach Destination

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Find the Safest Path in a Grid — Medium, same subpattern
• Minimum Obstacle Removal to Reach Corner — Hard, same subpattern
• Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
• Minimum Weighted Subgraph With the Required Paths — Hard, same subpattern
• Network Delay Time — Medium, same subpattern
• Number of Ways to Arrive at Destination — Medium, same subpattern

Second Minimum Time to Reach Destination FAQ