Brute Force Approach for Second Minimum Time to Reach Destination

A naive approach to finding the second minimum time would be to use Depth-First Search (DFS) to explore all possible paths from the source to the destination. Since we need the second minimum, we cannot simply stop after finding one path; we must enumerate paths to find the sorted order of their total durations.

Naive Pseudo-code

text
function dfs(current_node, current_time, visited_path):
    if current_node == n:
        add current_time to found_times
        return

    calculate wait_time based on current_time
    arrival_time = current_time + wait_time + edge_time

    for neighbor in adj[current_node]:
        # Allow revisiting nodes to find longer paths
        if path_length < limit: 
            dfs(neighbor, arrival_time, visited_path + [neighbor])

Analysis and Failure

The time complexity of this brute force approach is exponential. The graph contains cycles (it is undirected), and the problem statement explicitly allows visiting vertices multiple times (e.g., 1 -> 2 -> 1 -> 2 -> ...). Without a strict bound on path length, the recursion depth can be infinite. Even with a bound, the number of paths grows factorially with the number of nodes. Given the constraints $N \le 10^4$, this approach will immediately result in a Time Limit Exceeded (TLE) error.

Core Insight for Second Minimum Time to Reach Destination

The key intuition is to generalize Dijkstra's algorithm (or BFS) from tracking just the minimum distance to tracking the top k minimum distances.

In a standard shortest path algorithm, we maintain an array dist[i] representing the shortest time to reach node i. If we find a new path to i with time t where t < dist[i], we update dist[i].

For LeetCode 2045, we need the second minimum. Therefore, we maintain two values for each node:

1. dist1[i]: The minimum time to reach node i.
2. dist2[i]: The strictly second minimum time to reach node i.

The Invariant: We process nodes in increasing order of arrival time. When we extract a node u with time t from our queue, we attempt to travel to its neighbors v. The arrival time at v will be t_arrival.

• If t_arrival is strictly less than dist1[v], we have found a new shortest path. We update dist1[v] and push to the queue.
• If t_arrival is strictly greater than dist1[v] but strictly less than dist2[v], we have found the second shortest path. We update dist2[v] and push to the queue.
• If t_arrival equals dist1[v] or is greater than dist2[v], we ignore it.

Traffic Light Logic: The edge weight is dynamic. Before traversing an edge, we check the current time t.

• The signal cycle length is 2 * change.
• If (t % (2 * change)) is in the range [change, 2 * change), the light is red.
• We must wait until the cycle completes. The wait time is (2 * change) - (t % (2 * change)).
• If the light is green, the wait time is 0.

Visual Description: Imagine the algorithm as a wave expanding from the source. The first time the wave hits a node, that's the minimum time (dist1). Because we allow re-visiting nodes, the wave can "bounce back" or take a slightly longer detour. The second distinct time the wave hits that same node is recorded as dist2. The queue manages these wave fronts, ensuring we always process the earliest events first.

Execution Flow

Let's trace the logic with n = 2, edges = [[1,2]], time = 3, change = 2.

1. Init:

   • dist1 = [INF, 0, INF], dist2 = [INF, INF, INF].
   • Queue: [(1, 0)] (Node 1, time 0).

2. Pop (1, 0):

   • Check signal at time 0. 0 % 4 = 0 (Green). No wait.
   • Travel to neighbor 2. arrival = 0 + 3 = 3.
   • Update Node 2: 3 < dist1[2]. dist1[2] = 3.
   • Queue: [(2, 3)].

3. Pop (2, 3):

   • Check signal at time 3. Cycle is 2 * 2 = 4. 3 % 4 = 3.
   • 3 >= change (2), so it is Red.
   • Wait until next green (time 4). Wait time = 4 - 3 = 1.
   • Depart at 4. Travel to neighbor 1. arrival = 4 + 3 = 7.
   • Update Node 1: 7 > dist1[1] (0) and 7 < dist2[1] (INF).
   • dist2[1] = 7.
   • Queue: [(1, 7)].

4. Pop (1, 7):

   • Check signal at time 7. 7 % 4 = 3. Red.
   • Wait until 8.
   • Depart at 8. Travel to neighbor 2. arrival = 8 + 3 = 11.
   • Update Node 2: 11 > dist1[2] (3) and 11 < dist2[2] (INF).
   • dist2[2] = 11.
   • Queue: [(2, 11)].

5. Result:

   • We found dist2[2], which is 11.

Proof of Correctness

The correctness relies on the properties of Breadth-First Search on graphs with non-negative edge weights. BFS explores layers of the graph based on the number of edges (or total weight in the case of Dijkstra).

