Second Minimum Time to Reach Destination - Practice Coding Problems

Second Minimum Time to Reach Destination - 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] = [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.

Note: 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.

Input & Output

Example 1 — Basic Graph

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

› Output: 13

💡 Note: First minimum path: 1→4→5 takes 6 time units. Second minimum: 1→3→4→5 or 1→2→1→4→5 takes 13 time units considering traffic light delays.

Example 2 — Simple Path

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

› Output: 11

💡 Note: Only one direct path 1→2. First minimum is 3. To get second minimum, go 1→2→1→2, which takes 11 time units with traffic delays.

Example 3 — Multiple Routes

$ Input: n = 4, edges = [[1,2],[1,3],[2,4],[3,4]], time = 2, change = 4

› Output: 6

💡 Note: Two paths: 1→2→4 and 1→3→4. Both take 4 time units (first minimum). Second minimum requires one detour, taking 6 time units.

Constraints

2 ≤ n ≤ 10⁴
n - 1 ≤ edges.length ≤ min(2 × 10⁴, n × (n - 1) / 2)
edges[i].length == 2
1 ≤ u_i, v_i ≤ n
u_i != v_i
There are no duplicate edges
The graph is connected
1 ≤ time, change ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Graph Input

City represented as bidirectional graph with traffic lights

Path Finding

Find shortest and second shortest times considering light delays

Result

Return second minimum time from vertex 1 to vertex n

Key Takeaway

🎯 Key Insight: Use modified BFS to track both shortest and second shortest times while handling traffic light delays

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use a modified BFS/Dijkstra approach that tracks both the shortest and second shortest arrival times at each vertex while considering traffic light delays. The optimal approach uses a priority queue to process vertices by arrival time and maintains two distance values per vertex. Time: O(E log V), Space: O(V).

Common Approaches

Approach	Time	Space	Notes
✓ Modified BFS (Dijkstra-like)	O(E log V)	O(V)	Use BFS to find shortest and second shortest paths simultaneously
DFS with All Paths	O(n!)	O(n)	Explore all possible paths from vertex 1 to vertex n using depth-first search

Modified BFS (Dijkstra-like) — Algorithm Steps

Initialize priority queue with source vertex at time 0
For each vertex, track best and second-best arrival times
Process neighbors, calculating arrival time with traffic delays
Stop when we find second minimum time to destination

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start from vertex 1 with time 0, track best/second-best times

Process Vertices

Use priority queue to process vertices by arrival time

Update Times

For each neighbor, calculate new arrival time and update if better

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 105
#define MAX_HEAP 10000

struct Edge {
    int to;
    struct Edge* next;
};

struct HeapNode {
    int time;
    int node;
};

struct Edge* graph[MAX_N];
int dist[MAX_N][2];
struct HeapNode heap[MAX_HEAP];
int heap_size = 0;

void swap_heap(int i, int j) {
    struct HeapNode temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

void push_heap(int time, int node) {
    heap[heap_size].time = time;
    heap[heap_size].node = node;
    
    int pos = heap_size++;
    while (pos > 0) {
        int parent = (pos - 1) / 2;
        if (heap[parent].time <= heap[pos].time) break;
        swap_heap(parent, pos);
        pos = parent;
    }
}

struct HeapNode pop_heap() {
    struct HeapNode result = heap[0];
    heap[0] = heap[--heap_size];
    
    int pos = 0;
    while (2 * pos + 1 < heap_size) {
        int child = 2 * pos + 1;
        if (child + 1 < heap_size && heap[child + 1].time < heap[child].time) {
            child++;
        }
        if (heap[pos].time <= heap[child].time) break;
        swap_heap(pos, child);
        pos = child;
    }
    
    return result;
}

void add_edge(int from, int to) {
    struct Edge* edge = malloc(sizeof(struct Edge));
    edge->to = to;
    edge->next = graph[from];
    graph[from] = edge;
}

int solution(int n, int edges[][2], int edge_count, int time, int change) {
    // Initialize
    for (int i = 0; i <= n; i++) {
        graph[i] = NULL;
        dist[i][0] = INT_MAX;
        dist[i][1] = INT_MAX;
    }
    dist[1][0] = 0;
    heap_size = 0;
    
    // Build graph
    for (int i = 0; i < edge_count; i++) {
        add_edge(edges[i][0], edges[i][1]);
        add_edge(edges[i][1], edges[i][0]);
    }
    
    push_heap(0, 1);
    
    while (heap_size > 0) {
        struct HeapNode curr = pop_heap();
        int curr_time = curr.time;
        int node = curr.node;
        
        if (node == n && dist[n][1] != INT_MAX) {
            return dist[n][1];
        }
        
        if (curr_time > dist[node][1]) {
            continue;
        }
        
        for (struct Edge* edge = graph[node]; edge; edge = edge->next) {
            int neighbor = edge->to;
            int cycle = curr_time / change;
            int next_time;
            if (cycle % 2 == 1) {
                int wait_time = (cycle + 1) * change - curr_time;
                next_time = curr_time + wait_time + time;
            } else {
                next_time = curr_time + time;
            }
            
            if (next_time < dist[neighbor][0]) {
                dist[neighbor][1] = dist[neighbor][0];
                dist[neighbor][0] = next_time;
                push_heap(next_time, neighbor);
            } else if (next_time < dist[neighbor][1] && next_time != dist[neighbor][0]) {
                dist[neighbor][1] = next_time;
                push_heap(next_time, neighbor);
            }
        }
    }
    
    return dist[n][1];
}

int main() {
    int n = 4;
    int edges[][2] = {{1,2}, {1,3}, {3,4}};
    int time = 3, change = 5;
    
    int result = solution(n, edges, 3, time, change);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(E log V)

Priority queue operations for each edge, similar to Dijkstra's algorithm

⚡ Linearithmic

Space Complexity

O(V)

Priority queue and distance arrays for tracking best times

✓ Linear Space

23.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Modified BFS (Dijkstra-like) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler