Interstate Rescue Network Audit

Published atDate not available

Array Medium 0 views

Like0

This challenge becomes much easier once you know exactly what to keep, change, or count. In Interstate Rescue Network Audit, 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],[4,5]], start = 0, closed_highways = [[2,3]], the answer is 3. Depots 0, 1, and 2 receive the alert; the closure prevents reaching the rest. Another example is n = 5, roads = [[0,1],[1,2],[2,3],[3,4]], start = 4, closed_highways = [], which gives 5. With no closures, the activation spreads to all depots.

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],[4,5]], start = 0, closed_highways = [[2,3]]

Output

Explanation

Depots 0, 1, and 2 receive the alert; the closure prevents reaching the rest.

Example 2

Input

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

Output

Explanation

With no closures, the activation spreads to all depots.

Example 3

Input

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

Output

Explanation

The origin depot is surrounded by closed highways, so only itself is active.

Algorithm Flow

Recommendation Algorithm Flow for Interstate Rescue Network Audit

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 rescue_network_reach(int n, int[][] roads, int start, int[][] closed_highways) {
        Set<String> closed = new HashSet<>();
        for (int[] r : closed_highways) {
            int u = Math.min(r[0], r[1]);
            int v = Math.max(r[0], r[1]);
            closed.add(u + "-" + v);
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] r : roads) {
            int u = Math.min(r[0], r[1]);
            int v = Math.max(r[0], r[1]);
            if (!closed.contains(u + "-" + v)) {
                adj.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
                adj.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
            }
        }

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(start);
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            if(adj.containsKey(u)) {
                for (int v : adj.get(u)) {
                    if (visited.add(v)) {
                        queue.offer(v);
                    }
                }
            }
        }
        
        return visited.size();
    }
}

javascript

function rescue_network_reach(n, roads, start, closed_highways) {
    const closed = new Set();
    for (const [u, v] of closed_highways) {
        closed.add(u < v ? `${u}-${v}` : `${v}-${u}`);
    }

    const adj = new Map();
    for (const [u, v] of roads) {
        const key = u < v ? `${u}-${v}` : `${v}-${u}`;
        if (!closed.has(key)) {
            if (!adj.has(u)) adj.set(u, []);
            adj.get(u).push(v);
            if (!adj.has(v)) adj.set(v, []);
            adj.get(v).push(u);
        }
    }

    const visited = new Set();
    visited.add(start);
    const queue = [start];

    while (queue.length > 0) {
        const u = queue.shift();
        const neighbors = adj.get(u);
        if (neighbors) {
            for (const v of neighbors) {
                if (!visited.has(v)) {
                    visited.add(v);
                    queue.push(v);
                }
            }
        }
    }
    return visited.size;
}

php

<?php
function rescue_network_reach($n, $roads, $start, $closed_highways) {
    $closed = [];
    foreach ($closed_highways as $h) {
        $key = ($h[0] < $h[1]) ? "$h[0]-$h[1]" : "$h[1]-$h[0]";
        $closed[$key] = true;
    }

    $adj = [];
    foreach ($roads as $r) {
        $key = ($r[0] < $r[1]) ? "$r[0]-$r[1]" : "$r[1]-$r[0]";
        if (!isset($closed[$key])) {
            $adj[$r[0]][] = $r[1];
            $adj[$r[1]][] = $r[0];
        }
    }

    $visited = [$start => true];
    $queue = [$start];
    $head = 0;

    while ($head < count($queue)) {
        $u = $queue[$head++];
        if (isset($adj[$u])) {
            foreach ($adj[$u] as $v) {
                if (!isset($visited[$v])) {
                    $visited[$v] = true;
                    $queue[] = $v;
                }
            }
        }
    }
    return count($visited);
}
?>

python

import collections
from typing import List

def rescue_network_reach(n: int, roads: List[List[int]], start: int, closed_highways: List[List[int]]) -> int:
    closed = set()
    for u, v in closed_highways:
        closed.add(tuple(sorted((u, v))))
        
    adj = collections.defaultdict(list)
    for u, v in roads:
        if tuple(sorted((u, v))) not in closed:
            adj[u].append(v)
            adj[v].append(u)
            
    visited = {start}
    queue = collections.deque([start])
    
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                
    return len(visited)

rust

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

pub fn rescue_network_reach(_n: i32, roads: Vec<Vec<i32>>, start: i32, closed_highways: Vec<Vec<i32>>) -> i32 {
    let mut closed: HashSet<(i32, i32)> = HashSet::new();
    for c in closed_highways {
        let (u, v) = if c[0] < c[1] { (c[0], c[1]) } else { (c[1], c[0]) };
        closed.insert((u, v));
    }

    let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
    for r in roads {
        let (u, v) = (r[0], r[1]);
        let key = if u < v { (u, v) } else { (v, u) };
        if !closed.contains(&key) {
            adj.entry(u).or_default().push(v);
            adj.entry(v).or_default().push(u);
        }
    }

    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    visited.insert(start);
    queue.push_back(start);
    
    while let Some(u) = queue.pop_front() {
        if let Some(neighbors) = adj.get(&u) {
            for &v in neighbors {
                if visited.insert(v) {
                    queue.push_back(v);
                }
            }
        }
    }

    visited.len() as i32
}

typescript

function rescue_network_reach(n: number, roads: number[][], start: number, closed_highways: number[][]): number {
    const closed: { [key: string]: boolean } = {};
    for (let i = 0; i < closed_highways.length; i++) {
        const u = closed_highways[i][0];
        const v = closed_highways[i][1];
        const key = u < v ? u + "-" + v : v + "-" + u;
        closed[key] = true;
    }

    const adj: { [key: number]: number[] } = {};
    for (let i = 0; i < roads.length; i++) {
        const u = roads[i][0];
        const v = roads[i][1];
        const key = u < v ? u + "-" + v : v + "-" + u;
        if (!closed[key]) {
            if (!adj[u]) adj[u] = [];
            adj[u].push(v);
            if (!adj[v]) adj[v] = [];
            adj[v].push(u);
        }
    }

    const visited: { [key: number]: boolean } = {};
    visited[start] = true;
    const queue: number[] = [start];

    let head = 0;
    while (head < queue.length) {
        const u = queue[head];
        head++;
        const neighbors = adj[u];
        if (neighbors) {
            for (let i = 0; i < neighbors.length; i++) {
                const v = neighbors[i];
                if (!visited[v]) {
                    visited[v] = true;
                    queue.push(v);
                }
            }
        }
    }
    
    let count = 0;
    for (const k in visited) count++;
    return count;
}

Related Array Challenges

Comments (0)

Join the Discussion

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

Interstate Rescue Network Audit

Example Input & Output

Algorithm Flow

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

Disaster Relief Route Tracker

Metro Transfer Capacity Map

Riverside Power Grid Check

Campus Shuttle Loop Coverage

Harbor Ferry Route Planner

Skyway Signal Cluster

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.