LeetCode 3112: Minimum Time to Visit Disappearing Nodes Solution

Master LeetCode problem 3112 (Minimum Time to Visit Disappearing Nodes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3112. Minimum Time to Visit Disappearing Nodes

Medium

Array Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation:

To solve this problem, we can use Dijkstra's algorithm to find the shortest path from the source node 0 to all other nodes before they disappear. We will keep track of the time taken to reach each node and update it whenever we find a shorter path. If a node disappears before we reach it, we will mark it as unreachable.

Initialize a priority queue (min heap) to store nodes based on their tentative distances.
Initialize a distance array to store the minimum time to reach each node from node 0.
Initialize a set to keep track of disappeared nodes.
Initialize the distance array with infinity except for node 0 (distance 0).
Push the starting node 0 to the priority queue.
While the priority queue is not empty, pop a node and update the distances of its neighbors if the new time is less than the current time.
If a node disappears, mark it as unreachable in the distance array.
Return the distance array at the end.

Time Complexity: O(E + V*log(V)), where E is the number of edges and V is the number of nodes. Space Complexity: O(V) for the distance array and priority queue.

Solution Code

import java.util.*;

class Solution {
    public int[] shortestPath(int n, int[][] edges, int[] disappear) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new int[]{edge[0], edge[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;
        pq.offer(new int[]{0, 0});

        Set<Integer> disappeared = new HashSet<>();
        for (int i = 0; i < n; i++) {
            while (!pq.isEmpty() && disappeared.contains(pq.peek()[0])) {
                pq.poll();
            }
            if (pq.isEmpty()) break;
            int[] curr = pq.poll();
            int node = curr[0];
            int dist = curr[1];
            disappeared.add(node);

            for (int[] neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                int nextNode = neighbor[0];
                int nextDist = neighbor[1] + dist;
                if (nextDist < distance[nextNode]) {
                    distance[nextNode] = nextDist;
                    pq.offer(new int[]{nextNode, nextDist});
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (!disappeared.contains(i) && distance[i] == Integer.MAX_VALUE) {
                distance[i] = -1;
            }
        }

        return distance;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3112 (Minimum Time to Visit Disappearing Nodes)?

This page provides optimized solutions for LeetCode problem 3112 (Minimum Time to Visit Disappearing Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3112 (Minimum Time to Visit Disappearing Nodes)?

The time complexity for LeetCode 3112 (Minimum Time to Visit Disappearing Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3112 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3112 in Java, C++, or Python.

Back to LeetCode Solutions