We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Second Minimum Time to Reach Destination

Number: 2171

Difficulty: Hard

Paid? No

Companies: Google, Microsoft

Problem Description

Given an undirected connected graph with n vertices (labeled 1 through n) and a list of edges, every edge taking a constant time to traverse, determine the second minimum time required to travel from vertex 1 to vertex n. Each vertex contains a traffic signal that alternates between green and red every "change" minutes (all vertices change simultaneously). You can arrive at any time, but you can only leave a vertex when its signal is green, meaning you may have to wait if the signal shows red. The second minimum time is the smallest arrival time that is strictly larger than the minimum.

Key Insights

  • We can model the problem as a “shortest path” variant in which we need to track two distinct arrival times at each vertex: the minimum and the second minimum.
  • A modified BFS or Dijkstra's algorithm with extra state is used, where for every vertex we store up to two best arrival times.
  • When moving from one vertex to another, consider potential waiting time due to the traffic signal cycle. If the current time falls in a red phase (i.e. an odd cycle), compute the waiting time until the next green phase.
  • Ensure that if a newly computed time is equal to an already recorded best time for that vertex, then it is skipped because we need strictly larger distinct time values.

Space and Time Complexity

Time Complexity: O(m log n) – Each state (up to 2 per vertex) is pushed/popped from the priority queue, where m is the number of edges. Space Complexity: O(n + m) – For storing the graph and the best arrival times for each vertex.

Solution

We solve the problem using a priority queue (min-heap) augmented BFS/Dijkstra approach. For each vertex, we maintain a list of up to two distinct arrival times. When expanding a state (current time and vertex), we calculate the effective time to leave based on the traffic signal cycle:

  • If the current time modulo (2 * change) falls in a red phase (i.e., an odd phase), compute the additional wait time.
  • Add the traversal time to get the new arrival time at the adjacent vertex. We update the list of arrival times for that vertex only if the new time is not already recorded and if we have less than two times stored or the new time is smaller than the highest currently stored time. The answer is the second distinct arrival time for vertex n.

Code Solutions

import heapq

def secondMinimum(n, edges, time, change):
    # Build graph as adjacency list
    graph = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # best[node] stores up to two distinct arrival times
    best = [[] for _ in range(n + 1)]
    
    # Priority queue: (arrival_time, node)
    # Start at node 1 with time 0
    heap = [(0, 1)]
    best[1].append(0)
    
    while heap:
        curr_time, node = heapq.heappop(heap)
        
        # If we have reached destination and it is the second arrival, return it
        if node == n and len(best[n]) == 2 and curr_time > best[n][0]:
            return curr_time
        
        # Explore neighbors
        for neighbor in graph[node]:
            # Compute wait time at current node if necessary.
            # Determine what phase we are in
            phase = curr_time // change
            wait = 0
            if phase % 2 == 1:  # if red phase, wait until it turns green
                wait = change - (curr_time % change)
            new_time = curr_time + wait + time
            
            # Only update if we haven't already seen this new_time for neighbor.
            if len(best[neighbor]) < 2:
                if new_time in best[neighbor]:
                    continue
                best[neighbor].append(new_time)
                best[neighbor].sort()
                heapq.heappush(heap, (new_time, neighbor))
            elif new_time < best[neighbor][1] and new_time not in best[neighbor]:
                best[neighbor][1] = new_time
                best[neighbor].sort()
                heapq.heappush(heap, (new_time, neighbor))
    return -1  # Should not happen per problem constraints.

# Example usage:
print(secondMinimum(5, [[1,2],[1,3],[1,4],[3,4],[4,5]], 3, 5))  # Expected output: 13
← Back to All Questions