LeetCode 3607 - Power Grid Maintenance

LeetCode Problem 3607

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem gives an undirected graph of c power stations labeled from 1 to c, connected by bidirectional cables. These connections define connected components, which are referred to as power grids. Importantly, these grids are static, meaning connectivity does not change even if stations go offline.

Initially, every station is online. You must process two types of queries. A query [1, x] asks for a maintenance resolution: if station x is online, it resolves the query directly; otherwise, you must find the smallest-index online station within the same connected component as x. If no station in that component is online, the answer is -1. A query [2, x] simply marks station x as offline permanently.

The key challenge is that queries must be answered online and efficiently, with up to 2 * 10^5 queries and up to 10^5 stations. This immediately rules out recomputing connectivity or scanning components per query.

The constraints imply that graph preprocessing is allowed, but query-time operations must be near logarithmic or amortized constant. The graph structure is static, so connected components can be precomputed once.

Edge cases include isolated nodes (no connections), fully connected graphs, repeated offline operations on the same node, and queries asking for offline nodes that belong to singleton components.

Approaches

The brute-force approach recomputes the answer for each query by performing a graph traversal (DFS or BFS) starting from node x to find its connected component and then scanning all nodes in that component to find the smallest online station. This works logically because connectivity is fixed, but it is too slow because each query may require traversing up to O(c) nodes, and there can be O(q) queries.

The key insight is that connected components never change, so we can precompute them once using Union-Find or BFS/DFS. After that, each component can maintain a dynamic structure that tracks currently online nodes. Since we always need the smallest-index online node, a min-heap per component works well if we allow lazy deletion. When a node goes offline, we simply mark it as offline globally, and when querying, we clean outdated heap tops until we find a valid online node.

This transforms the problem into a combination of static graph decomposition and dynamic set querying with efficient minimum retrieval.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q · c)	O(c + n)	DFS/BFS per query to find component and scan
Optimal	O((c + n + q) log c) amortized	O(c + n)	Precompute components + heap per component with lazy deletion

Algorithm Walkthrough

First, we treat the graph as static and compute connected components using either DFS or Union-Find. Each node is assigned a component identifier, which groups nodes that share connectivity.

Second, for each component, we build a min-heap containing all nodes in that component. This heap represents candidates for the smallest indexed online station.

Third, we maintain a global boolean array online[], initially set to True for all nodes. This tracks whether a station is currently operational.

Fourth, we process queries one by one:

1. If the query is [2, x], we mark online[x] = False. We do not remove it from the heap because removal would be expensive.
2. If the query is [1, x] and online[x] is True, we directly return x because the station resolves its own query.
3. Otherwise, we locate the heap for the component of x. We repeatedly remove heap elements from the top while the top node is offline. This is lazy deletion.
4. If the heap becomes empty, we return -1. Otherwise, the top of the heap is the smallest indexed online node.

The use of heaps ensures that we always retrieve the smallest available station efficiently, while lazy deletion avoids expensive updates during offline operations.

Why it works: the invariant is that each component’s heap always contains all nodes in that component, and the global online[] array defines validity. Since heaps are always ordered by node ID, and we only discard invalid nodes when encountered, the first valid heap top is always the correct answer.

Python Solution

from typing import List
import heapq
from collections import defaultdict, deque

class Solution:
    def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(c + 1)]
        for u, v in connections:
            adj[u].append(v)
            adj[v].append(u)
        
        comp_id = [-1] * (c + 1)
        comps = []
        
        for i in range(1, c + 1):
            if comp_id[i] != -1:
                continue
            queue = deque([i])
            comp_id[i] = len(comps)
            nodes = []
            
            while queue:
                node = queue.popleft()
                nodes.append(node)
                for nei in adj[node]:
                    if comp_id[nei] == -1:
                        comp_id[nei] = len(comps)
                        queue.append(nei)
            
            comps.append(nodes)
        
        heaps = []
        for nodes in comps:
            heap = nodes[:]
            heapq.heapify(heap)
            heaps.append(heap)
        
        online = [True] * (c + 1)
        result = []
        
        for t, x in queries:
            if t == 2:
                online[x] = False
            else:
                if online[x]:
                    result.append(x)
                    continue
                
                cid = comp_id[x]
                heap = heaps[cid]
                
                while heap and not online[heap[0]]:
                    heapq.heappop(heap)
                
                if not heap:
                    result.append(-1)
                else:
                    result.append(heap[0])
        
        return result

Implementation Explanation

The code begins by building an adjacency list representation of the graph. It then computes connected components using BFS, assigning each node a component ID and collecting nodes per component.

Next, each component is converted into a min-heap. This heap contains all nodes in that component and is used to efficiently retrieve the smallest indexed online station.

A boolean array online tracks station status. When a station goes offline, it is simply marked false.

