Coding

Reachable Nodes Before Destruction

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a network of n nodes, represented by an undirected graph, where each node is connected to other nodes by edges. Each edge has a specific travel time associated with it. Additionally, you are given an array destroy_time where destroy_time[i] denotes the time at which node i will be destroyed. Once a node is destroyed, it becomes inaccessible.Starting from node 0, your task is to determine which nodes can be reached and saved before they are destroyed. A node is considered "saved" if you can reach it from node 0 before the time mentioned in destroy_time. Return an array where answer[i] is 1 if node i can be saved (i.e., you can reach it before it is destroyed) and 0 if it cannot be saved.

Input: n = 4, edges = [[0,1,3],[1,2,2],[0,2,5],[2,3,4]], destroy_time = [6,4,7,5] Output: [1, 1, 1, 0] Explanation: Node 0: This is the starting point, and it is already saved, so the answer is 1. Node 1: It takes 3 units of time to reach via the edge [0,1], and it is destroyed at time 4, so it be saved. Node 2: It takes 5 units of time to reach via the edge [0,2], and it is destroyed at time 7, so it can be saved. Node 3: It takes 9 units of time to reach via the edges [0,2] → [2,3], but it is destroyed at time 5, so it cannot be saved.

Input: n = 5, edges = [[0,1,2],[0,2,3],[1,3,4],[2,4,1]], destroy_time = [5,6,8,7,9] Output: [1, 1, 1, 1, 1] Explanation: Node 0: This is the starting point, and it is already saved, so the answer is 1. Node 1: It takes 2 units of time to reach via the edge [0,1], and it is destroyed at time 6, so it can be saved. Node 2: It takes 3 units of time to reach via the edge [0,2], and it is destroyed at time 8, so it can be saved. Node 3: It takes 6 units of time to reach via the edges [0,1] → [1,3], and it is destroyed at time 7, so it can be saved. Node 4: It takes 4 units of time to reach via the edges [0,2] → [2,4], and it is destroyed at time 9, so it can be saved.

1 <= n <= 5 * 104
0 <= edges.length <= 105
edges[i] == [ui, vi, lengthi]
0 <= ui, vi <= n - 1
1 <= lengthi <= 105
destroy_time.length == n
1 <= destroy_time[i] <= 105

cpp

class Solution {
public:
    vector<int> reachableNodes(int n, vector<vector<int>>& v, vector<int>& d) {
  
    }
};

java

class Solution {
    public List<Integer> reachableNodes(int n, int[][] edges, int[] distLimit) {
     
    }
}

python

class Solution:
    def reachableNodes(self, n, edges, distLimit):

javascript

class Solution {
    reachableNodes(n, edges, distLimit) {
 
    }
}

csharp

public class Solution {
    public List<int> ReachableNodes(int n, List<List<int>> v, List<int> d) {

    }
}

func reachableNodes(n int, edges [][]int, distLimit []int) []int {
	
}

Stuck? Show a way to structure it+

01Build an undirected weighted adjacency list.
02Run Dijkstra from node zero.
03Relax only when candidate arrival is before destruction time.
04Ignore stale priority-queue entries.
05Mark every finite valid distance as saved.

Reference answer

This is Dijkstra with an arrival-time constraint, since all edge travel times are positive. Initialize dist[0] to zero, push it into a min-priority queue, and skip stale extracted entries. For every edge to v with weight w, compute next = time plus w; relax only when next is strictly less than destroyTime[v] and less than dist[v]. The strict comparison matters: arriving at the destruction time is not before destruction. Nodes reached through a destroyed intermediate are automatically excluded because an invalid arrival is never enqueued. At the end, output 1 for finite distances and 0 otherwise. Clarify the problem convention for node zero: mark it immediately saved if the start is safe by definition, or require zero to be before its destruction time. Runtime is O((V plus E) log V) with a binary heap and O(V plus E) space.

Then expect these follow-ups

What changes if an edge can be destroyed mid-traversal?
Tests: constraint adaptation
How would you recover an actual saved path for each node?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question