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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question