Union-Find (Disjoint Set Union)

Problem: A stone can be removed if another stone shares its row or column. Return the most stones that can be removed.

Solve it on LeetCode ↗

Constraints: 1 ≤ stones.length ≤ 1000 · 0 ≤ xi, yi ≤ 10⁴ · No two stones are at the same coordinate point.

From brute force to the pattern: Trying removal orders with DFS is exponential; components give the answer in near-linear time.

Spot it: Stones sharing a row or column form connected groups, and each group can be reduced to one stone. So the answer is stones − components. Union-find on rows and columns (column ids offset to keep them distinct) finds the components.

Why not another pattern? Simulating removals in some order can get stuck; counting components gives the optimum directly.

Approach:

1. For each stone, union row with ~col (a distinct key for columns).
2. Count distinct roots among the used keys.
3. Return len(stones) − roots.

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        parent = {}

        def find(x):
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for r, c in stones:
            parent[find(r)] = find(~c)  # a stone links its row and its column (~c keeps columns separate)
        components = len({find(x) for x in parent})
        return len(stones) - components  # each group keeps exactly one stone

What the code is doing, line by line:

1. ~c is −c − 1, which can never collide with a row index ≥ 0.
2. Within a connected group, stones can be removed leaf-first (think of a spanning tree) until one remains.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One stone → 0.
• All in one row.
• Stones connected only through a chain.

Complexity: O(n · α(n)) time, O(n) space.

Problem: Accounts sharing any email belong to the same person. Merge them: name followed by sorted emails (any order of accounts).

Solve it on LeetCode ↗

Constraints: 1 ≤ accounts.length ≤ 1000 · 2 ≤ accounts[i].length ≤ 10 · 1 ≤ accounts[i][j].length ≤ 30 · accounts[i][0] consists of English letters. · accounts[i][j] (for j > 0) is a valid email.

From brute force to the pattern: Pairwise account comparison is quadratic; union-find over emails is near-linear.

Spot it: Emails are nodes; an account links all of its emails. Connected components = people → union-find over emails.

Why not another pattern? Comparing every pair of accounts for shared emails is O(a² · e).

Approach:

1. For each account, union each email with the account's first email; remember each email's name.
2. Group emails by find(email).
3. Output [name] + sorted(emails) per group.

from collections import defaultdict

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        parent = {}
        name_of = {}

        def find(x):
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for name, first, *rest in accounts:
            name_of[first] = name
            find(first)
            for email in rest:
                name_of[email] = name
                parent[find(email)] = find(first)  # same account: same person
        groups = defaultdict(list)
        for email in parent:
            groups[find(email)].append(email)
        return [[name_of[root]] + sorted(emails) for root, emails in groups.items()]

What the code is doing, line by line:

1. Linking every email to the account's first email connects the whole account.
2. A shared email links two accounts' components automatically.
3. Names are the same within a person, so any email's name works.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Same name, different people (no shared email).
• An account with one email.
• Chains of accounts linked through different emails.

Complexity: O(E log E) time (sorting dominates), O(E) space for E emails.

Problem: Each day one cell floods. Return the last day you can still walk from the top row to the bottom row on land.

Solve it on LeetCode ↗

Constraints: 2 ≤ row, col ≤ 2 * 10⁴ · 4 ≤ row * col ≤ 2 * 10⁴ · cells.length == row * col · 1 ≤ ri ≤ row · 1 ≤ ci ≤ col · All the values of cells are unique.

From brute force to the pattern: Checking every day with BFS is O((rc)²); binary search + BFS is O(rc log rc); reverse union-find is near-linear.

Spot it: Flooding only removes connections, which union-find can't undo. Run time backwards: start fully flooded and turn cells back into land from the last day. With virtual TOP and BOTTOM nodes, the first day they connect is the answer.

Why not another pattern? Binary search on the day with BFS per check is O(rc log rc) — also fine; reverse union-find is a single pass.

Approach:

