Minimum Time to Visit Disappearing Nodes - Practice Coding Problems

Minimum Time to Visit Disappearing Nodes - Problem

There is an undirected graph of n nodes. You are given a 2D array edges, where edges[i] = [u_i, v_i, length_i] describes an edge between node u_i and node v_i with a traversal time of length_i units.

Additionally, you are given an array disappear, where disappear[i] denotes the time when the node i disappears from the graph and you won't be able to visit it.

Note: The graph might be disconnected and might contain multiple edges. Return the array answer, with answer[i] denoting the minimum units of time required to reach node i from node 0. If node i is unreachable from node 0 then answer[i] is -1.

Input & Output

Example 1 — Basic Graph with Disappearing Nodes

$ Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

› Output: [0,2,3]

💡 Note: Start at node 0 (time 0). Path 0→1 takes 2 time units, but node 1 disappears at time 1, so it's unreachable directly. However, path 0→1→2 takes 2+1=3 time units, arriving at node 2 before it disappears at time 5. Direct path 0→2 takes 4 time units, but 0→1→2 is faster at 3 units.

Example 2 — Early Disappearing Node

$ Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

› Output: [0,2,3]

💡 Note: Node 0 disappears at time 1, but we start there at time 0 so it's reachable. Node 1 can be reached via 0→1 in 2 time units (before time 3). Node 2 is reachable via 0→1→2 in 3 time units (before time 5).

Example 3 — Unreachable Node

$ Input: n = 2, edges = [[0,1,10]], disappear = [1,1]

› Output: [0,-1]

💡 Note: Node 1 disappears at time 1, but it takes 10 time units to reach it from node 0. Since 10 > 1, node 1 is unreachable, so return -1.

Constraints

1 ≤ n ≤ 5 × 10⁴
0 ≤ edges.length ≤ 10⁵
edges[i] = [u_i, v_i, length_i]
0 ≤ u_i, v_i ≤ n - 1
1 ≤ length_i ≤ 10⁴
1 ≤ disappear[i] ≤ 10⁵

Visualization

Tap to expand

Key Insight: Modified Dijkstra with time-based node availability

Understanding the Visualization

Input Graph

Graph with weighted edges and disappear times for each node

Path Finding

Use modified Dijkstra to find shortest paths respecting time constraints

Result

Minimum time to reach each node, or -1 if unreachable

Key Takeaway

🎯 Key Insight: This is a shortest path problem with time constraints - use Dijkstra's algorithm but only visit nodes before they disappear

Asked in

G Google 25 a Amazon 20 f Meta 15 ⊞ Microsoft 12

The key insight is to use Dijkstra's shortest path algorithm with an additional time constraint: only visit nodes if we can reach them before their disappear time. The optimal approach uses a priority queue to explore paths in order of increasing distance, ensuring we find the shortest valid path to each reachable node. Time: O((V + E) log V), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ DFS All Paths	O(2^n)	O(n)	Try every possible path using DFS and track minimum time to each node
Dijkstra with Time Constraints	O((V + E) log V)	O(V + E)	Modified Dijkstra's algorithm that only processes nodes before they disappear

DFS All Paths — Algorithm Steps

Build adjacency list from edges
For each node, run DFS from node 0
Track minimum time while ensuring arrival before disappear time

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from node 0 with time 0

Explore Paths

Try all neighbors, backtrack when necessary

Check Constraints

Only visit nodes before they disappear

Code -

solution.c — C

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

#define MAX_NODES 1000
#define MAX_EDGES 2000

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

struct Edge* graph[MAX_NODES];
int result[MAX_NODES];
int disappear[MAX_NODES];
int visited[MAX_NODES];

void dfs(int node, int time, int n) {
    if (time >= disappear[node]) return;
    
    if (result[node] == -1 || time < result[node]) {
        result[node] = time;
    } else {
        return;
    }
    
    struct Edge* edge = graph[node];
    while (edge) {
        if (!visited[edge->to]) {
            visited[edge->to] = 1;
            dfs(edge->to, time + edge->weight, n);
            visited[edge->to] = 0;
        }
        edge = edge->next;
    }
}

void solution(int n, int edges[][3], int edge_count, int disappear_arr[]) {
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
        result[i] = -1;
        visited[i] = 0;
        disappear[i] = disappear_arr[i];
    }
    
    // Build adjacency list
    for (int i = 0; i < edge_count; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int w = edges[i][2];
        
        struct Edge* edge1 = malloc(sizeof(struct Edge));
        edge1->to = v;
        edge1->weight = w;
        edge1->next = graph[u];
        graph[u] = edge1;
        
        struct Edge* edge2 = malloc(sizeof(struct Edge));
        edge2->to = u;
        edge2->weight = w;
        edge2->next = graph[v];
        graph[v] = edge2;
    }
    
    result[0] = 0;
    visited[0] = 1;
    dfs(0, 0, n);
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Read edges and disappear arrays (simplified parsing)
    int edge_count = 0;
    int edges[MAX_EDGES][3];
    int disappear_arr[MAX_NODES];
    
    // Parse input arrays (simplified)
    
    solution(n, edges, edge_count, disappear_arr);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, explores all possible paths which can be exponential

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and adjacency list storage

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 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

DFS All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler