BudiBadu Logo

Garden Relay Count

Array Easy 0 views
Like7

The botanical caretakers have been wiring lanterns between the gardens of a sprawling park to coordinate nightly maintenance runs. Each garden is labelled from 0 to n - 1, and every lantern link ties two gardens together so a message can travel in either direction. When a supervisor standing in one garden relays a message, it spreads along connected links until all reachable gardens receive notice. The task is to count how many gardens hear the message starting from a specified origin.

Consider the park as an undirected graph where gardens are nodes and lantern links are edges. From the origin garden, the message travels along any edge and continues to new gardens until no more connections exist. Isolated gardens that cannot be reached remain silent. Duplicate links in the list simply reinforce an existing connection without adding new paths.

Return the count of distinct gardens that receive the message, including the starting garden itself. If the garden has no outbound links, the count is simply 1.

Example 1:

Input: n = 6, links = [[0,1],[1,2],[2,3],[3,4],[4,5]], start = 0
Output: 6
Explanation: All gardens are connected in a chain, so the message reaches every one.

Example 2:

Input: n = 5, links = [[0,1],[2,3]], start = 0
Output: 2
Explanation: Only gardens 0 and 1 are reachable from the origin.

Example 3:

Input: n = 4, links = [], start = 2
Output: 1
Explanation: No links exist, so only the starting garden counts.

Algorithm Flow

Recommendation Algorithm Flow for Garden Relay Count - Budibadu
Recommendation Algorithm Flow for Garden Relay Count - Budibadu

Best Answers

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;
    }
}