1. Nodes 0..r·c − 1, plus TOP = r·c, BOTTOM = r·c + 1.
2. For day from the last down to 1: make cells[day − 1] land; union with land neighbours; top-row cells with TOP, bottom-row with BOTTOM.
3. If find(TOP) == find(BOTTOM), return day − 1 (that cell was still land on day − 1).

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        TOP, BOTTOM = row * col, row * col + 1
        parent = list(range(row * col + 2))
        land = [[False] * col for _ in range(row)]

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            parent[find(a)] = find(b)

        for day in range(len(cells), 0, -1):  # undo the floods, latest first
            r, c = cells[day - 1][0] - 1, cells[day - 1][1] - 1
            land[r][c] = True
            node = r * col + c
            if r == 0:
                union(node, TOP)
            if r == row - 1:
                union(node, BOTTOM)
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < row and 0 <= nc < col and land[nr][nc]:
                    union(node, nr * col + nc)
            if find(TOP) == find(BOTTOM):
                return day - 1  # on day - 1 this cell was still land, and a path existed
        return 0

What the code is doing, line by line:

1. Going backwards, land only appears, so connections only form: exactly what union-find supports.
2. The virtual TOP and BOTTOM nodes turn "any top cell to any bottom cell" into one connectivity question.
3. When restoring the cell flooded on day creates the connection, the land on day day − 1 has a crossing.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One column.
• A crossing only via a winding path.
• The first flood already blocks everything.

Complexity: O(r · c · α(r · c)) time and space.

Problem: An m × n grid starts as water. After each addLand position, return the number of islands.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ m, n, positions.length ≤ 10⁴ · 1 ≤ m * n ≤ 10⁴ · positions[i].length == 2 · 0 ≤ ri < m · 0 ≤ ci < n

From brute force to the pattern: Counting islands with BFS after every addition is O(k · mn); union-find is near O(k).

Spot it: Islands only merge as land is added, never split → union-find handles each addition in near-constant time: the new cell is a new island, and each union with a neighbouring island of a different root removes one.

Why not another pattern? Re-running a flood-fill count after every addition is O(k · m · n).

Approach:

1. parent dict for land cells only; islands = 0.
2. Add (r, c) (skip duplicates): parent[cell] = cell, islands += 1.
3. For each land neighbour: if its root differs, union and islands −= 1.
4. Record islands.

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = {}  # land cell -> parent cell

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path halving
                x = parent[x]
            return x

        islands = 0
        result = []
        for r, c in positions:
            cell = (r, c)
            if cell not in parent:  # adding land twice changes nothing
                parent[cell] = cell
                islands += 1  # a brand-new island
                for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if nb in parent:
                        a, b = find(cell), find(nb)
                        if a != b:
                            parent[a] = b  # two islands become one
                            islands -= 1
            result.append(islands)
        return result

What the code is doing, line by line:

1. Only land cells are stored, so the grid is never allocated.
2. Each successful union merges two different islands, reducing the count by one.
3. A neighbour already in the same set (e.g. two neighbours of one island) doesn't change the count.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The same position added twice.
• A cell that joins three islands at once.
• 1×1 grid.

Complexity: O(k · α(k)) time for k additions, O(k) space.

Problem: Change at most one 0 to 1. Return the size of the largest island possible.

Solve it on LeetCode ↗

Constraints: n == grid.length · n == grid[i].length · 1 ≤ n ≤ 500 · grid[i][j] is either 0 or 1.

From brute force to the pattern: Flip + BFS for every zero is O(n⁴); precomputed sizes make each zero O(1).

Spot it: Precompute every island's component id and size (union-find or flood fill). Flipping a 0 joins the distinct islands next to it, so its result is 1 + Σ sizes of the distinct neighbouring ids.

Why not another pattern? Flipping each 0 and re-measuring with BFS is O(n⁴).

Approach:

