Disaster Relief Route Tracker

Published at05 Jan 2026

Array Array Manipulation Medium 4 views

Like17

This problem feels like a little puzzle you can solve one step at a time. In Disaster Relief Route Tracker, you are trying to work toward the right number by following one clear idea.

Here, you are mostly deciding whether a rule stays true while you look through the input. Sometimes that means checking if things are connected, balanced, or allowed. Sometimes it means noticing the first place where the rule breaks. The answer depends on being careful from beginning to end.

For example, if the input is n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[1,5]], start = 1, blocked_shelters = [4], the answer is 5. The convoy reaches shelters 1, 0, 2, 3, and 5 while skipping the blocked shelter 4. Another example is n = 4, roads = [], start = 2, blocked_shelters = [], which gives 1. With no roads, only the staging shelter receives supplies.

This problem needs a little more patience than a very easy one. The key is noticing the exact moment when the rule stays true or breaks.

Example Input & Output

Example 1

Input

n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[1,5]], start = 1, blocked_shelters = [4]

Output

Explanation

The convoy reaches shelters 1, 0, 2, 3, and 5 while skipping the blocked shelter 4.

Example 2

Input

n = 4, roads = [], start = 2, blocked_shelters = []

Output

Explanation

With no roads, only the staging shelter receives supplies.

Example 3

Input

n = 5, roads = [[0,1],[1,2],[2,3],[3,4]], start = 0, blocked_shelters = [2]

Output

Explanation

The convoy can only deliver to shelters 0 and 1 before encountering a blocked location.

Algorithm Flow

Recommendation Algorithm Flow for Disaster Relief Route Tracker

Solution Approach

This problem asks us to count how many shelters the convoy can reach while skipping blocked ones. Roads form an undirected graph, and the reachable set is exactly the connected component of the start, excluding any blocked shelters. A breadth-first search is the natural tool.

The key detail is that we must never enter a blocked shelter, and if the start itself is blocked, no supplies are delivered at all. BFS explores outward from the start and simply refuses to visit blocked nodes.

Here is the implementation:

function relief_route_reach(n, roads, start, blocked_shelters) {
    const blocked = new Set(blocked_shelters);
    if (blocked.has(start)) return 0;
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const u = queue.shift();
        for (const v of adj[u]) {
            if (!visited.has(v) && !blocked.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

First we store the blocked shelters in a set for fast lookup and return 0 immediately if the start is blocked. Then we build an undirected adjacency list from the roads, so each road [u, v] links both directions.

We seed BFS with the start and expand through neighbors. The crucial condition is !blocked.has(v) — we only visit a neighbor if it is neither already seen nor blocked. This keeps the convoy from ever entering a closed shelter.

Let us trace n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[1,5]], start = 1, blocked_shelters = [4]. From shelter 1, we reach 0, 2, and 5. From 2 we reach 3. Shelter 4 is blocked and skipped, so the visited set is {1, 0, 2, 5, 3}, giving 5. When there are no roads, only the start is visited, so the answer is 1.

The time complexity is O(n + e) where e is the number of roads, and the space complexity is O(n) for the graph and visited set.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;

class Solution {
    public int relief_route_reach(int n, int[][] roads, int start, int[] blocked_shelters) {
        Set<Integer> blocked = new HashSet<>();
        for (int s : blocked_shelters) blocked.add(s);
        if (blocked.contains(start)) return 0;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] road : roads) {
            adj[road[0]].add(road[1]);
            adj[road[1]].add(road[0]);
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(start);
        queue.add(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj[u]) {
                if (!visited.contains(v) && !blocked.contains(v)) {
                    visited.add(v);
                    queue.add(v);
                }
            }
        }
        return visited.size();
    }
}

javascript

function relief_route_reach(n, roads, start, blocked_shelters) {
    const blocked = new Set(blocked_shelters);
    if (blocked.has(start)) return 0;
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const u = queue.shift();
        for (const v of adj[u]) {
            if (!visited.has(v) && !blocked.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

php

<?php
function relief_route_reach($n, $roads, $start, $blocked_shelters) {
    $blocked = array_flip($blocked_shelters);
    if (isset($blocked[$start])) return 0;
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $u = $road[0];
        $v = $road[1];
        $adj[$u][] = $v;
        $adj[$v][] = $u;
    }
    $visited = [$start => true];
    $queue = [$start];
    while (!empty($queue)) {
        $u = array_shift($queue);
        foreach ($adj[$u] as $v) {
            if (!isset($visited[$v]) && !isset($blocked[$v])) {
                $visited[$v] = true;
                $queue[] = $v;
            }
        }
    }
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def relief_route_reach(n: int, roads: List[List[int]], start: int, blocked_shelters: List[int]) -> int:
    blocked = set(blocked_shelters)
    if start in blocked: return 0
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append(v)
        adj[v].append(u)
    visited = {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in visited and v not in blocked:
                visited.add(v)
                queue.append(v)
    return len(visited)

rust

use std::collections::{HashSet, VecDeque};

pub fn relief_route_reach(n: i32, roads: Vec<Vec<i32>>, start: i32, blocked_shelters: Vec<i32>) -> i32 {
    let blocked: HashSet<i32> = blocked_shelters.into_iter().collect();
    if blocked.contains(&start) { return 0; }
    let mut adj = vec![vec![]; n as usize];
    for road in roads {
        let u = road[0] as usize;
        let v = road[1] as usize;
        adj[u].push(v as i32);
        adj[v].push(u as i32);
    }
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    visited.insert(start);
    queue.push_back(start);
    while let Some(u) = queue.pop_front() {
        for &v in &adj[u as usize] {
            if !visited.contains(&v) && !blocked.contains(&v) {
                visited.insert(v);
                queue.push_back(v);
            }
        }
    }
    visited.len() as i32
}

typescript

function relief_route_reach(n: number, roads: number[][], start: number, blocked_shelters: number[]): number {
    const blocked = new Set(blocked_shelters);
    if (blocked.has(start)) return 0;
    const adj: number[][] = Array.from({length: n}, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set<number>([start]);
    const queue: number[] = [start];
    while (queue.length > 0) {
        const u = queue.shift()!;
        for (const v of adj[u]) {
            if (!visited.has(v) && !blocked.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

Related Array Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Disaster Relief Route Tracker

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Array Challenges

Riverside Power Grid Check

Campus Shuttle Loop Coverage

Harbor Ferry Route Planner

Skyway Signal Cluster

Museum Corridor Sweep

Celestial Skyline Layout

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.