1. Monotonicity: The arrival times extracted from the queue are non-decreasing.
2. Completeness: By maintaining dist1 and dist2, we implicitly explore all simple paths and paths with cycles that could potentially be the second shortest.
3. Strict Inequality: The condition arrival_time > dist1[v] ensures we satisfy the problem requirement that the second minimum must be strictly larger than the minimum.
4. Termination: Since we only push to the queue when we find a strictly better dist1 or dist2, and weights are positive, updates are finite. The algorithm terminates.

Reference Implementation

C++ Solution for LeetCode 2045

cpp
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        // Build adjacency list
        vector<vector<int>> adj(n + 1);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        // dist1 stores the minimum time, dist2 stores the second minimum time
        vector<int> dist1(n + 1, INT_MAX);
        vector<int> dist2(n + 1, INT_MAX);
        
        // Queue for BFS: stores {node, current_time}
        queue<pair<int, int>> q;
        q.push({1, 0});
        dist1[1] = 0;

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

            // Calculate wait time due to traffic signal
            // Cycle length is 2 * change (Green -> Red)
            int cycle = 2 * change;
            int timeInCycle = currTime % cycle;
            int waitTime = 0;
            
            // If in the red phase (change <= timeInCycle < 2*change), wait
            if (timeInCycle >= change) {
                waitTime = cycle - timeInCycle;
            }
            
            // Time when we arrive at the neighbor
            int arrivalTime = currTime + waitTime + time;

            for (int v : adj[u]) {
                // If we found a strictly better minimum time
                if (arrivalTime < dist1[v]) {
                    dist2[v] = dist1[v]; // Old min becomes second min
                    dist1[v] = arrivalTime;
                    q.push({v, arrivalTime});
                }
                // If we found a strictly better second minimum time
                else if (arrivalTime > dist1[v] && arrivalTime < dist2[v]) {
                    dist2[v] = arrivalTime;
                    q.push({v, arrivalTime});
                }
            }
        }

        return dist2[n];
    }
};

Java Solution for LeetCode 2045

java
import java.util.*;

class Solution {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        // Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // Arrays to track min and second min times
        int[] dist1 = new int[n + 1];
        int[] dist2 = new int[n + 1];
        Arrays.fill(dist1, Integer.MAX_VALUE);
        Arrays.fill(dist2, Integer.MAX_VALUE);

        // BFS Queue: stores {node, time}
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{1, 0});
        dist1[1] = 0;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0];
            int currTime = curr[1];

            // Calculate wait time
            int cycle = 2 * change;
            int timeInCycle = currTime % cycle;
            int waitTime = 0;
            if (timeInCycle >= change) {
                waitTime = cycle - timeInCycle;
            }

            int arrivalTime = currTime + waitTime + time;

            for (int v : adj.get(u)) {
                // Update minimum time
                if (arrivalTime < dist1[v]) {
                    dist2[v] = dist1[v];
                    dist1[v] = arrivalTime;
                    q.offer(new int[]{v, arrivalTime});
                }
                // Update second minimum time
                else if (arrivalTime > dist1[v] && arrivalTime < dist2[v]) {
                    dist2[v] = arrivalTime;
                    q.offer(new int[]{v, arrivalTime});
                }
            }
        }

        return dist2[n];
    }
}

Python Solution for LeetCode 2045

python
from collections import deque, defaultdict
import math

class Solution:
    def secondMinimum(self, n: int, edges: list[list[int]], time: int, change: int) -> int:
        # Build adjacency list
        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            
        # dist1 stores min time, dist2 stores second min time
        dist1 = [float('inf')] * (n + 1)
        dist2 = [float('inf')] * (n + 1)
        
        # Queue for BFS: (node, current_time)
        q = deque([(1, 0)])
        dist1[1] = 0
        
        while q:
            u, curr_time = q.popleft()
            
            # Calculate wait time
            # Cycle is 2 * change
            cycle = 2 * change
            time_in_cycle = curr_time % cycle
            
            wait_time = 0
            # If in Red phase
            if time_in_cycle >= change:
                wait_time = cycle - time_in_cycle
            
            arrival_time = curr_time + wait_time + time
            
            for v in adj[u]:
                # Found new minimum
                if arrival_time < dist1[v]:
                    dist2[v] = dist1[v]
                    dist1[v] = arrival_time
                    q.append((v, arrival_time))
                # Found new second minimum
                elif dist1[v] < arrival_time < dist2[v]:
                    dist2[v] = arrival_time
                    q.append((v, arrival_time))
                    
        return dist2[n]

• Mistake: Pushing to the queue every time you visit a node, regardless of distance improvement.
• Concept: You should only push to the queue if the new time improves dist1 or dist2. Without this check, the queue grows exponentially due to cycles.
• Consequence: The algorithm spins in cycles until the time limit is reached.