For type [1, x] queries, the algorithm first checks if x is online. If so, it returns immediately. Otherwise, it retrieves the heap corresponding to x’s component and pops offline nodes until a valid one is found or the heap becomes empty.

This lazy deletion strategy ensures that each node is removed at most once from the heap, keeping operations efficient.

Go Solution

package main

import (
	"container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func processQueries(c int, connections [][]int, queries [][]int) []int {
	adj := make([][]int, c+1)
	for _, e := range connections {
		u, v := e[0], e[1]
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	compID := make([]int, c+1)
	for i := range compID {
		compID[i] = -1
	}

	comps := [][]int{}

	var bfs func(int)
	bfs = func(start int) {
		q := []int{start}
		compID[start] = len(comps)
		nodes := []int{}

		for len(q) > 0 {
			node := q[0]
			q = q[1:]
			nodes = append(nodes, node)

			for _, nei := range adj[node] {
				if compID[nei] == -1 {
					compID[nei] = len(comps)
					q = append(q, nei)
				}
			}
		}

		comps = append(comps, nodes)
	}

	for i := 1; i <= c; i++ {
		if compID[i] == -1 {
			bfs(i)
		}
	}

	heaps := make([]*MinHeap, len(comps))
	for i, nodes := range comps {
		h := &MinHeap{}
		for _, v := range nodes {
			*h = append(*h, v)
		}
		heap.Init(h)
		heaps[i] = h
	}

	online := make([]bool, c+1)
	for i := 1; i <= c; i++ {
		online[i] = true
	}

	res := []int{}

	for _, q := range queries {
		t, x := q[0], q[1]
		if t == 2 {
			online[x] = false
		} else {
			if online[x] {
				res = append(res, x)
				continue
			}

			cid := compID[x]
			h := heaps[cid]

			for h.Len() > 0 && !online[(*h)[0]] {
				heap.Pop(h)
			}

			if h.Len() == 0 {
				res = append(res, -1)
			} else {
				res = append(res, (*h)[0])
			}
		}
	}

	return res
}

Go-Specific Notes

Go requires explicit heap interface implementation using container/heap. Unlike Python, we cannot rely on built-in priority queues, so we define a custom MinHeap type. The logic remains identical, but heap operations are more verbose. Slice management and BFS queue handling are also explicit due to the lack of built-in deque structures.

Worked Examples

For c = 5 and a fully connected chain, the BFS produces a single component {1,2,3,4,5}. The heap becomes [1,2,3,4,5].

After query [1,3], station 3 is online, so output is 3.

After [2,1], station 1 becomes offline, so online = {2,3,4,5}.

For [1,1], station 1 is offline. Heap top is 1, but it is skipped. Next valid is 2, so output is 2.

After [2,2], online = {3,4,5}. Heap still contains 1 and 2, but both are skipped when popped.

For [1,2], station 2 is offline. Heap skips 1 and 2, so output becomes 3.

For c = 3 with no edges, each node is its own component. Each heap is singleton.

Query [1,1] returns 1.

Query [2,1] marks it offline.

Query [1,1] finds heap empty after lazy deletion, returning -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((c + n + q) log c)	BFS/DSU builds components, heap operations amortized across all nodes
Space	O(c + n)	adjacency list, component mapping, heaps, and online array

The heap operations are amortized because each node is removed from its heap at most once during lazy deletion, ensuring efficient total processing.

Test Cases

# basic example
sol = Solution()
assert sol.processQueries(5, [[1,2],[2,3],[3,4],[4,5]], [[1,3],[2,1],[1,1],[2,2],[1,2]]) == [3,2,3]

# no connections, isolated nodes
assert sol.processQueries(3, [], [[1,1],[2,1],[1,1]]) == [1,-1]

# all offline before query
assert sol.processQueries(2, [[1,2]], [[2,1],[2,2],[1,1]]) == [-1]

# repeated offline operations
assert sol.processQueries(3, [[1,2],[2,3]], [[2,3],[2,3],[1,3]]) == [2]

# single node
assert sol.processQueries(1, [], [[1,1],[2,1],[1,1]]) == [1,-1]

Test	Why
sample chain graph	validates normal component traversal
no edges	validates singleton components
all offline	ensures -1 handling
repeated offline	checks idempotent updates
single node	minimal boundary case

Edge Cases

One important edge case is a fully disconnected graph where every node forms its own component. In this case, each heap contains exactly one node, so once it goes offline, all queries must correctly return -1. The algorithm handles this because heap cleanup will empty the structure after lazy deletion.

Another edge case is repeated [2, x] operations on the same node. Since the online[] array is idempotent, marking an already offline node again has no effect, and heap cleanup naturally ignores it.

A final edge case involves large connected components where many nodes go offline before a query. Even though heaps retain stale entries, lazy deletion ensures correctness by skipping invalid nodes until a valid one is found or exhaustion occurs.