Riverside Power Grid Check

Published at05 Jan 2026

Array 2D Array Easy 17 views

Like14

You can think of this as a small game with a very specific goal. In Riverside Power Grid Check, 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, lines = [[0,1],[1,2],[0,2],[3,4]], origin = 3, the answer is 2. Only substations 3 and 4 are reachable from the origin segment. Another example is n = 4, lines = [], origin = 2, which gives 1. With no power lines connected, only the origin substation is inspected.

This is a friendly practice problem, but it still rewards careful reading. The key is noticing the exact moment when the rule stays true or breaks.

Example Input & Output

Example 1

Input

n = 6, lines = [[0,1],[1,2],[0,2],[3,4]], origin = 3

Output

Explanation

Only substations 3 and 4 are reachable from the origin segment.

Example 2

Input

n = 5, lines = [[0,1],[1,2],[2,3],[3,4]], origin = 0

Output

Explanation

The crew moves sequentially across each line and inspects every substation.

Example 3

Input

n = 4, lines = [], origin = 2

Output

Explanation

With no power lines connected, only the origin substation is inspected.

Algorithm Flow

Recommendation Algorithm Flow for Riverside Power Grid Check

Solution Approach

This problem asks us to count how many power stations are reachable from a starting station through the connection links. The links form an undirected graph, so the answer is the size of the connected component containing the start.

A breadth-first search is the natural choice. We explore outward from the start along every link, marking each station we reach, and then return how many stations were visited.

Here is the implementation:

function power_grid_coverage(n, links, start) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of links) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const u = queue.shift();
        for (const v of adj[u]) {
            if (!visited.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

We build an undirected adjacency list so each link connects both directions. Then we seed BFS with the start and explore all reachable neighbors, marking each as visited. When the queue empties, the visited set contains exactly the component of the start, so its size is the answer.

Let us trace n = 6, links = [[0,1],[1,2],[0,2],[3,4]], start = 3. From station 3, we can reach 4, but the component {0,1,2} is disconnected. The visited set is {3, 4}, giving 2. For a path where everything connects, all stations are reached, giving the full count.

When there are no links, only the start is reachable, so the answer is 1.

The time complexity is O(n + e) where e is the number of links, 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 power_grid_coverage(int n, int[][] lines, int origin) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] line : lines) {
            adj.computeIfAbsent(line[0], k -> new ArrayList<>()).add(line[1]);
            adj.computeIfAbsent(line[1], k -> new ArrayList<>()).add(line[0]);
        }

        if (!adj.containsKey(origin)) return 1;

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(origin);
        queue.offer(origin);
        
        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 power_grid_coverage(n, lines, origin) {
    const adj = new Map();
    for (const [u, v] of lines) {
        if (!adj.has(u)) adj.set(u, []);
        adj.get(u).push(v);
        if (!adj.has(v)) adj.set(v, []);
        adj.get(v).push(u);
    }

    if (!adj.has(origin)) return 1;

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

    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 power_grid_coverage($n, $lines, $origin) {
    $adj = [];
    foreach ($lines as $line) {
        $adj[$line[0]][] = $line[1];
        $adj[$line[1]][] = $line[0];
    }

    if (!isset($adj[$origin])) {
        return 1;
    }

    $visited = [$origin => true];
    $queue = [$origin];
    $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 power_grid_coverage(n: int, lines: List[List[int]], origin: int) -> int:
    adj = collections.defaultdict(list)
    for u, v in lines:
        adj[u].append(v)
        adj[v].append(u)
        
    if origin not in adj and not lines:
        return 1
    if origin not in adj: return 1

    visited = set([origin])
    queue = collections.deque([origin])
    
    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 power_grid_coverage(_n: i32, lines: Vec<Vec<i32>>, origin: i32) -> i32 {
    let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
    for line in lines {
        adj.entry(line[0]).or_default().push(line[1]);
        adj.entry(line[1]).or_default().push(line[0]);
    }

    if !adj.contains_key(&origin) {
        return 1;
    }

    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    visited.insert(origin);
    queue.push_back(origin);
    
    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 power_grid_coverage(n: number, lines: number[][], origin: number): number {
    const adj = new Map<number, number[]>();
    for (const [u, v] of lines) {
        if (!adj.has(u)) adj.set(u, []);
        adj.get(u)!.push(v);
        if (!adj.has(v)) adj.set(v, []);
        adj.get(v)!.push(u);
    }

    if (!adj.has(origin)) return 1;

    const visited = new Set<number>();
    visited.add(origin);
    const queue = [origin];

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

Related Array Challenges

Comments (0)

Join the Discussion

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

Riverside Power Grid Check

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

Campus Shuttle Loop Coverage

Harbor Ferry Route Planner

Skyway Signal Cluster

Museum Corridor Sweep

Celestial Skyline Layout

Equinox Gate Verdict

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.