Garden Relay Count

Published atDate not available

Array Easy 0 views

Like0

This problem asks how many garden stations can be reached by a relay signal. You start at one chosen garden, and the signal can move along the given paths, but only for a limited number of steps.

The answer is a count of reachable gardens, and the starting garden counts too. If the start has no useful path, then the answer can still be 1 because the signal begins there. If the step limit is small, the signal may stop early even when the full network is much larger.

For example, if you start at garden 3 and there are no usable links connected to it, only garden 3 gets counted. In another example, starting at garden 2 with a limit of 1 step means you can only reach the gardens that are exactly one hop away, plus the starting point itself.

The key is counting only the places that can be reached before the step limit runs out. You are not counting the whole connected group, only the part that the relay can reach in time.

Example Input & Output

Example 1

Input

n = 4, paths = [[0,1],[2,2]], start = 3, max_steps = 3

Output

Explanation

Garden 3 has no usable link, so only the starting location hears the relay.

Example 2

Input

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

Output

Explanation

Starting at garden 2 lets the caretakers reach gardens 1 and 3 within one hop.

Example 3

Input

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

Output

Explanation

The relay covers gardens 0, 1, and 2 before the hop limit stops the signal.

Algorithm Flow

Recommendation Algorithm Flow for Garden Relay Count

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 garden_relay_count(int n, int[][] paths, int start, int max_steps) {
        if (n <= 0) return 0;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] p : paths) {
            if (p.length < 2) continue;
            int u = p[0], v = p[1];
            if (u < n && v < n) {
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }
        boolean[] visited = new boolean[n];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start, 0});
        visited[start] = true;
        int count = 1;
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0], d = curr[1];
            if (d < max_steps) {
                for (int v : adj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.add(new int[]{v, d + 1});
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

javascript

function garden_relay_count(n, paths, start, max_steps) {
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of paths) {
        if (u < n && v < n) {
            graph[u].push(v);
            graph[v].push(u);
        }
    }
    const visited = new Set([start]);
    const queue = [[start, 0]];
    let head = 0;
    while (head < queue.length) {
        const [u, d] = queue[head++];
        if (d < max_steps) {
            for (const v of graph[u]) {
                if (!visited.has(v)) {
                    visited.add(v);
                    queue.push([v, d + 1]);
                }
            }
        }
    }
    return visited.size;
}

php

<?php
function garden_relay_count($n, $paths, $start, $max_steps) {
    $graph = array_fill(0, $n, []);
    foreach ($paths as $path) {
        if ($path[0] < $n && $path[1] < $n) {
            $graph[$path[0]][] = $path[1];
            $graph[$path[1]][] = $path[0];
        }
    }
    $visited = [$start => true];
    $queue = [[$start, 0]];
    $head = 0;
    while ($head < count($queue)) {
        list($u, $d) = $queue[$head++];
        if ($d < $max_steps) {
            foreach ($graph[$u] as $v) {
                if (!isset($visited[$v])) {
                    $visited[$v] = true;
                    $queue[] = [$v, $d + 1];
                }
            }
        }
    }
    return count($visited);
}

python

from collections import deque
from typing import List

def garden_relay_count(n: int, paths: List[List[int]], start: int, max_steps: int) -> int:
    graph = [[] for _ in range(n)]
    for u, v in paths:
        if u < n and v < n:
            graph[u].append(v)
            graph[v].append(u)
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        u, d = queue.popleft()
        if d < max_steps:
            for v in graph[u]:
                if v not in visited:
                    visited.add(v)
                    queue.append((v, d + 1))
    return len(visited)

rust


pub fn garden_relay_count(n: i32, paths: Vec<Vec<i32>>, start: i32, max_steps: i32) -> i32 {
    let n = n as usize;
    let mut graph = vec![vec![]; n];
    for path in paths {
        let u = path[0] as usize;
        let v = path[1] as usize;
        if u < n && v < n {
            graph[u].push(v);
            graph[v].push(u);
        }
    }
    let mut visited = vec![false; n];
    let start = start as usize;
    visited[start] = true;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((start, 0));
    let mut count = 1;
    while let Some((u, d)) = queue.pop_front() {
        if d < max_steps {
            for &v in &graph[u] {
                if !visited[v] {
                    visited[v] = true;
                    queue.push_back((v, d + 1));
                    count += 1;
                }
            }
        }
    }
    count
}

typescript

function garden_relay_count(n: number, paths: number[][], start: number, max_steps: number): number {
    const graph: number[][] = [];
    for (let i = 0; i < n; i++) graph[i] = [];
    for (let i = 0; i < paths.length; i++) {
        const [u, v] = paths[i];
        if (u < n && v < n) {
            graph[u].push(v);
            graph[v].push(u);
        }
    }
    const visited: { [key: number]: boolean } = {};
    const queue: [number, number][] = [[start, 0]];
    visited[start] = true;
    let head = 0;
    let count = 1;
    while (head < queue.length) {
        const [u, d] = queue[head++];
        if (d < max_steps) {
            const neighbors = graph[u];
            for (let i = 0; i < neighbors.length; i++) {
                const v = neighbors[i];
                if (!visited[v]) {
                    visited[v] = true;
                    queue.push([v, d + 1]);
                    count++;
                }
            }
        }
    }
    return count;
}

Related Array Challenges

Comments (0)

Join the Discussion

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

Garden Relay Count

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

Lantern Stall Picks

Festival Stall Order

Studio Lighting Slots

Seaport Ferry Gate Control

Railway Network Delay Optimizer

Harbor Signal Expansion Test

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.