LeetCode 2045 - Second Minimum Time to Reach Destination

LeetCode Problem 2045

Difficulty: 🔴 Hard
Topics: Breadth-First Search, Graph Theory, Shortest Path

Solution

Here is a comprehensive technical solution guide for LeetCode 2045 following your requested format:

Problem Understanding

The problem asks us to find the second minimum time to travel from vertex 1 to vertex n in a weighted, undirected graph, where the weight of every edge is the same (time). The twist is that each vertex has a traffic signal that alternates between green and red every change minutes. We can leave a vertex only when the signal is green, but we can enter it at any time.

The input consists of the number of vertices n, a list of edges edges, and two integers time and change. The output is a single integer representing the second minimum travel time from vertex 1 to vertex n. The second minimum is strictly larger than the minimum time.

Key points about the input:

The graph is connected and has no self-loops or duplicate edges.
The time to traverse any edge is uniform.
Traffic lights can force waiting if we arrive at a red signal.
The journey can revisit vertices, including the start and end.

Important edge cases include:

Graphs where the shortest path is also a cycle - second minimum might require revisiting nodes.
Signals changing at times that require waiting, potentially elongating a path to become the second minimum.
Graphs with multiple paths of equal minimum length, where timing at signals determines which path is second minimum.

Approaches

Brute Force Approach

A brute force solution would enumerate all possible paths from vertex 1 to n, calculate the total travel time for each path considering the traffic signals, and then pick the second smallest value. This approach is guaranteed correct because it explores all possibilities, but it is infeasible for large n because the number of paths grows exponentially.

Optimal Approach

The optimal approach leverages a modified BFS. Instead of tracking just the shortest time to reach each vertex, we track the first and second shortest arrival times. BFS naturally finds paths in increasing order of steps, and by computing the actual time considering traffic lights, we can maintain the invariant that for each vertex we know the two smallest times at which it can be reached.

The key observation is that, even with traffic signals, the time to leave a vertex is deterministic given the arrival time, so we can simulate waiting for green lights easily. By storing two times per vertex, BFS ensures we capture both the minimum and second minimum times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(2^n)	Enumerate all paths from 1 to n, consider traffic signals
Optimal	O(E log V)	O(V)	Modified BFS storing two smallest times per vertex

Algorithm Walkthrough

Graph Representation: Build an adjacency list from the edges for efficient neighbor lookup.
Time Tracking: For each vertex, maintain a list of the two smallest times it can be reached. Initialize vertex 1 with [0].
BFS Queue: Use a queue of (current_vertex, elapsed_time) to process vertices in order of path traversal.
Simulate Traffic Signals: For each vertex visited, compute whether we need to wait for green signal using elapsed_time and change. If we are in a red period, wait until green.
Update Times: If the newly computed time for a neighbor is smaller than any recorded times and it is distinct, append it. Maintain only the first two smallest times per vertex.
BFS Termination: When the second smallest time for the target vertex n is discovered, return it.

Why it works: BFS guarantees we explore paths in increasing step order, and maintaining two arrival times per vertex ensures we capture the second minimum time. Simulating the traffic signals ensures we correctly account for waiting periods.

Python Solution

from collections import deque
from typing import List

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        # Build graph
        graph = [[] for _ in range(n + 1)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Store the first and second shortest arrival times for each node
        times = [[] for _ in range(n + 1)]
        queue = deque([(1, 0)])  # (node, elapsed_time)
        times[1].append(0)
        
        while queue:
            node, elapsed = queue.popleft()
            
            for neighbor in graph[node]:
                # Compute waiting time due to traffic signal
                cycles = elapsed // change
                if cycles % 2 == 1:
                    # Currently red, wait until green
                    wait = change - (elapsed % change)
                else:
                    wait = 0
                next_time = elapsed + wait + time
                
                if len(times[neighbor]) < 2 and next_time not in times[neighbor]:
                    times[neighbor].append(next_time)
                    queue.append((neighbor, next_time))
        
        # Return second minimum time
        return sorted(times[n])[1]

This Python implementation builds the adjacency list, simulates BFS while computing waiting times due to signals, and keeps track of the first two distinct times to reach each node. Sorting the times at the target ensures we return the second minimum.

Go Solution

package main

func secondMinimum(n int, edges [][]int, time int, change int) int {
    graph := make([][]int, n+1)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    times := make([][]int, n+1)
    queue := [][2]int{{1, 0}} // {node, elapsed}
    times[1] = append(times[1], 0)

    for len(queue) > 0 {
        node, elapsed := queue[0][0], queue[0][1]
        queue = queue[1:]

        for _, neighbor := range graph[node] {
            cycles := elapsed / change
            wait := 0
            if cycles%2 == 1 {
                wait = change - (elapsed % change)
            }
            nextTime := elapsed + wait + time

            if len(times[neighbor]) < 2 {
                distinct := true
                for _, t := range times[neighbor] {
                    if t == nextTime {
                        distinct = false
                        break
                    }
                }
                if distinct {
                    times[neighbor] = append(times[neighbor], nextTime)
                    queue = append(queue, [2]int{neighbor, nextTime})
                }
            }
        }
    }

    if times[n][0] < times[n][1] {
        return times[n][1]
    }
    return times[n][0]
}

In Go, we explicitly handle duplicate checks and slices for each node. Go's slice semantics require careful handling of the queue and append operations.

Worked Examples

Example 1: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5

Step	Node	Elapsed	Queue	Notes
0	1	0	[(1,0)]	Start
1	1	0	[(2,3),(3,3),(4,3)]	All neighbors reachable without wait
2	2	3	...	Process 2
3	3	3	...	Process 3, next_time = 6
4	4	3	...	Process 4, waits until green for second path, next_time = 10
5	5	6	...	Second minimum = 13

Example 2: n = 2, edges = [[1,2]], time = 3, change = 2

Minimum path: 1 -> 2, time = 3
Second minimum path: 1 -> 2 -> 1 -> 2, accounting for red signals, time = 11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E)	BFS explores each edge at most twice (two times per node)
Space	O(V + E)	Adjacency list + two times per vertex + queue

The BFS is efficient because we only track two times per node, and the number of edges is bounded by constraints.

Test Cases

# Example 1
assert Solution().secondMinimum(5, [[1,2],[1,3],[1,4],[3,4],[4,5]], 3, 5) == 13  # second minimum path
# Example 2
assert Solution().secondMinimum(2, [[1,2]], 3, 2) == 11  # revisiting nodes
# Minimum size
assert Solution().secondMinimum(2, [[1,2]], 1, 1) == 3  # only two nodes, minimal path