Garden Relay Count

Published at05 Jan 2026

Graph BFS Easy 16 views

Like7

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

Solution Approach

This problem asks us to count the gardens reachable from a start, but only within a limited number of steps. Unlike a plain reachability check, we must stop exploring once the step budget is used up, so we track the distance of each node during the search.

A breadth-first search is ideal here because it visits nodes in order of increasing distance. We store each node together with its distance from the start, and only expand a node further if we still have steps to spare.

Here is the implementation:

function count_relay_reach(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;
}

We build an undirected graph, skipping any path that references a non-existent node. We seed the queue with the start at distance 0. In the loop, we only expand a node when its current distance d is less than max_steps, pushing unvisited neighbors with distance d + 1.

Because BFS explores level by level, every node is first discovered at its shortest distance from the start. The condition d < max_steps guarantees we never travel more than the allowed number of hops, and the start itself is always counted.

The time complexity is O(n + e) and the space complexity is O(n).

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 count_relay_reach(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 count_relay_reach(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 count_relay_reach($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 count_relay_reach(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 count_relay_reach(n: i32, paths: Vec<(i32, i32)>, start: i32, max_steps: i32) -> i32 {
    let n = n as usize;
    let mut graph = vec![vec![]; n];
    for (u, v) in paths {
        let u = u as usize;
        let v = v 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 countRelayReach(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 Graph 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

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 Graph Challenges

Catalog Shelf Lineup

Ascending Manifest

Mountain Cabin Signal Range

Seaport Ferry Gate Control

City Bus Loop Access

Railway Network Delay Optimizer

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.