1. Union-find over land cells, tracking component sizes.
2. For each 0: collect the roots of its land neighbours in a set; candidate 1 + Σ size[root].
3. Answer: the max candidate, or n² if there's no 0.

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        parent = list(range(n * n))
        size = [1] * (n * n)

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for r in range(n):
            for c in range(n):
                if grid[r][c]:
                    for nr, nc in ((r + 1, c), (r, c + 1)):
                        if nr < n and nc < n and grid[nr][nc]:
                            a, b = find(r * n + c), find(nr * n + nc)
                            if a != b:
                                parent[a] = b
                                size[b] += size[a]  # island sizes add up
        best = max((size[find(i)] for i in range(n * n) if grid[i // n][i % n]), default=0)
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    roots = {find(nr * n + nc) for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1))
                             if 0 <= nr < n and 0 <= nc < n and grid[nr][nc]}  # distinct neighbouring islands
                    best = max(best, 1 + sum(size[x] for x in roots))
        return best

What the code is doing, line by line:

1. Cells are numbered r · n + c for the union-find arrays.
2. The set removes duplicates when the same island touches the 0 from two sides.
3. If the grid has no 0, the answer is the existing largest island (all ones → n²).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All ones → n².
• All zeros → 1.
• One island touching a zero on two sides.

Complexity: O(n² · α(n²)) time, O(n²) space.

Problem: Friendship is transitive. Given [timestamp, x, y] logs, return the earliest time everyone is acquainted, or −1.

Solve it on LeetCode ↗ (Premium)

Constraints: 2 ≤ n ≤ 100 · 1 ≤ logs.length ≤ 10⁴ · logs[i].length == 3 · 0 ≤ timestampi ≤ 10⁹ · 0 ≤ xi, yi ≤ n - 1 · xi != yi · All the values timestampi are unique · All the pairs (xi, yi) occur at most one time in the input

From brute force to the pattern: Checking connectivity with BFS after every log is O(L · (n + L)); union-find is near-linear.

Spot it: Groups only merge over time → process logs in time order with union-find, counting groups. The first time the count reaches 1 is the answer.

Why not another pattern? Rebuilding the graph and checking connectivity after every log is O(logs · n).

Approach:

1. Sort logs by timestamp; groups = n.
2. For each log: if x and y have different roots, union and groups −= 1.
3. When groups == 1, return the timestamp; otherwise −1.

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        groups = n
        for t, x, y in sorted(logs):  # in time order
            a, b = find(x), find(y)
            if a != b:
                parent[a] = b
                groups -= 1  # two friend groups merge
                if groups == 1:
                    return t  # everyone is connected now
        return -1

What the code is doing, line by line:

1. Each merge of two different groups reduces the number of groups by one.
2. Logs between people already in the same group change nothing.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Never fully connected → −1.
• Logs not sorted.
• n = 1 (never happens per constraints, but 0 groups to merge).

Complexity: O(L log L + L · α(n)) time, O(n) space.

Problem: Swaps between given index pairs can be done any number of times. Minimise the Hamming distance between source and target.

Solve it on LeetCode ↗

Constraints: n == source.length == target.length · 1 ≤ n ≤ 10⁵ · 1 ≤ source[i], target[i] ≤ 10⁵ · 0 ≤ allowedSwaps.length ≤ 10⁵ · allowedSwaps[i].length == 2 · 0 ≤ ai, bi ≤ n - 1 · ai != bi

From brute force to the pattern: Exploring swap sequences is exponential; components + counting is linear.

Spot it: Swaps compose: indices in the same union-find component can be permuted arbitrarily. So per component, the matches are the multiset overlap between source values and target values.

Why not another pattern? Simulating swaps or searching permutations is exponential.

Approach:

1. Union the index pairs.
2. Per component root: counter of source values.
3. For each index, if its target value is available in its component's counter, use it; otherwise count a mismatch.

from collections import Counter, defaultdict

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in allowedSwaps:
            parent[find(a)] = find(b)  # these positions can exchange values
        available = defaultdict(Counter)  # component -> source values it holds
        for i, x in enumerate(source):
            available[find(i)][x] += 1
        distance = 0
        for i, t in enumerate(target):
            pool = available[find(i)]
            if pool[t]:
                pool[t] -= 1  # some source value in this component can be moved here
            else:
                distance += 1
        return distance

What the code is doing, line by line:

1. Adjacent transpositions within a connected set generate every permutation of that set.
2. Matching target values against the component's multiset counts the best overlap.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No swaps (plain Hamming distance).
• Duplicate values.
• Everything connected.

Complexity: O(n + s · α(n)) time, O(n) space.

Problem: A path's score is its smallest road. Paths may repeat roads and cities. Return the minimum score of a path from 1 to n.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁵ · 1 ≤ roads.length ≤ 10⁵ · roads[i].length == 3 · 1 ≤ ai, bi ≤ n · ai != bi · 1 ≤ distancei ≤ 10⁴ · There are no repeated edges. · There is at least one path between 1 and n.

From brute force to the pattern: Searching paths with a max-min objective is overkill; the component's smallest road is the answer.

Spot it: Because paths can wander and come back, any road in the same connected component as city 1 (and n) can be included. Find the component with union-find and take its smallest road.

Why not another pattern? Dijkstra-style path optimisation is unnecessary: the repetition rule removes the path structure.

Approach:

1. Union all roads.
2. Return the minimum distance among roads whose endpoints share city 1's root.

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        parent = list(range(n + 1))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b, _ in roads:
            parent[find(a)] = find(b)
        root = find(1)
        return min(d for a, b, d in roads if find(a) == root)  # any road reachable from city 1

What the code is doing, line by line:

1. From city 1 you can detour to any road in its component and come back, then continue to n.
2. Both endpoints of a road are in the same component, so checking one is enough.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Disconnected parts with smaller roads (ignored).
• A single road.
• The smallest road on a dead-end branch.

Complexity: O(E · α(n)) time, O(n) space.

Problem: Nodes i, j are linked if |nums[i] − nums[j]| ≤ maxDiff (nums sorted). Answer reachability queries.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁵ · nums is sorted in non-decreasing order. · 0 ≤ maxDiff ≤ 10⁵ · 1 ≤ queries.length ≤ 10⁵ · queries[i] == [ui, vi] · 0 ≤ ui, vi < n

From brute force to the pattern: All pairwise edges + BFS is O(n²); scanning gaps is O(n).

Spot it: With sorted values, if i reaches some j > i + 1, then each step in between also has a small gap, so components are contiguous runs broken where nums[i+1] − nums[i] > maxDiff. Label runs (a 1D union-find).

Why not another pattern? Building all O(n²) edges is too slow.

Approach:

1. group[0] = 0; group[i] = group[i − 1] + (gap > maxDiff).
2. Query: group[u] == group[v].

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        group = [0] * n
        for i in range(1, n):
            group[i] = group[i - 1] + (nums[i] - nums[i - 1] > maxDiff)  # a big gap starts a new component
        return [group[u] == group[v] for u, v in queries]

What the code is doing, line by line:

1. If adjacent sorted values are close, they're directly linked, so a run of close neighbours is connected.
2. A gap larger than maxDiff can't be jumped by anyone, since every pair across it differs even more.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• u == v.
• Equal values.
• Every gap too large.

Complexity: O(n + q) time, O(n) space.

Problem: Same graph but nums is unsorted, and queries ask for the shortest path length (−1 if unreachable).

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁵ · 0 ≤ maxDiff ≤ 10⁵ · 1 ≤ queries.length ≤ 10⁵ · queries[i] == [ui, vi] · 0 ≤ ui, vi < n

From brute force to the pattern: BFS per query is O(q · n²) on the implicit graph; greedy jumps with binary lifting are O(log n) per query.

Spot it: In sorted order, the best move from a node is to the farthest position still within maxDiff (greedy jumps, like Jump Game II). Precompute that with two pointers, then binary lifting answers each query in O(log n).

Why not another pattern? BFS per query is O(n²) per query.

Approach:

1. Sort indices by value; pos[node] = its sorted position.
2. reach[p] = largest q with vals[q] − vals[p] ≤ maxDiff (two pointers); up[0] = reach, up[j] = up[j−1] ∘ up[j−1].
3. Query a < b (positions): jump with the largest powers while up[j][a] < b, counting 2^j; then one more jump if reach[a] ≥ b, else −1.

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[int]:
        order = sorted(range(n), key=lambda i: nums[i])
        pos = [0] * n
        for p, i in enumerate(order):
            pos[i] = p
        vals = [nums[i] for i in order]
        reach = [0] * n  # farthest sorted position reachable in one step
        q = 0
        for p in range(n):
            q = max(q, p)
            while q + 1 < n and vals[q + 1] - vals[p] <= maxDiff:
                q += 1
            reach[p] = q
        up = [reach]  # up[j][p]: position after 2^j greedy jumps
        for _ in range(n.bit_length()):
            prev = up[-1]
            up.append([prev[prev[p]] for p in range(n)])
        answer = []
        for u, v in queries:
            a, b = sorted((pos[u], pos[v]))
            if a == b:
                answer.append(0)
                continue
            jumps = 0
            for j in range(len(up) - 1, -1, -1):
                if up[j][a] < b:
                    a = up[j][a]  # still short of b: take these 2^j jumps
                    jumps += 1 << j
            answer.append(jumps + 1 if reach[a] >= b else -1)  # one more jump, or stuck
        return answer

What the code is doing, line by line:

1. Jumping to the farthest reachable position is never worse: anything reachable from a nearer position is reachable from the farther one too.
2. Binary lifting takes jumps in powers of two while staying short of the target, then checks the final jump.
3. If the greedy walk gets stuck (reach[a] == a), the target is in another component: −1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Same node → 0.
• Different components → −1.
• Equal values.

Complexity: O((n + q) log n) time, O(n log n) space.

Problem: A tree had one extra edge added. Return the edge to remove (the last such edge in the input if several work).

Solve it on LeetCode ↗

Constraints: n == edges.length · 3 ≤ n ≤ 1000 · edges[i].length == 2 · 1 ≤ ai < bi ≤ edges.length · ai != bi · There are no repeated edges. · The given graph is connected.

From brute force to the pattern: Removing each edge and testing is O(n²); union-find is near-linear.

Spot it: Adding edges one by one, the extra edge is the one that joins two nodes already connected → union-find detects it immediately.

Why not another pattern? Removing each edge and checking connectivity is O(n²).

Approach:

1. For each edge in order: if find(a) == find(b), return it.
2. Otherwise union them.

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        parent = list(range(len(edges) + 1))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return [a, b]  # already connected: this edge closes the cycle
            parent[ra] = rb
        return []

What the code is doing, line by line:

1. The graph has exactly one cycle; the first edge that closes it, in input order, is the last cycle edge to appear — the one the problem asks for.
2. Every other edge joins two different components.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• The cycle includes the first edges.
• Small cycle of length 3.
• The extra edge is last.

Complexity: O(n · α(n)) time, O(n) space.

Problem: Equations are a==b or a!=b over letters. Can all hold at once?

Solve it on LeetCode ↗

Constraints: 1 ≤ equations.length ≤ 500 · equations[i].length == 4 · equations[i][0] is a lowercase letter. · equations[i][1] is either '=' or '!'. · equations[i][2] is '='. · equations[i][3] is a lowercase letter.

From brute force to the pattern: Assigning values is exponential; union-find is linear.

Spot it: Equalities are transitive → union-find groups letters that must be equal. Then each != must connect different groups.

Why not another pattern? Trying value assignments is exponential in the number of letters.

Approach:

1. Union the two letters of every ==.
2. For every !=, if both letters have the same root, return false.

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        parent = list(range(26))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for e in equations:
            if e[1] == "=":
                parent[find(ord(e[0]) - 97)] = find(ord(e[3]) - 97)  # must be equal
        for e in equations:
            if e[1] == "!" and find(ord(e[0]) - 97) == find(ord(e[3]) - 97):
                return False  # forced equal, but required different
        return True

What the code is doing, line by line:

1. All equalities must be applied before checking inequalities, because equality chains can come in any order.
2. a != a is caught because a letter is always in its own group.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• a!=a → false.
• Long equality chains.
• Only inequalities → true.

Complexity: O(m · α(26)) time, O(1) space.

Problem: Move cables (each connects two computers) so all n computers are connected. Return the fewest moves, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵ · 1 ≤ connections.length ≤ min(n * (n - 1) / 2, 10⁵) · connections[i].length == 2 · 0 ≤ ai, bi < n · ai != bi · There are no repeated connections. · No two computers are connected by more than one cable.

From brute force to the pattern: Simulating moves is complicated; counting components is near-linear.

Spot it: Each move can join two components, using a redundant cable. With at least n − 1 cables there are always enough spares, so the answer is components − 1, counted with union-find.

Why not another pattern? Simulating cable moves is unnecessary once the counting argument is clear.

Approach:

1. If len(connections) < n − 1, return −1.
2. Union all cables, counting successful unions.
3. Return components − 1.

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1  # not enough cables to connect n computers
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        components = n
        for a, b in connections:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                components -= 1
        return components - 1  # one move per extra component

What the code is doing, line by line:

1. A connected graph on n nodes needs n − 1 edges, so fewer cables can never work.
2. Otherwise the redundant cables (those inside a component) are enough to link the components.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Too few cables → −1.
• Already connected → 0.
• Isolated computers.

Complexity: O(m · α(n)) time, O(n) space.

Problem: Stations go offline over time (grids stay connected). For a check at x: x if online, else the smallest online id in its grid, else −1.

Solve it on LeetCode ↗

From brute force to the pattern: Scanning a grid per query is O(c); lazy heaps are O(log c) amortised.

Spot it: Grids are fixed connected components → union-find once. Each component keeps a min-heap of its ids; offline stations are removed lazily when they reach the top.

Why not another pattern? Scanning a grid for its smallest online station per query is O(c) each.

Approach:

1. Union all cables; heap of ids per root.
2. Type 2: mark offline.
3. Type 1: if online, answer x; else pop offline ids from its grid's heap and answer the top or −1.

import heapq

class Solution:
    def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
        parent = list(range(c + 1))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in connections:
            parent[find(a)] = find(b)
        grid = {}  # root -> min-heap of station ids in that grid
        for s in range(1, c + 1):
            grid.setdefault(find(s), []).append(s)  # added in increasing order: already a heap
        offline = set()
        answer = []
        for kind, x in queries:
            if kind == 2:
                offline.add(x)
                continue
            if x not in offline:
                answer.append(x)  # it handles its own check
                continue
            heap = grid[find(x)]
            while heap and heap[0] in offline:
                heapq.heappop(heap)  # lazily drop stations that went offline
            answer.append(heap[0] if heap else -1)
        return answer

What the code is doing, line by line:

1. Taking a station offline doesn't change connectivity, so the components are computed once.
2. Stations never come back online, so a popped offline id never needs to return.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All stations offline → −1.
• Isolated stations.
• Checking an online station.

Complexity: O((c + n) α(c) + q log c) time, O(c) space.

Problem: Swap characters at any given pairs any number of times. Return the lexicographically smallest string.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10^5 · 0 ≤ pairs.length ≤ 10^5 · 0 ≤ pairs[i][0], pairs[i][1] < s.length · s only contains lower case English letters.

From brute force to the pattern: Searching swap sequences is exponential; components + sorting is near-linear.

Spot it: Swaps compose: indices in the same union-find component can be permuted freely, so give each component its characters in sorted order.

Why not another pattern? Simulating swaps can't reach every permutation efficiently.

Approach:

1. Union all pairs.
2. Group indices by root.
3. Sort each group's characters and write them into its sorted indices.

from collections import defaultdict

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        parent = list(range(len(s)))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in pairs:
            parent[find(a)] = find(b)
        groups = defaultdict(list)
        for i in range(len(s)):
            groups[find(i)].append(i)  # indices in increasing order
        out = list(s)
        for idx in groups.values():
            for i, ch in zip(idx, sorted(s[i] for i in idx)):
                out[i] = ch  # smallest letters to the earliest positions
        return "".join(out)

What the code is doing, line by line:

1. Repeated swaps along connected pairs can produce any permutation of a component.
2. Sorted letters into sorted positions is the smallest arrangement of each component.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No pairs (unchanged).
• Everything connected (sorted string).
• Repeated pairs.

Complexity: O(n log n + p α(n)) time, O(n) space.