Second Minimum Time to Reach Destination

Tested Python solution for LeetCode 2045 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2045, Hard. Topics: Breadth-First Search, Graph Theory, Shortest Path. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2045   # by problem number
lcpy gen -s second_minimum_time_to_reach_destination   # by problem name

​

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] = [u<sub>i</sub>, v<sub>i</sub>] denotes a bi-directional edge between vertex u<sub>i</sub> and vertex v<sub>i</sub>. 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.

​

Examples

       

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

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 <= 10<sup>4</sup>
• n - 1 <= edges.length <= min(2 * 10<sup>4</sup>, n * (n - 1) / 2)
• edges[i].length == 2
• 1 <= u<sub>i</sub>, v<sub>i</sub> <= n
• u<sub>i</sub> != v<sub>i</sub>
• There are no duplicate edges.
• Each vertex can be reached directly or indirectly from every other vertex.
• 1 <= time, change <= 10<sup>3</sup>

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class Solution:
    # Time: O(n + m) BFS plus O(second_path_length) for the signal simulation
    # Space: O(n + m)
    def second_minimum(self, n: int, edges: list[list[int]], time: int, change: int) -> int:
        adj: list[list[int]] = [[] for _ in range(n + 1)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        # two smallest distinct arrival edge-counts per vertex (BFS order)
        dists: list[list[int]] = [[] for _ in range(n + 1)]
        dists[1].append(0)
        queue: deque[tuple[int, int]] = deque([(1, 0)])
        while queue:
            node, steps = queue.popleft()
            for nb in adj[node]:
                nxt = steps + 1
                if len(dists[nb]) < 2 and nxt not in dists[nb]:
                    dists[nb].append(nxt)
                    queue.append((nb, nxt))

        elapsed = 0
        for _ in range(dists[n][1]):
            if (elapsed // change) % 2 == 1:
                elapsed = (elapsed // change + 1) * change
            elapsed += time
        return elapsed

​

Complexity

Time	Space
O(n + m) BFS plus O(second_path_length) for the signal simulation	O(n + m)

​

Tags

NeetCode All.