How to Solve Power Grid Maintenance

This problem requires tracking connectivity among multiple power stations under sequential operations. By assigning component IDs via DFS or BFS, each query can efficiently determine whether a station is connected or offline. Using array scanning combined with hash lookups ensures that updates and connectivity checks remain fast even for large networks of stations.

Problem Statement

You are managing a set of c power stations, each uniquely identified from 1 to c. The stations are connected by n bidirectional cables given in a 2D array connections, where connections[i] = [ui, vi] indicates a direct link between station ui and station vi. Initially, all stations are online, and directly or indirectly connected stations form a single or multiple power grids.

You are given a sequence of queries, where each query either simulates a station going offline or asks for the size of the connected component a station currently belongs to. Implement a system that processes these queries efficiently, returning the number of connected stations when asked and -1 if the queried station is offline.

Examples

Example 1

Input: c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]

Output: [3,2,3]

Example 2

Input: c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]

Output: [1,-1]

Constraints

• 1 <= c <= 105
• 0 <= n == connections.length <= min(105, c * (c - 1) / 2)
• connections[i].length == 2
• 1 <= ui, vi <= c
• ui != vi
• 1 <= queries.length <= 2 * 105
• queries[i].length == 2
• queries[i][0] is either 1 or 2.
• 1 <= queries[i][1] <= c

Solution Approach

Assign Component IDs

Use DFS or BFS to traverse all stations, assigning a unique component ID to each connected subgrid. Store component IDs in an array for O(1) lookup when processing queries about station connectivity.

Use Hash Lookup for Offline Tracking

Maintain a hash set of stations currently offline. When a query indicates a station goes offline, remove it from active components and update the hash. Connectivity queries first check this hash to return -1 if the station is offline.

Process Queries Efficiently

Scan the queries array sequentially. For type 1 queries (component size), return the size from a precomputed component-size map unless the station is offline. For type 2 queries (take offline), update the offline hash and decrement connected sizes as needed.

Complexity Analysis

Time complexity depends on the initial component assignment via DFS/BFS, O(c + n), plus O(1) per query using hash lookups. Space complexity includes storing component IDs, offline hash set, and component sizes, O(c + n).

What Interviewers Usually Probe

• Candidate efficiently maps stations to connected components using DFS/BFS.
• Uses a hash set or array for quick online/offline checks.
• Processes queries without recomputing entire connectivity each time.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to check if a station is offline before reporting size.
• Recomputing connectivity naively on each query leading to TLE.
• Incorrectly updating component sizes after a station goes offline.

Follow-up variants

• Queries may include reconnect operations instead of only offline.
• Connections might form multiple disconnected grids initially.
• Use weighted connections or additional station attributes affecting connectivity.

How GhostInterview Helps

• GhostInterview precomputes component IDs to answer queries instantly, avoiding repeated DFS/BFS scans.
• It tracks offline stations automatically using hash lookups tied to the array scanning pattern.
• Provides step-by-step query handling showing component size updates, preventing common TLE mistakes.

Topic Pages

• Array
• Hash Table
• Depth-First Search
• Breadth-First Search
• Union Find
• Graph
• Heap (Priority Queue)
• Ordered Set

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What pattern does Power Grid Maintenance follow?

It uses array scanning plus hash lookup to track connected components and efficiently process online/offline queries.

How do I handle a query for a station that is offline?

Check the offline hash set first; if the station is offline, return -1 immediately.

Can this problem be solved without DFS or BFS?

Direct DFS/BFS assignment is optimal for component IDs, but Union-Find can also be used to maintain connectivity dynamically.

What happens when multiple stations go offline consecutively?

Update the offline hash for each station and adjust component sizes accordingly; connectivity queries then reflect the current state.

How does GhostInterview optimize processing for Power Grid Maintenance?

It precomputes component IDs and uses hash lookups to answer connectivity queries instantly while handling offline updates efficiently.