Watch 10 video solutions for Power Grid Maintenance, a medium level problem involving Array, Hash Table, Depth-First Search. This walkthrough by NeetCodeIO has 6,412 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer c representing c power stations, each with a unique identifier id from 1 to c (1‑based indexing).
These stations are interconnected via n bidirectional cables, represented by a 2D array connections, where each element connections[i] = [ui, vi] indicates a connection between station ui and station vi. Stations that are directly or indirectly connected form a power grid.
Initially, all stations are online (operational).
You are also given a 2D array queries, where each query is one of the following two types:
[1, x]: A maintenance check is requested for station x. If station x is online, it resolves the check by itself. If station x is offline, the check is resolved by the operational station with the smallest id in the same power grid as x. If no operational station exists in that grid, return -1.
[2, x]: Station x goes offline (i.e., it becomes non-operational).
Return an array of integers representing the results of each query of type [1, x] in the order they appear.
Note: The power grid preserves its structure; an offline (non‑operational) node remains part of its grid and taking it offline does not alter connectivity.
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]
Explanation:
{1, 2, 3, 4, 5} are online and form a single power grid.[1,3]: Station 3 is online, so the maintenance check is resolved by station 3.[2,1]: Station 1 goes offline. The remaining online stations are {2, 3, 4, 5}.[1,1]: Station 1 is offline, so the check is resolved by the operational station with the smallest id among {2, 3, 4, 5}, which is station 2.[2,2]: Station 2 goes offline. The remaining online stations are {3, 4, 5}.[1,2]: Station 2 is offline, so the check is resolved by the operational station with the smallest id among {3, 4, 5}, which is station 3.Example 2:
Input: c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]
Output: [1,-1]
Explanation:
[1,1]: Station 1 is online in its isolated grid, so the maintenance check is resolved by station 1.[2,1]: Station 1 goes offline.[1,1]: Station 1 is offline and there are no other stations in its grid, so the result is -1.
Constraints:
1 <= c <= 1050 <= n == connections.length <= min(105, c * (c - 1) / 2)connections[i].length == 21 <= ui, vi <= cui != vi1 <= queries.length <= 2 * 105queries[i].length == 2queries[i][0] is either 1 or 2.1 <= queries[i][1] <= cProblem Overview: You manage a power grid where cities (nodes) are connected by transmission lines (edges). As maintenance operations occur, connections change and queries ask about connectivity or available power sources. The task is to efficiently maintain the grid state and answer these queries without recomputing the entire graph each time.
Approach 1: Rebuild Connectivity with DFS/BFS (O(Q * (N + E)) time, O(N) space)
A straightforward solution treats each query independently. When the grid changes, rebuild the connectivity information by running a traversal such as Depth-First Search or Breadth-First Search. For each query, start from the requested node and explore reachable nodes using an adjacency list. This guarantees correctness but quickly becomes expensive because each update or query may trigger a full traversal of the graph.
Approach 2: Adjacency Tracking with Hash Structures (O((N + E) + Q log N) time, O(N + E) space)
Another improvement keeps adjacency lists in a Hash Table or map structure and only updates edges affected by maintenance operations. Queries still require checking component membership through traversal, but updates become cheaper because edge modifications are constant time. This approach works for smaller graphs but still struggles when queries are frequent since connectivity checks remain expensive.
Approach 3: Union-Find + Sorted Set (O((N + E) α(N) + Q log N) time, O(N) space)
The optimal approach models the grid as connected components using a Disjoint Set Union (Union-Find) structure. Each transmission line performs a union(a, b) operation, quickly merging two components using path compression and union by rank. To support maintenance queries that require retrieving a specific active node (for example, the smallest available station in a component), maintain an ordered set of nodes per component. When components merge, merge or update their sets so queries can retrieve the required element in O(log n) time.
The key insight: connectivity changes are handled by Union-Find in near constant time, while the ordered set efficiently tracks nodes that satisfy query constraints. Instead of recomputing the graph for every query, the algorithm maintains component-level metadata and performs fast lookups.
Recommended for interviews: The Union-Find + ordered set solution is what most interviewers expect for dynamic connectivity problems. A DFS/BFS rebuild shows you understand graph traversal, but the optimized solution demonstrates knowledge of Union Find, component merging, and efficient query handling in large graphs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS/BFS Rebuild per Query | O(Q * (N + E)) | O(N) | Small graphs or when queries are very limited |
| Adjacency + Hash Structures | O((N + E) + Q log N) | O(N + E) | Moderate input sizes with infrequent connectivity checks |
| Union-Find + Sorted Set | O((N + E) α(N) + Q log N) | O(N) | Large graphs with many updates and connectivity queries |