#3607

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Power Grid Maintenance

Determine which power stations remain connected after maintenance using array scanning and hash lookups to track components efficiently.

array hash table depth first search breadth first search union find

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Union-Find + Sorted Set

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def processQueries(
        self, c: int, connections: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        uf = UnionFind(c + 1)
        for u, v in connections:
            uf.union(u, v)
        st = [SortedList() for _ in range(c + 1)]
        for i in range(1, c + 1):
            st[uf.find(i)].add(i)
        ans = []
        for a, x in queries:
            root = uf.find(x)
            if a == 1:
                if x in st[root]:
                    ans.append(x)
                elif len(st[root]):
                    ans.append(st[root][0])
                else:
                    ans.append(-1)
            else:
                st[root].discard(x)
        return ans

Continue Practicing

#3493 properties graph #2368 reachable nodes with restrictions #928 minimize malware spread ii