City Signal Span

Published atDate not available

Array Easy 0 views

Like0

Imagine looking after a city full of routes, signals, or stops. In City Signal Span, you are trying to work toward the right number by following one clear idea.

Calculate emergency broadcast signal span A good way to think about it is to first understand what goes in, then what rule you must follow, and finally what shape the answer should have.

For example, if the input is n = 4, roads = [[0,1],[1,2],[2,3]], start = 0, the answer is 4. The signal travels along every road and covers all four intersections. Another example is n = 6, roads = [[0,1],[1,2],[2,0],[3,4]], start = 5, which gives 1. Intersection 5 is isolated, so only the starting point receives the broadcast.

This is a friendly practice problem, but it still rewards careful reading. The key is understanding the rule clearly and then applying it carefully.

One helpful habit is to say the rule out loud in your own words before you start solving. If you can explain what counts, what changes, and what the final answer should look like, you are already much closer to the right solution.

Example Input & Output

Example 1

Input

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

Output

Explanation

The signal travels along every road and covers all four intersections.

Example 2

Input

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

Output

Explanation

Intersection 5 is isolated, so only the starting point receives the broadcast.

Example 3

Input

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

Output

Explanation

Intersections 0, 1, and 2 share a chain of roads, while 3 and 4 are separate.

Algorithm Flow

Recommendation Algorithm Flow for City Signal Span

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 city_signal_span(int n, int[][] roads, int start) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] road : roads) {
            adj.get(road[0]).add(road[1]);
            adj.get(road[1]).add(road[0]);
        }
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int neighbor : adj.get(curr)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return visited.size();
    }
}

javascript

function city_signal_span(n, roads, start) {
    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 curr = queue.shift();
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

php

<?php
function city_signal_span($n, $roads, $start) {
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $adj[$road[0]][] = $road[1];
        $adj[$road[1]][] = $road[0];
    }
    $visited = [$start => true];
    $queue = [$start];
    while (!empty($queue)) {
        $curr = array_shift($queue);
        foreach ($adj[$curr] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor;
            }
        }
    }
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def city_signal_span(n: int, roads: List[List[int]], start: int) -> int:
    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:
        curr = queue.popleft()
        for neighbor in adj[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return len(visited)

rust

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

pub fn city_signal_span(n: i32, roads: Vec<Vec<i32>>, start: i32) -> i32 {
    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);
        adj[v].push(u);
    }
    let mut visited = HashSet::new();
    visited.insert(start as usize);
    let mut queue = VecDeque::new();
    queue.push_back(start as usize);
    while let Some(curr) = queue.pop_front() {
        for &neighbor in &adj[curr] {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back(neighbor);
            }
        }
    }
    visited.len() as i32
}

typescript

function city_signal_span(n: number, roads: number[][], start: number): number {
    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([start]);
    const queue = [start];
    while (queue.length > 0) {
        const curr = queue.shift()!;
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

Related Array Challenges

Comments (0)

Join the Discussion

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

City Signal Span

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

Celestial Skyline Layout

Aurora Diary Synthesis

Ember Glyph Mosaic

Tidal Melody Chorus

Lantern Pattern Paths

Echoing Story Weaver

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.