Riverside Power Grid Check

Published atDate not available

Array Easy 0 views

Like0

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

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

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

City Signal Span

Celestial Skyline Layout

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.