Skip to main content
Talentd

Power Grid Maintenance - Solution & Explanation

MediumArrayHash TableDepth-First SearchBreadth-First Search10 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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:

  • Initially, all stations {1, 2, 3, 4, 5} are online and form a single power grid.
  • Query [1,3]: Station 3 is online, so the maintenance check is resolved by station 3.
  • Query [2,1]: Station 1 goes offline. The remaining online stations are {2, 3, 4, 5}.
  • Query [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.
  • Query [2,2]: Station 2 goes offline. The remaining online stations are {3, 4, 5}.
  • Query [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:

  • There are no connections, so each station is its own isolated grid.
  • Query [1,1]: Station 1 is online in its isolated grid, so the maintenance check is resolved by station 1.
  • Query [2,1]: Station 1 goes offline.
  • Query [1,1]: Station 1 is offline and there are no other stations in its grid, so the result is -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

Approach Overview

Problem 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.

Solution

We can use Union-Find to maintain the connection relationships between power stations, thereby determining which grid each station belongs to. For each grid, we use a sorted set (such as SortedList in Python, TreeSet in Java, or std::set in C++) to store all online station IDs in that grid, allowing efficient querying and deletion of stations.

The specific steps are as follows:

  1. Initialize the Union-Find structure and process all connection relationships, merging connected stations into the same set.
  2. Create a sorted set for each grid, initially adding all station IDs to their corresponding grid's set.
  3. Iterate through the query list:
    • For query [1, x], first find the root node of the grid that station x belongs to, then check that grid's sorted set:
      • If station x is online (exists in the set), return x.
      • Otherwise, return the station with the smallest ID in the set (if the set is non-empty), otherwise return -1.
    • For query [2, x], find the root node of the grid that station x belongs to, and remove station x from that grid's sorted set, indicating that the station is offline.
  4. Finally, return all query results of type [1, x].

The time complexity is O((c + n + q) log c) and the space complexity is O(c), where c is the number of stations, and n and q are the number of connections and queries, respectively.

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS/BFS Rebuild per QueryO(Q * (N + E))O(N)Small graphs or when queries are very limited
Adjacency + Hash StructuresO((N + E) + Q log N)O(N + E)Moderate input sizes with infrequent connectivity checks
Union-Find + Sorted SetO((N + E) α(N) + Q log N)O(N)Large graphs with many updates and connectivity queries

Video Solution

Power Grid Maintenance | Simplest Solution | Intuition | Dry Run | Leetcode 3607 | codestorywithMIK • codestorywithMIK • 6,697 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Power Grid Maintenance easy or hard?
Power Grid Maintenance is generally considered a medium-level problem. The challenge comes from recognizing that repeated graph traversals are too slow and switching to a Union-Find based design that maintains connectivity efficiently while supporting ordered queries.
Power Grid Maintenance Python/Java solution
A typical implementation uses a Union-Find class with path compression and union by rank. Each component maintains an ordered structure such as TreeSet in Java, sorted containers in Python, or set + heap variants depending on the requirement. The same logic translates easily across Python, Java, C++, and Go.
How to solve Power Grid Maintenance in O(n)?
Pure O(n) is typically not achievable because dynamic queries require ordered lookups or updates. However, the core connectivity operations can be made almost constant using Union-Find with path compression. The remaining cost comes from ordered set operations, resulting in roughly O((n + q) log n) overall complexity.
What is the best approach for Power Grid Maintenance?
The most efficient approach uses Union-Find (Disjoint Set Union) combined with an ordered set. Union-Find maintains connected components of the power grid in near constant time using path compression. The ordered set tracks nodes within each component so queries can retrieve the required station in O(log n) time.
Is Power Grid Maintenance asked at Google/Amazon/Meta?
Problems involving dynamic graph connectivity, Union-Find, and component queries frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include maintaining network connectivity, detecting connected components, and handling online graph updates.
What data structure is used in Power Grid Maintenance?
The primary data structure is Union-Find (Disjoint Set Union) for tracking connected components. An ordered set or balanced tree structure is often used alongside it to store nodes within each component and support efficient retrieval operations.
What is the time complexity of Power Grid Maintenance?
The optimal solution runs in O((N + E) α(N) + Q log N) time, where α(N) is the inverse Ackermann function from Union-Find operations. Each union or find operation is nearly constant, while ordered set operations such as insert or lookup take O(log n). Space complexity is O(N).

Ready to solve this problem?

Practice Power Grid Maintenance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays