Skip to content

17. Graph#

Problems at a glance#

LC Problem
— Number of Provinces ↗
— Rotten Oranges ↗
— Perfect Squares ↗
— Open the Lock ↗
— Minimum Genetic Mutation ↗
— Word Ladder ↗
— Word Ladder II ↗
— Shortest Path in Binary Matrix ↗
— Jump Game IV ↗
— Sliding Puzzle ↗
— Flood Fill ↗
— Number of Islands ↗
— Max Area of Island ↗
— Count Sub Islands ↗
— Number of Distinct Islands ↗
— Number of Distinct Islands II ↗
— Surrounded Regions ↗
— Pacific Atlantic Water Flow ↗
— Course Schedule ↗
— Eventual Safe States ↗
— Longest Cycle in a Graph ↗
— Redundant Connection ↗
— Redundant Connection II ↗
— Graph Valid Tree ↗
— Minimum Height Trees ↗
— Reconstruct Itinerary ↗
— Is Graph Bipartite? ↗
— Possible Bipartition ↗
— Course Schedule II ↗
— Alien Dictionary ↗
— Sequence Reconstruction ↗
— Parallel Courses ↗
— Parallel Courses III ↗
— Minimum Time to Complete All Tasks ↗
— Build a Matrix With Conditions ↗
— Sort Items by Groups Respecting Dependencies ↗
— Network Delay Time ↗
— Path with Minimum Effort ↗
— Minimum Cost to Reach Destination in Time ↗
— Finding the City With the Smallest Number of Neighbors at a Threshold Distance ↗
— Accounts Merge ↗
— Satisfiability of Equality Equations ↗
— Most Stones Removed ↗
— Number of Good Paths ↗
— Count Components ↗
— Smallest String With Swaps ↗

BFS#

1. Number of Provinces - LeetCode#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        provinces = 0

        for i in range(n):
            if visited[i]:
                continue
            provinces += 1
            queue = deque([i])
            visited[i] = True
            while queue:
                city = queue.popleft()
                for nei in range(n):
                    if isConnected[city][nei] and not visited[nei]:
                        visited[nei] = True
                        queue.append(nei)
        return provinces
Explanation:

  1. Build implicit graph: The adjacency matrix tells us neighbors directly.
  2. BFS from each unvisited city: Each BFS marks one entire connected component.
  3. Count components: Increment provinces once per new BFS launch.

Time: O(n²)  |  Space: O(n)

 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
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.count = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.parent[ra] = rb
            self.count -= 1

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        uf = UnionFind(n)
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    uf.union(i, j)
        return uf.count
Explanation:

  1. Union all edges where isConnected[i][j] = 1.
  2. Track component count — each successful union decrements it.
  3. Return final count of disjoint sets.

Time: O(n² α(n))  |  Space: O(n)

2. Rotten Oranges - LeetCode#

Problem Statement

In a grid, 0 = empty, 1 = fresh orange, 2 = rotten orange. Every minute, fresh oranges adjacent (4-directionally) to a rotten one become rotten. Return minutes until no fresh orange remains, or -1 if impossible.

Example: grid = [[2,1,1],[1,1,0],[0,1,1]] → Output: 4

Code and Explanation 

 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
from collections import deque

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        minutes = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue and fresh:
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))
            minutes += 1

        return minutes if fresh == 0 else -1
Explanation:

  1. Seed queue with all initially rotten oranges; count fresh ones.
  2. Level-order BFS: Process one minute per queue layer.
  3. Rot neighbors and decrement fresh; if BFS ends with fresh > 0, return -1.

Time: O(rows × cols)  |  Space: O(rows × cols)

3. Perfect Squares - LeetCode#

Problem Statement

Given n, return the least number of perfect square numbers that sum to n.

Example: n = 12 → Output: 3 (4 + 4 + 4)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import deque

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i * i for i in range(1, int(n ** 0.5) + 1)]
        queue = deque([n])
        visited = {n}
        steps = 0

        while queue:
            for _ in range(len(queue)):
                rem = queue.popleft()
                if rem == 0:
                    return steps
                for sq in squares:
                    nxt = rem - sq
                    if nxt < 0:
                        break
                    if nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
            steps += 1
        return steps
Explanation:

  1. Treat n as start state; subtract perfect squares to reach 0.
  2. BFS guarantees minimum steps (unweighted shortest path in state graph).
  3. Precompute squares up to √n for efficient transitions.

Time: O(n · √n)  |  Space: O(n)

4. Open the Lock - LeetCode#

Problem Statement

A lock has 4 wheels (0–9). Start at "0000", reach target, avoiding deadends. Each move rotates one wheel one step. Return minimum moves or -1.

Code and Explanation 

 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
from collections import deque

class Solution:
    def openLock(self, deadends: list[str], target: str) -> int:
        dead = set(deadends)
        if "0000" in dead:
            return -1

        queue = deque([("0000", 0)])
        visited = {"0000"}

        while queue:
            state, moves = queue.popleft()
            if state == target:
                return moves
            for i in range(4):
                digit = int(state[i])
                for delta in (-1, 1):
                    nxt = list(state)
                    nxt[i] = str((digit + delta) % 10)
                    nxt = "".join(nxt)
                    if nxt not in dead and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, moves + 1))
        return -1
Explanation:

  1. State space: Each 4-digit string is a node; edges are ±1 on one wheel.
  2. BFS from "0000" finds shortest path to target.
  3. Skip deadends and track visited to avoid cycles.

Time: O(10⁴)  |  Space: O(10⁴)

5. Minimum Genetic Mutation - LeetCode#

Problem Statement

Change startGene to endGene one character at a time using valid genes from bank. Return minimum mutations or -1.

Code and Explanation 

 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
from collections import deque

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        bank_set = set(bank)
        if endGene not in bank_set:
            return -1

        genes = "ACGT"
        queue = deque([(startGene, 0)])
        visited = {startGene}

        while queue:
            gene, steps = queue.popleft()
            if gene == endGene:
                return steps
            for i in range(len(gene)):
                for g in genes:
                    if g == gene[i]:
                        continue
                    nxt = gene[:i] + g + gene[i + 1:]
                    if nxt in bank_set and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, steps + 1))
        return -1
Explanation:

  1. Same pattern as Word Ladder: Each valid mutation is an edge.
  2. BFS counts minimum single-character changes.
  3. Early exit if endGene ∉ bank.

Time: O(n · m · 4) where n = |bank|, m = gene length  |  Space: O(n)

6. Word Ladder - LeetCode#

Problem Statement

Transform beginWord to endWord changing one letter at a time; each intermediate word must be in wordList. Return shortest transformation sequence length or 0.

Code and Explanation 

 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
from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])
        visited = {beginWord}

        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            chars = list(word)
            for i in range(len(chars)):
                orig = chars[i]
                for c in "abcdefghijklmnopqrstuvwxyz":
                    if c == orig:
                        continue
                    chars[i] = c
                    nxt = "".join(chars)
                    if nxt in word_set and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, length + 1))
                chars[i] = orig
        return 0
Explanation:

  1. Try all 26 letter substitutions at each position.
  2. BFS layers = transformation length — first hit of endWord is optimal.
  3. Mark visited to prevent revisiting words.

Time: O(n · m · 26)  |  Space: O(n)

7. Word Ladder II - LeetCode#

Problem Statement

Return all shortest transformation sequences from beginWord to endWord.

Code and Explanation 

 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
47
48
49
50
from collections import deque, defaultdict

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
        word_set = set(wordList)
        if endWord not in word_set:
            return []

        # BFS to build shortest-path graph
        graph = defaultdict(set)
        queue = deque([beginWord])
        visited = {beginWord}
        found = False

        while queue and not found:
            level_visited = set()
            for _ in range(len(queue)):
                word = queue.popleft()
                chars = list(word)
                for i in range(len(chars)):
                    orig = chars[i]
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        if c == orig:
                            continue
                        chars[i] = c
                        nxt = "".join(chars)
                        if nxt not in word_set:
                            continue
                        graph[word].add(nxt)
                        if nxt == endWord:
                            found = True
                        if nxt not in visited and nxt not in level_visited:
                            level_visited.add(nxt)
                            queue.append(nxt)
                    chars[i] = orig
            visited |= level_visited

        result = []

        def dfs(word, path):
            if word == endWord:
                result.append(path[:])
                return
            for nei in graph[word]:
                path.append(nei)
                dfs(nei, path)
                path.pop()

        dfs(beginWord, [beginWord])
        return result
Explanation:

  1. BFS builds a DAG of edges on shortest paths only (level-by-level).
  2. DFS backtracking from beginWord collects all paths to endWord.
  3. Stop BFS early once endWord is reached at current level.

Time: O(n · m · 26) + output size  |  Space: O(n · m)

8. Shortest Path in Binary Matrix - LeetCode#

Problem Statement

Return the length of the shortest clear path from top-left to bottom-right in an n x n binary matrix (8-directional movement). Return -1 if no path.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] or grid[n - 1][n - 1]:
            return -1

        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        queue = deque([(0, 0, 1)])
        grid[0][0] = 1

        while queue:
            r, c, dist = queue.popleft()
            if r == n - 1 and c == n - 1:
                return dist
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append((nr, nc, dist + 1))
        return -1
Explanation:

  1. 8-directional BFS on cells with value 0.
  2. Mark visited by setting cell to 1 when enqueued.
  3. Distance tracked per node — first arrival at (n-1, n-1) is shortest.

Time: O(n²)  |  Space: O(n²)

9. Jump Game IV - LeetCode#

Problem Statement

From index 0, reach index n-1. From i, jump to i±1 or any j where nums[j] == nums[i]. Return minimum jumps.

Code and Explanation 

 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
from collections import deque, defaultdict

class Solution:
    def minJumps(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0

        value_indices = defaultdict(list)
        for i, val in enumerate(nums):
            value_indices[val].append(i)

        queue = deque([(0, 0)])
        visited = {0}

        while queue:
            idx, jumps = queue.popleft()
            if idx == n - 1:
                return jumps

            neighbors = [idx - 1, idx + 1] + value_indices[nums[idx]]
            value_indices[nums[idx]].clear()  # use same-value jump once

            for nei in neighbors:
                if 0 <= nei < n and nei not in visited:
                    visited.add(nei)
                    queue.append((nei, jumps + 1))
        return -1
Explanation:

  1. Index same-value jumps via a hash map of value → indices.
  2. Clear value list after use to avoid redundant same-value edges.
  3. BFS on index graph gives minimum jumps.

Time: O(n)  |  Space: O(n)

10. Sliding Puzzle - LeetCode#

Problem Statement

A 2 x 3 sliding puzzle with tiles 1–5 and 0 (empty). Return minimum moves to reach "123450", or -1.

Code and Explanation 

 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
from collections import deque

class Solution:
    def slidingPuzzle(self, board: list[list[int]]) -> int:
        start = "".join(str(x) for row in board for x in row)
        target = "123450"
        if start == target:
            return 0

        neighbors = {
            0: [1, 3], 1: [0, 2, 4], 2: [1, 5],
            3: [0, 4], 4: [1, 3, 5], 5: [2, 4]
        }

        queue = deque([(start, 0)])
        visited = {start}

        while queue:
            state, moves = queue.popleft()
            zero = state.index("0")
            for nei in neighbors[zero]:
                chars = list(state)
                chars[zero], chars[nei] = chars[nei], chars[zero]
                nxt = "".join(chars)
                if nxt == target:
                    return moves + 1
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, moves + 1))
        return -1
Explanation:

  1. Encode board as string — only 6! = 720 possible states.
  2. Predefine swap neighbors for each empty-cell position.
  3. BFS finds minimum moves to target.

Time: O(6!)  |  Space: O(6!)

DFS#

1. Flood Fill - LeetCode#

Problem Statement

Given an image, starting pixel (sr, sc), and color, perform a flood fill (replace connected same-color region).

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def floodFill(self, image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
        orig = image[sr][sc]
        if orig == color:
            return image

        def dfs(r, c):
            if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]):
                return
            if image[r][c] != orig:
                return
            image[r][c] = color
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        dfs(sr, sc)
        return image
Explanation:

  1. DFS from seed pixel, recoloring matching neighbors.
  2. Base cases: out of bounds or different color.
  3. Early return if orig == color to avoid infinite recursion.

Time: O(rows × cols)  |  Space: O(rows × cols) recursion stack

2. Number of Islands - LeetCode#

Problem Statement

Given a grid of '1' (land) and '0' (water), count the number of islands.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
                return
            grid[r][c] = "0"
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    count += 1
                    dfs(r, c)
        return count
Explanation:

  1. Scan grid; each unvisited '1' starts a new island.
  2. DFS marks entire component by sinking land to '0'.
  3. Increment count per new DFS launch.

Time: O(rows × cols)  |  Space: O(rows × cols)

3. Max Area of Island - LeetCode#

Problem Statement

Return the maximum area of an island in a binary grid.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        best = 0

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            grid[r][c] = 0
            return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))
        return best
Explanation:

  1. DFS returns area of current connected component.
  2. Sink visited cells to avoid double counting.
  3. Track global maximum across all components.

Time: O(rows × cols)  |  Space: O(rows × cols)

4. Count Sub Islands - LeetCode#

Problem Statement

grid1 has islands; grid2 has candidate islands. Count how many islands in grid2 are sub-islands of grid1 (every land cell in grid2's island is also land in grid1).

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countSubIslands(self, grid1: list[list[int]], grid2: list[list[int]]) -> int:
        rows, cols = len(grid1), len(grid1[0])
        count = 0

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid2[r][c] == 0:
                return True
            if grid1[r][c] == 0:
                grid2[r][c] = 0
                return False
            grid2[r][c] = 0
            ok = True
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                if not dfs(r + dr, c + dc):
                    ok = False
            return ok

        for r in range(rows):
            for c in range(cols):
                if grid2[r][c] == 1 and dfs(r, c):
                    count += 1
        return count
Explanation:

  1. DFS each grid2 island; if any cell is water in grid1, mark island invalid.
  2. Propagate False up the recursion if sub-island condition fails.
  3. Count islands where DFS returns True.

Time: O(rows × cols)  |  Space: O(rows × cols)

5. Number of Distinct Islands - LeetCode#

Problem Statement

Count distinct island shapes in a binary grid (shapes are identical under translation).

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numDistinctIslands(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        shapes = set()

        def dfs(r, c, path):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                path.append("b")
                return
            grid[r][c] = 0
            path.append("o")
            dfs(r + 1, c, path); path.append("d")
            dfs(r - 1, c, path); path.append("u")
            dfs(r, c + 1, path); path.append("r")
            dfs(r, c - 1, path); path.append("l")

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    path = []
                    dfs(r, c, path)
                    shapes.add("".join(path))
        return len(shapes)
Explanation:

  1. Encode shape as DFS direction string (o=origin, d/u/r/l=moves, b=backtrack).
  2. Same shape → same string regardless of grid position.
  3. Count unique encodings in a set.

Time: O(rows × cols)  |  Space: O(rows × cols)

6. Number of Distinct Islands II - LeetCode#

Problem Statement

Count distinct island shapes allowing rotation and reflection.

Code and Explanation 

 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
class Solution:
    def numDistinctIslands2(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        shapes = set()

        def dfs(r, c, cells):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return
            grid[r][c] = 0
            cells.append((r, c))
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                dfs(r + dr, c + dc, cells)

        def normalize(cells):
            shapes = []
            for xr, yr in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                points = [(x * xr, y * yr) for x, y in cells]
                min_x = min(p[0] for p in points)
                min_y = min(p[1] for p in points)
                norm = tuple(sorted((x - min_x, y - min_y) for x, y in points))
                shapes.append(norm)
            return min(shapes)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    cells = []
                    dfs(r, c, cells)
                    shapes.add(normalize(cells))
        return len(shapes)
Explanation:

  1. Collect island cells via DFS.
  2. Try 4 axis transformations (original, flip x, flip y, flip both).
  3. Normalize by translating to origin and pick lexicographically smallest tuple.

Time: O(rows × cols × k log k) where k = island size  |  Space: O(rows × cols)

7. Surrounded Regions - LeetCode#

Problem Statement

Capture 'O' regions completely surrounded by 'X'. Border-connected 'O' regions are not captured.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def solve(self, board: list[list[str]]) -> None:
        rows, cols = len(board), len(board[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "O":
                return
            board[r][c] = "T"
            dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)

        for r in range(rows):
            for c in range(cols):
                if (r in (0, rows-1) or c in (0, cols-1)) and board[r][c] == "O":
                    dfs(r, c)

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "T":
                    board[r][c] = "O"
Explanation:

  1. DFS from border 'O' cells, marking them temporary 'T'.
  2. Remaining 'O' are surrounded → flip to 'X'.
  3. Restore 'T' back to 'O'.

Time: O(rows × cols)  |  Space: O(rows × cols)

8. Pacific Atlantic Water Flow - LeetCode#

Problem Statement

Heights grid: water flows from cell to adjacent equal-or-lower cell. Return cells that can reach both Pacific (top/left) and Atlantic (bottom/right) oceans.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        rows, cols = len(heights), len(heights[0])
        pacific, atlantic = set(), set()

        def dfs(r, c, visited, prev_height):
            if (r, c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if heights[r][c] < prev_height:
                return
            visited.add((r, c))
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                dfs(r + dr, c + dc, visited, heights[r][c])

        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])
        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])

        return [[r, c] for r, c in pacific & atlantic]
Explanation:

  1. Reverse thinking: DFS uphill from ocean borders (flow can reach ocean if path is non-decreasing in reverse).
  2. Two sets: cells reachable from Pacific and Atlantic.
  3. Intersection gives cells draining to both.

Time: O(rows × cols)  |  Space: O(rows × cols)

Cycle Detection#

1. Detect Cycle in Undirected Graph - GFG#

Problem Statement

Given an undirected graph with V vertices and E edges, detect if it contains a cycle.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def isCycle(self, V: int, edges: list[list[int]]) -> bool:
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * V

        def dfs(node, parent):
            visited[node] = True
            for nei in graph[node]:
                if not visited[nei]:
                    if dfs(nei, node):
                        return True
                elif nei != parent:
                    return True
            return False

        for i in range(V):
            if not visited[i] and dfs(i, -1):
                return True
        return False
Explanation:

  1. DFS each component; track parent to ignore the back-edge to parent.
  2. Visited neighbor ≠ parent → cycle found.
  3. Handle disconnected graphs by looping all vertices.

Time: O(V + E)  |  Space: O(V + E)

2. Detect Cycle in Directed Graph - GFG#

Problem Statement

Detect if a directed graph has a cycle.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isCycle(self, V: int, edges: list[list[int]]) -> bool:
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)

        state = [0] * V  # 0=unvisited, 1=in-stack, 2=done

        def dfs(node):
            state[node] = 1
            for nei in graph[node]:
                if state[nei] == 1:
                    return True
                if state[nei] == 0 and dfs(nei):
                    return True
            state[node] = 2
            return False

        return any(state[i] == 0 and dfs(i) for i in range(V))
Explanation:

  1. Three-color DFS: 1 = currently in recursion stack (active path).
  2. Edge to active node → back-edge → cycle.
  3. Mark 2 when subtree fully explored.

Time: O(V + E)  |  Space: O(V + E)

3. Course Schedule - LeetCode#

Problem Statement

numCourses courses with prerequisites prerequisites[i] = [a, b] meaning take b before a. Return true if all courses can be finished.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[prereq].append(course)

        state = [0] * numCourses

        def dfs(node):
            state[node] = 1
            for nei in graph[node]:
                if state[nei] == 1 or (state[nei] == 0 and dfs(nei)):
                    return True
            state[node] = 2
            return False

        return not any(state[i] == 0 and dfs(i) for i in range(numCourses))
Explanation:

  1. Prerequisites form a directed graph; cycle means impossible schedule.
  2. DFS cycle detection on prerequisite edges prereq → course.
  3. Return true iff no cycle exists.

Time: O(V + E)  |  Space: O(V + E)

4. Eventual Safe States - LeetCode#

Problem Statement

A node is safe if every path from it leads to a terminal node (no cycle). Return all safe nodes in ascending order.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
        n = len(graph)
        state = [0] * n  # 0=unknown, 1=unsafe(in stack), 2=safe

        def dfs(node):
            if state[node] == 2:
                return True
            if state[node] == 1:
                return False
            state[node] = 1
            for nei in graph[node]:
                if not dfs(nei):
                    return False
            state[node] = 2
            return True

        return [i for i in range(n) if dfs(i)]
Explanation:

  1. Node is safe iff no cycle reachable from it.
  2. DFS marks unsafe nodes on cycles (state=1 revisited).
  3. Nodes reaching only safe terminals get state=2.

Time: O(V + E)  |  Space: O(V + E)

5. Longest Cycle in a Graph - LeetCode#

Problem Statement

Each node i has at most one outgoing edge to edges[i] (-1 if none). Return the length of the longest cycle, or -1.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestCycle(self, edges: list[int]) -> int:
        n = len(edges)
        dist = [-1] * n
        best = -1

        for start in range(n):
            if dist[start] != -1:
                continue
            path, node = [], start
            while node != -1 and dist[node] == -1:
                dist[node] = len(path)
                path.append(node)
                node = edges[node]

            if node != -1 and dist[node] != -1:
                cycle_len = len(path) - dist[node]
                best = max(best, cycle_len)

            for node in path:
                dist[node] = n  # mark visited from this start

        return best
Explanation:

  1. Functional graph: each node has ≤1 outgoing edge → walk until repeat or -1.
  2. On revisit within same walk, cycle length = len(path) - dist[node].
  3. Try all starts to cover all components.

Time: O(n)  |  Space: O(n)

6. Redundant Connection - LeetCode#

Problem Statement

An undirected tree plus one extra edge creates exactly one cycle. Return the edge that can be removed to restore a tree (last edge in input if multiple answers).

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.parent[ra] = rb
        return True

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        uf = UnionFind(len(edges))
        for u, v in edges:
            if not uf.union(u, v):
                return [u, v]
Explanation:

  1. Process edges in order; union endpoints.
  2. If already connected (union returns False), this edge closes the cycle.
  3. First such edge (last in input) is the answer.

Time: O(n α(n))  |  Space: O(n)

7. Redundant Connection II - LeetCode#

Problem Statement

A rooted tree with one extra directed edge. Remove one edge to restore a valid rooted tree.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))

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

    def union(self, a, b):
        if self.find(a) == self.find(b):
            return False
        self.parent[self.find(a)] = self.find(b)
        return True

class Solution:
    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        parent = [0] * (n + 1)
        cand1 = cand2 = None

        for u, v in edges:
            if parent[v]:
                cand1, cand2 = [parent[v], v], [u, v]
            parent[v] = u

        uf = UnionFind(n)
        for u, v in edges:
            if [u, v] == cand2:
                continue
            if not uf.union(u, v):
                return cand1 if cand1 else [u, v]
        return cand2
Explanation:

  1. Two cases: double parent (node with two incoming) or cycle (no double parent).
  2. Track candidate edges when a node gets a second parent.
  3. UF detects cycle; return appropriate redundant edge.

Time: O(n α(n))  |  Space: O(n)

8. Graph Valid Tree - LeetCode#

Problem Statement

n nodes, edges list. Determine if edges form a valid tree (connected, acyclic).

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.parent[ra] = rb
        self.count -= 1
        return True

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        uf = UnionFind(n)
        for u, v in edges:
            if not uf.union(u, v):
                return False
        return uf.count == 1
Explanation:

  1. Tree needs exactly n-1 edges and no cycles.
  2. UF rejects duplicate connections (cycle).
  3. Exactly one component (count == 1) confirms connectivity.

Time: O(n α(n))  |  Space: O(n)

9. Minimum Height Trees - LeetCode#

Problem Statement

For an undirected tree, a centroid root minimizes tree height. Return all MHT roots.

Code and Explanation 

 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
from collections import deque

class Solution:
    def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
        if n <= 2:
            return list(range(n))

        graph = [[] for _ in range(n)]
        degree = [0] * n
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            degree[u] += 1
            degree[v] += 1

        leaves = deque(i for i in range(n) if degree[i] == 1)

        remaining = n
        while remaining > 2:
            layer_size = len(leaves)
            remaining -= layer_size
            for _ in range(layer_size):
                leaf = leaves.popleft()
                for nei in graph[leaf]:
                    degree[nei] -= 1
                    if degree[nei] == 1:
                        leaves.append(nei)
        return list(leaves)
Explanation:

  1. Repeatedly remove leaf nodes (degree 1) layer by layer.
  2. Last 1–2 nodes are tree centroids (MHT roots).
  3. Analogous to topo-sort on a tree.

Time: O(n)  |  Space: O(n)

10. Reconstruct Itinerary - LeetCode#

Problem Statement

Given flight tickets from → to, reconstruct the itinerary starting at "JFK" using all tickets once. Return lexicographically smallest valid itinerary.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        from collections import defaultdict

        graph = defaultdict(list)
        for src, dst in sorted(tickets):
            graph[src].append(dst)

        route = []

        def dfs(airport):
            while graph[airport]:
                dfs(graph[airport].pop(0))
            route.append(airport)

        dfs("JFK")
        return route[::-1]
Explanation:

  1. Sort destinations for lexicographic preference.
  2. DFS (Hierholzer) consumes edges, appending airport when stuck.
  3. Reverse post-order gives Eulerian path using all tickets.

Time: O(E log E)  |  Space: O(E)

Bipartite Graphs#

1. Is Graph Bipartite? - LeetCode#

Problem Statement

Two-color an undirected graph. Return true if bipartite (no odd-length cycle).

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque

class Solution:
    def isBipartite(self, graph: list[list[int]]) -> bool:
        n = len(graph)
        color = [-1] * n

        for start in range(n):
            if color[start] != -1:
                continue
            queue = deque([start])
            color[start] = 0
            while queue:
                node = queue.popleft()
                for nei in graph[node]:
                    if color[nei] == -1:
                        color[nei] = 1 - color[node]
                        queue.append(nei)
                    elif color[nei] == color[node]:
                        return False
        return True
Explanation:

  1. Assign alternating colors (0/1) via BFS.
  2. Neighbor same color → odd cycle → not bipartite.
  3. Check all components (graph may be disconnected).

Time: O(V + E)  |  Space: O(V)

2. Possible Bipartition - LeetCode#

Problem Statement

n people, dislikes pairs who cannot be in the same group. Can we split into two groups?

Code and Explanation 

 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
from collections import deque, defaultdict

class Solution:
    def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        color = {}

        for person in range(1, n + 1):
            if person in color:
                continue
            queue = deque([person])
            color[person] = 0
            while queue:
                node = queue.popleft()
                for nei in graph[node]:
                    if nei not in color:
                        color[nei] = 1 - color[node]
                        queue.append(nei)
                    elif color[nei] == color[node]:
                        return False
        return True
Explanation:

  1. Build dislike graph; bipartition exists iff graph is 2-colorable.
  2. BFS coloring same as Is Graph Bipartite.
  3. Isolated nodes (no dislikes) are trivially valid.

Time: O(n + d) where d = |dislikes|  |  Space: O(n + d)

3. Cycle Detection in Bipartite Graph - [Conceptual]#

Problem Statement

A graph is bipartite iff it has no odd-length cycle. Detect this during 2-coloring.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque

def has_odd_cycle(graph):
    n = len(graph)
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue
        queue = deque([(start, 0)])
        color[start] = 0
        while queue:
            node, dist = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append((nei, dist + 1))
                elif color[nei] == color[node]:
                    return True  # odd cycle exists
    return False
Explanation:

  1. Same-color neighbor on BFS tree edge means odd cycle.
  2. Equivalently: bipartite ⟺ no odd cycle.
  3. Used as subroutine in bipartition problems.

Time: O(V + E)  |  Space: O(V)

4. Check for Odd-Length Cycle - [Conceptual]#

Problem Statement

Determine if an undirected graph contains any cycle of odd length.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque

def has_odd_length_cycle(graph):
    n = len(graph)
    dist = [-1] * n

    for start in range(n):
        if dist[start] != -1:
            continue
        dist[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if dist[nei] == -1:
                    dist[nei] = dist[node] + 1
                    queue.append(nei)
                elif (dist[node] - dist[nei]) % 2 == 0:
                    return True  # same parity = odd cycle
    return False
Explanation:

  1. BFS assigns level parity (even/odd distance from root).
  2. Non-tree edge connecting same parity closes an odd cycle.
  3. Dual view of bipartite coloring conflict.

Time: O(V + E)  |  Space: O(V)

5. M-Coloring Problem - GFG#

Problem Statement

Color graph with at most m colors so no adjacent vertices share a color. Return true if possible.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def graphColoring(self, V: int, edges: list[list[int]], m: int) -> bool:
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        colors = [0] * V

        def can_color(node):
            if node == V:
                return True
            for c in range(1, m + 1):
                if all(colors[nei] != c for nei in graph[node]):
                    colors[node] = c
                    if can_color(node + 1):
                        return True
                    colors[node] = 0
            return False

        return can_color(0)
Explanation:

  1. Try colors 1..m for each vertex in order.
  2. DFS backtrack when no valid color for current vertex.
  3. m=2 reduces to bipartite check; general m uses backtracking.

Time: O(m^V) worst case  |  Space: O(V)

6. Graph Coloring#

Problem Statement

Assign minimum colors to adjacent-different vertices. Classic DFS/backtracking or greedy on special graphs.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def greedy_coloring(self, V: int, edges: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        colors = [-1] * V
        colors[0] = 0

        for node in range(1, V):
            used = {colors[nei] for nei in graph[node] if colors[nei] != -1}
            c = 0
            while c in used:
                c += 1
            colors[node] = c
        return colors
Explanation:

  1. Pick smallest unused color for each vertex in order.
  2. Not optimal but O(V + E) greedy heuristic.
  3. Bipartite graphs need only 2 colors (use BFS coloring instead).

Time: O(V + E)  |  Space: O(V)

7. Team Division - [Codeforces/GFG]#

Problem Statement

Divide players into two teams; given conflicts, determine if a valid 2-team split exists.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.parity = [0] * n

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

    def union(self, a, b, same_team=False):
        ra, rb = self.find(a), self.find(b)
        need = self.parity[a] ^ self.parity[b] ^ (0 if same_team else 1)
        if ra == rb:
            return need == 0
        self.parent[ra] = rb
        self.parity[ra] = need
        return True

def can_divide_teams(n, conflicts):
    uf = UnionFind(n)
    for a, b in conflicts:
        if not uf.union(a, b, same_team=False):
            return False
    return True
Explanation:

  1. Conflict = opposite parity (different teams).
  2. UF tracks XOR parity relative to component root.
  3. Contradiction if conflict edge connects same-parity nodes.

Time: O(n α(n))  |  Space: O(n)

8. Union Find Bipartition Check - [Conceptual]#

Problem Statement

Check bipartition using Union-Find with parity instead of BFS coloring.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.parity = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            root = self.find(self.parent[x])
            self.parity[x] ^= self.parity[self.parent[x]]
            self.parent[x] = root
        return self.parent[x]

    def opposite(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return self.parity[a] != self.parity[b]
        self.parent[ra] = rb
        self.parity[ra] = self.parity[a] ^ self.parity[b] ^ 1
        return True

def is_bipartite_uf(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.opposite(u, v):
            return False
    return True
Explanation:

  1. Each edge demands opposite parity between endpoints.
  2. UF merges with XOR constraint propagation.
  3. Equivalent to BFS 2-coloring but better for incremental/online edges.

Time: O((V+E) α(V))  |  Space: O(V)

9. Two Groups - LeetCode 886 variant#

Problem Statement

Split n people into two groups with no forbidden pair in the same group.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def twoGroups(self, n: int, forbidden: list[list[int]]) -> bool:
        graph = [[] for _ in range(n + 1)]
        for a, b in forbidden:
            graph[a].append(b)
            graph[b].append(a)

        color = {}

        def dfs(node, c):
            color[node] = c
            for nei in graph[node]:
                if nei not in color:
                    if not dfs(nei, 1 - c):
                        return False
                elif color[nei] == c:
                    return False
            return True

        for i in range(1, n + 1):
            if i not in color and not dfs(i, 0):
                return False
        return True
Explanation:

  1. Identical to Possible Bipartition with DFS instead of BFS.
  2. Forbidden pairs become graph edges.
  3. 2-color all components.

Time: O(n + f)  |  Space: O(n + f)

10. Graph Coloring with Constraints - [Advanced Interview Variant]#

Problem Statement

Pre-colored vertices + adjacency constraints: extend coloring with ≤ m colors.

Code and Explanation 

 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
def color_with_constraints(V, edges, fixed_colors, m):
    graph = [[] for _ in range(V)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    colors = list(fixed_colors)

    def dfs(node):
        for nei in graph[node]:
            if colors[nei] == 0:
                used = {colors[x] for x in graph[nei] if colors[x] != 0}
                for c in range(1, m + 1):
                    if c not in used:
                        colors[nei] = c
                        if dfs(nei):
                            return True
                        colors[nei] = 0
                return False
        return True

    for i in range(V):
        if colors[i] == 0:
            for c in range(1, m + 1):
                colors[i] = c
                if dfs(i):
                    break
                colors[i] = 0
            else:
                return None
    return colors
Explanation:

  1. Respect pre-colored vertices (non-zero entries).
  2. DFS assigns remaining with backtracking.
  3. m=2 tests bipartite extension; general m is NP-complete.

Time: O(m^V) worst case  |  Space: O(V)

Topological Sort#

1. Course Schedule II - LeetCode#

Problem Statement

Return a valid course ordering to finish all courses, or [] if impossible.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque(i for i in range(numCourses) if indegree[i] == 0)
        order = []

        while queue:
            node = queue.popleft()
            order.append(node)
            for nei in graph[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return order if len(order) == numCourses else []
Explanation:

  1. Indegree-0 nodes have no unmet prerequisites.
  2. Process layer by layer, decrementing neighbor indegrees.
  3. If len(order) < numCourses, cycle exists.

Time: O(V + E)  |  Space: O(V + E)

2. Alien Dictionary - LeetCode#

Problem Statement

Sorted dictionary of alien words — derive character precedence order.

Code and Explanation 

 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
from collections import deque, defaultdict

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        graph = defaultdict(set)
        indegree = {c: 0 for word in words for c in word}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            for a, b in zip(w1, w2):
                if a != b:
                    if b not in graph[a]:
                        graph[a].add(b)
                        indegree[b] += 1
                    break

        queue = deque(c for c in indegree if indegree[c] == 0)
        order = []

        while queue:
            c = queue.popleft()
            order.append(c)
            for nei in graph[c]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return "".join(order) if len(order) == len(indegree) else ""
Explanation:

  1. Compare adjacent words to find first differing character → edge.
  2. Invalid prefix case: longer word before shorter prefix → "".
  3. Topo sort on character graph gives alien alphabet.

Time: O(C) where C = total characters  |  Space: O(1) — 26 letters

3. All Tasks Scheduling Orders#

Problem Statement

Given task dependencies, return all valid topological orderings.

Code and Explanation 

 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
class Solution:
    def allTopologicalOrders(self, n: int, edges: list[list[int]]) -> list[list[int]]:
        graph = [[] for _ in range(n)]
        indegree = [0] * n
        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1

        result = []
        path = []
        indeg = indegree[:]

        def dfs():
            if len(path) == n:
                result.append(path[:])
                return
            for node in range(n):
                if indeg[node] == 0 and node not in path:
                    path.append(node)
                    indeg[node] = -1
                    for nei in graph[node]:
                        indeg[nei] -= 1
                    dfs()
                    for nei in graph[node]:
                        indeg[nei] += 1
                    indeg[node] = 0
                    path.pop()

        dfs()
        return result
Explanation:

  1. At each step, pick any indegree-0 unvisited node.
  2. Backtrack after exploring all downstream choices.
  3. Exponential output in worst case.

Time: O(n! · (V+E)) worst case  |  Space: O(V + output)

4. Sequence Reconstruction - LeetCode#

Problem Statement

Determine if org is the unique shortest supersequence consistent with all seqs pairwise orderings.

Code and Explanation 

 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
from collections import deque, defaultdict

class Solution:
    def sequenceReconstruction(self, org: list[int], seqs: list[list[int]]) -> bool:
        nodes = set(org)
        graph = defaultdict(set)
        indegree = {x: 0 for x in org}

        for seq in seqs:
            for x in seq:
                nodes.add(x)
            for i in range(len(seq) - 1):
                a, b = seq[i], seq[i + 1]
                if b not in graph[a]:
                    graph[a].add(b)
                    indegree[b] += 1

        if len(nodes) != len(org):
            return False

        queue = deque(x for x in org if indegree[x] == 0)
        order = []

        while queue:
            if len(queue) != 1:
                return False
            node = queue.popleft()
            order.append(node)
            for nei in graph[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return order == org
Explanation:

  1. Build graph from consecutive pairs in each sequence.
  2. Unique topo order requires exactly one indegree-0 node at each step.
  3. Result must equal org.

Time: O(n + s)  |  Space: O(n)

5. Parallel Courses - LeetCode#

Problem Statement

Minimum semesters to finish all courses given prerequisites (take any number per semester).

Code and Explanation 

 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
from collections import deque

class Solution:
    def minimumSemesters(self, n: int, relations: list[list[int]]) -> int:
        graph = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for prev, nxt in relations:
            graph[prev].append(nxt)
            indegree[nxt] += 1

        queue = deque(i for i in range(1, n + 1) if indegree[i] == 0)
        semesters = 0
        taken = 0

        while queue:
            semesters += 1
            for _ in range(len(queue)):
                course = queue.popleft()
                taken += 1
                for nei in graph[course]:
                    indegree[nei] -= 1
                    if indegree[nei] == 0:
                        queue.append(nei)

        return semesters if taken == n else -1
Explanation:

  1. Each BFS layer = one semester.
  2. All indegree-0 courses can run in parallel.
  3. Return -1 if cycle prevents finishing.

Time: O(V + E)  |  Space: O(V + E)

6. Parallel Courses III - LeetCode#

Problem Statement

Each course has duration time[i]. Prerequisites must finish first. Return minimum time to complete all.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        graph = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for prev, nxt in relations:
            graph[prev].append(nxt)
            indegree[nxt] += 1

        dist = [0] * (n + 1)
        queue = deque(i for i in range(1, n + 1) if indegree[i] == 0)
        for i in queue:
            dist[i] = time[i - 1]

        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                dist[nei] = max(dist[nei], dist[node] + time[nei - 1])
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return max(dist[1:])
Explanation:

  1. Topo order ensures prerequisites processed first.
  2. dist[nei] = max over predecessors of finish time + own duration.
  3. Answer = max finish time across all courses.

Time: O(V + E)  |  Space: O(V + E)

7. Minimum Time to Complete All Tasks - LeetCode#

Problem Statement

You are given an integer n, indicating there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[i] = [prevCourse_i, nextCourse_i], denoting that course prevCourse_i must be taken before course nextCourse_i. You are also given a 0-indexed integer array time where time[i] is how many months it takes to complete the (i+1)-th course.

You can take courses simultaneously, and you may return to taking courses at any time. Return the minimum number of months needed to complete all courses.

Code and Explanation

Same technique as Parallel Courses III §6 — DP on topo order tracking max finish time per course.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        graph = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for prev, nxt in relations:
            graph[prev].append(nxt)
            indegree[nxt] += 1

        dist = [0] * (n + 1)
        queue = deque(i for i in range(1, n + 1) if indegree[i] == 0)
        for i in queue:
            dist[i] = time[i - 1]

        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                dist[nei] = max(dist[nei], dist[node] + time[nei - 1])
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return max(dist[1:])
Explanation:

  1. Topo order ensures prerequisites processed first.
  2. dist[nei] = max over predecessors of finish time + own duration.
  3. Answer = max finish time across all courses.

Time: O(V + E)  |  Space: O(V + E)

8. Build a Matrix With Conditions - LeetCode#

Problem Statement

Row and column conditions above, left on values 1..k. Build a k×k matrix or return [].

Code and Explanation 

 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
from collections import deque

class Solution:
    def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]:
        def topo(conditions):
            graph = [[] for _ in range(k + 1)]
            indegree = [0] * (k + 1)
            for above, below in conditions:
                graph[above].append(below)
                indegree[below] += 1
            queue = deque(i for i in range(1, k + 1) if indegree[i] == 0)
            order = []
            while queue:
                node = queue.popleft()
                order.append(node)
                for nei in graph[node]:
                    indegree[nei] -= 1
                    if indegree[nei] == 0:
                        queue.append(nei)
            return order if len(order) == k else []

        row_order = topo(rowConditions)
        col_order = topo(colConditions)
        if not row_order or not col_order:
            return []

        pos = {val: i for i, val in enumerate(col_order)}
        matrix = [[0] * k for _ in range(k)]
        for r, val in enumerate(row_order):
            matrix[r][pos[val]] = val
        return matrix
Explanation:

  1. Separate topo sorts for row and column constraints.
  2. Place value v at (row_rank[v], col_rank[v]).
  3. Cycle in either graph → impossible.

Time: O(k + r + c)  |  Space: O(k)

9. Sort Items by Groups Respecting Dependencies - LeetCode#

Problem Statement

Items belong to groups; both item-level and group-level dependencies exist. Return valid ordering or [].

Code and Explanation 

 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
47
48
49
50
51
from collections import deque

class Solution:
    def sortItems(self, n: int, m: int, group: list[int], beforeItems: list[list[int]]) -> list[int]:
        group = [g + 1 if g != -1 else m + i for i, g in enumerate(group)]
        group_count = max(group) + 1

        def topo(nodes, graph_fn):
            indegree = {x: 0 for x in nodes}
            graph = {x: [] for x in nodes}
            for node in nodes:
                for dep in graph_fn(node):
                    graph[dep].append(node)
                    indegree[node] += 1
            queue = deque(x for x in nodes if indegree[x] == 0)
            order = []
            while queue:
                x = queue.popleft()
                order.append(x)
                for nei in graph[x]:
                    indegree[nei] -= 1
                    if indegree[nei] == 0:
                        queue.append(nei)
            return order if len(order) == len(nodes) else []

        items_by_group = [[] for _ in range(group_count)]
        for i in range(n):
            items_by_group[group[i]].append(i)

        group_graph = [[] for _ in range(group_count)]
        group_indegree = [0] * group_count
        for i in range(n):
            for dep in beforeItems[i]:
                if group[dep] != group[i]:
                    if group[i] not in group_graph[group[dep]]:
                        group_graph[group[dep]].append(group[i])
                        group_indegree[group[i]] += 1

        group_order = topo([g for g in range(group_count) if items_by_group[g]],
                           lambda g: group_graph[g])
        if not group_order:
            return []

        result = []
        for g in group_order:
            item_order = topo(items_by_group[g],
                              lambda i: [d for d in beforeItems[i] if group[d] == g])
            if not item_order:
                return []
            result.extend(item_order)
        return result
Explanation:

  1. Assign unique group IDs to ungrouped items.
  2. Topo sort groups first, then items within each group.
  3. Two-level ordering respects all cross/group dependencies.

Time: O(n + d)  |  Space: O(n)

10. Minimum Height Trees - LeetCode#

Problem Statement

A tree of n nodes is labeled from 0 to n - 1. You are given a 2D integer array edges of length n - 1 where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i.

A set of labels is called valid if, for every label x in the set, the tree remains connected when all other nodes are removed.

Return all minimum height tree (MHT) roots — the valid labels that minimize the height of the resulting rooted tree. The height is the number of edges on the longest downward path from the root to any leaf.

Code and Explanation

Same leaf-removal BFS as Cycle Detection §9 — repeatedly strip degree-1 nodes until centroids remain.

 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
from collections import deque

class Solution:
    def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
        if n <= 2:
            return list(range(n))

        graph = [[] for _ in range(n)]
        degree = [0] * n
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            degree[u] += 1
            degree[v] += 1

        leaves = deque(i for i in range(n) if degree[i] == 1)

        remaining = n
        while remaining > 2:
            layer_size = len(leaves)
            remaining -= layer_size
            for _ in range(layer_size):
                leaf = leaves.popleft()
                for nei in graph[leaf]:
                    degree[nei] -= 1
                    if degree[nei] == 1:
                        leaves.append(nei)
        return list(leaves)
Explanation:

  1. Repeatedly remove leaf nodes (degree 1) layer by layer.
  2. Last 1–2 nodes are tree centroids (MHT roots).
  3. Analogous to topo-sort on a tree.

Time: O(n)  |  Space: O(n)

Shortest Path#

1. Dijkstra Template - GFG#

Problem Statement

Single-source shortest paths in a weighted graph with non-negative edges.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq

def dijkstra(graph, src, n):
    """
    graph[u] = list of (v, weight)
    Returns dist[] array; dist[i] = shortest distance src -> i
    """
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist
Explanation:

  1. Greedy + relaxation: always settle closest unvisited node.
  2. Min-heap efficiently picks next minimum-distance node.
  3. Non-negative weights required — use BFS for unweighted, 0-1 BFS for {0,1} weights.

Time: O((V + E) log V)  |  Space: O(V + E)

2. Network Delay Time - LeetCode#

Problem Statement

Signal from node k spreads with edge weights times[i] = [u, v, w]. Return time for all nodes to receive signal, or -1.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = [float("inf")] * (n + 1)
        dist[k] = 0
        heap = [(0, k)]

        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (d + w, v))

        ans = max(dist[1:])
        return ans if ans < float("inf") else -1
Explanation:

  1. Classic Dijkstra from source k.
  2. Answer = max distance to all reachable nodes.
  3. -1 if any node unreachable.

Time: O((V+E) log V)  |  Space: O(V+E)

3. Path with Minimum Effort - LeetCode#

Problem Statement

Minimize maximum absolute height difference along a path from top-left to bottom-right.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import heapq

class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        dist = [[float("inf")] * cols for _ in range(rows)]
        dist[0][0] = 0
        heap = [(0, 0, 0)]
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]

        while heap:
            effort, r, c = heapq.heappop(heap)
            if r == rows - 1 and c == cols - 1:
                return effort
            if effort > dist[r][c]:
                continue
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    ne = max(effort, abs(heights[r][c] - heights[nr][nc]))
                    if ne < dist[nr][nc]:
                        dist[nr][nc] = ne
                        heapq.heappush(heap, (ne, nr, nc))
        return 0
Explanation:

  1. Edge cost = height diff; path cost = max edge on path (minimax).
  2. Dijkstra with modified relaxation: ne = max(effort, diff).
  3. First arrival at destination is optimal.

Time: O(rows × cols · log(rows × cols))  |  Space: O(rows × cols)

4. Maze with Portals (0-1 BFS) - [Conceptual]#

Problem Statement

Grid maze: walking costs 1, using a portal costs 0. Find shortest path from start to goal.

Code and Explanation 

 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
from collections import deque

def shortest_path_portals(grid, start, goal, portals):
    rows, cols = len(grid), len(grid[0])
    dist = [[float("inf")] * cols for _ in range(rows)]
    dist[start[0]][start[1]] = 0
    dq = deque([(*start, 0)])

    while dq:
        r, c, d = dq.popleft()
        if (r, c) == goal:
            return d
        if d > dist[r][c]:
            continue

        # cost-1 moves (walk)
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                if d + 1 < dist[nr][nc]:
                    dist[nr][nc] = d + 1
                    dq.append((nr, nc, d + 1))

        # cost-0 moves (portal)
        if (r, c) in portals:
            nr, nc = portals[(r, c)]
            if d < dist[nr][nc]:
                dist[nr][nc] = d
                dq.appendleft((nr, nc, d))

    return -1
Explanation:

  1. 0-weight edges → push front; 1-weight → push back.
  2. Equivalent to Dijkstra when weights ∈ {0, 1}.
  3. O(V+E) without heap.

Time: O(rows × cols)  |  Space: O(rows × cols)

5. Minimum Cost to Reach Destination in Time - LeetCode#

Problem Statement

Travel edges with cost and time; must arrive by deadline maxTime. Minimize total cost.

Code and Explanation 

 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
import heapq
from collections import defaultdict

class Solution:
    def minCost(self, maxTime: int, edges: list[list[int]], passingFees: list[int]) -> int:
        n = len(passingFees)
        graph = defaultdict(list)
        for u, v, t in edges:
            graph[u].append((v, t))
            graph[v].append((u, t))

        dist = [[float("inf")] * (maxTime + 1) for _ in range(n)]
        dist[0][0] = passingFees[0]
        heap = [(passingFees[0], 0, 0)]

        while heap:
            cost, node, time = heapq.heappop(heap)
            if node == n - 1:
                return cost
            if cost > dist[node][time]:
                continue
            for nei, t in graph[node]:
                nt = time + t
                if nt <= maxTime:
                    nc = cost + passingFees[nei]
                    if nc < dist[nei][nt]:
                        dist[nei][nt] = nc
                        heapq.heappush(heap, (nc, nei, nt))
        return -1
Explanation:

  1. State = (node, time_used); optimize cost.
  2. Dijkstra on expanded state graph with time budget maxTime.
  3. First arrival at destination with minimum cost wins.

Time: O((V · T + E) log(V · T))  |  Space: O(V · T)

6. Multi-Source BFS - [Conceptual]#

Problem Statement

Find shortest distance from any source to every cell (e.g., distance to nearest gate/land/rotten orange).

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque

def multi_source_bfs(grid, sources):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()

    for r, c in sources:
        dist[r][c] = 0
        queue.append((r, c))

    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1 and grid[nr][nc] == 0:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist
Explanation:

  1. Initialize queue with ALL sources at distance 0.
  2. Standard BFS propagates shortest distance outward.
  3. Used in: Rotten Oranges, Walls and Gates, As Far from Land as Possible.

Time: O(rows × cols)  |  Space: O(rows × cols)

7. Finding the City With the Smallest Number of Neighbors at a Threshold Distance - LeetCode#

Problem Statement

Find the city with fewest reachable cities within distance threshold (smallest index on tie).

Code and Explanation 

 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
import heapq

class Solution:
    def findTheCity(self, n: int, edges: list[list[int]], distanceThreshold: int) -> int:
        graph = [[] for _ in range(n)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        def dijkstra(src):
            dist = [float("inf")] * n
            dist[src] = 0
            heap = [(0, src)]
            while heap:
                d, u = heapq.heappop(heap)
                if d > dist[u]:
                    continue
                for v, w in graph[u]:
                    if d + w < dist[v]:
                        dist[v] = d + w
                        heapq.heappush(heap, (d + w, v))
            return sum(1 for d in dist if 0 < d <= distanceThreshold)

        best_city, min_count = -1, n
        for i in range(n):
            cnt = dijkstra(i)
            if cnt <= min_count:
                min_count = cnt
                best_city = i
        return best_city
Explanation:

Explanation:

  1. Run Dijkstra from each city (n ≤ 100).
  2. Count neighbors with distance ≤ threshold (exclude self).
  3. Pick smallest count; on tie, return city with greatest index.

Time: O(n · (V+E) log V)  |  Space: O(V+E)

Union Find (DSU)#

1. Find Union Basic Template - GFG#

Problem Statement

Implement Disjoint Set Union with find and union supporting connectivity queries.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)
Explanation:

  1. Path compression flattens tree in find.
  2. Union by rank keeps trees shallow.
  3. Amortized α(n) per operation — effectively constant.

Time: O(α(n)) per op  |  Space: O(n)

2. Redundant Connection - LeetCode#

Problem Statement

Find the edge whose removal eliminates the single cycle in an undirected graph.

Code and Explanation

Same UF technique as Cycle Detection §6 — process edges in order; the first edge connecting already-merged nodes closes the cycle.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.parent[ra] = rb
        return True

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        uf = UnionFind(len(edges))
        for u, v in edges:
            if not uf.union(u, v):
                return [u, v]
Explanation:

  1. Process edges in order; union endpoints.
  2. If already connected (union returns False), this edge closes the cycle.
  3. First such edge (last in input) is the answer.

Time: O(n α(n))  |  Space: O(n)

3. Redundant Connection II - LeetCode#

Problem Statement

Remove one directed edge to restore a valid rooted tree.

Code and Explanation

Same technique as Cycle Detection §7 — handle double-parent and directed-cycle cases separately with UF.

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))

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

    def union(self, a, b):
        if self.find(a) == self.find(b):
            return False
        self.parent[self.find(a)] = self.find(b)
        return True

class Solution:
    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        parent = [0] * (n + 1)
        cand1 = cand2 = None

        for u, v in edges:
            if parent[v]:
                cand1, cand2 = [parent[v], v], [u, v]
            parent[v] = u

        uf = UnionFind(n)
        for u, v in edges:
            if [u, v] == cand2:
                continue
            if not uf.union(u, v):
                return cand1 if cand1 else [u, v]
        return cand2
Explanation:

  1. Two cases: double parent (node with two incoming) or cycle (no double parent).
  2. Track candidate edges when a node gets a second parent.
  3. UF detects cycle; return appropriate redundant edge.

Time: O(n α(n))  |  Space: O(n)

4. Accounts Merge - LeetCode#

Problem Statement

Merge accounts sharing common emails. Return merged accounts sorted by name with sorted emails.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

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

class Solution:
    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
        email_to_id = {}
        id_to_name = {}
        uf = UnionFind(len(accounts))

        for i, acc in enumerate(accounts):
            id_to_name[i] = acc[0]
            for email in acc[1:]:
                if email in email_to_id:
                    uf.union(i, email_to_id[email])
                else:
                    email_to_id[email] = i

        groups = {}
        for email, idx in email_to_id.items():
            root = uf.find(idx)
            groups.setdefault(root, []).append(email)

        return [[id_to_name[r]] + sorted(emails) for r, emails in groups.items()]
Explanation:

  1. Index accounts; union accounts sharing any email.
  2. Email map links duplicate emails across accounts.
  3. Group by root, sort emails per merged account.

Time: O(n · k · α(n) + e log e)  |  Space: O(n · k)

5. Satisfiability of Equality Equations - LeetCode#

Problem Statement

Variables a-z with equations == and !=. Determine if all != can be satisfied.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class UnionFind:
    def __init__(self):
        self.parent = list(range(26))

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

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

class Solution:
    def equationsPossible(self, equations: list[str]) -> bool:
        uf = UnionFind()
        for eq in equations:
            if eq[1] == '=':
                uf.union(ord(eq[0]) - 97, ord(eq[3]) - 97)

        for eq in equations:
            if eq[1] == '!':
                if uf.find(ord(eq[0]) - 97) == uf.find(ord(eq[3]) - 97):
                    return False
        return True
Explanation:

  1. Process == first — union equal variables.
  2. Check != — fail if variables in same set.
  3. Transitive equality handled by UF.

Time: O(n α(26))  |  Space: O(1)

6. Most Stones Removed - LeetCode#

Problem Statement

Stones sharing a row or column can be removed. Return maximum stones removable.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.parent[ra] = rb
            self.count -= 1

class Solution:
    def removeStones(self, stones: list[list[int]]) -> int:
        row_id = {}
        col_id = {}
        uf = UnionFind(2 * len(stones))
        idx = 0

        for r, c in stones:
            if r not in row_id:
                row_id[r] = idx; idx += 1
            if c not in col_id:
                col_id[c] = idx; idx += 1
            uf.union(row_id[r], col_id[c])

        return len(stones) - uf.count
Explanation:

  1. Bipartite modeling: row nodes ↔ column nodes; stone connects its row to its col.
  2. Stones in same component can be removed down to 1.
  3. Answer = n - components.

Time: O(n α(n))  |  Space: O(n)

7. Number of Good Paths - LeetCode#

Problem Statement

A good path visits nodes with non-decreasing values; endpoints share same value. Count good paths.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = [1] * n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return 0
        paths = self.count[ra] * self.count[rb]
        self.parent[rb] = ra
        self.count[ra] += self.count[rb]
        return paths

class Solution:
    def numberOfGoodPaths(self, vals: list[int], edges: list[list[int]]) -> int:
        n = len(vals)
        uf = UnionFind(n)
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        nodes = sorted(range(n), key=lambda x: vals[x])
        ans = n  # single-node paths

        for node in nodes:
            for nei in adj[node]:
                if vals[nei] <= vals[node]:
                    ans += uf.union(node, nei)
        return ans
Explanation:

  1. Process nodes in increasing value order.
  2. Union with neighbors of equal or smaller value.
  3. Each union merges path counts — new paths = count[a] × count[b].

Time: O(n log n + E α(n))  |  Space: O(n)

8. Count Components - LeetCode#

Problem Statement

Count connected components in an undirected graph with n nodes and edges.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.parent[ra] = rb
            self.count -= 1

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        uf = UnionFind(n)
        for u, v in edges:
            uf.union(u, v)
        return uf.count
Explanation:

  1. Start with n components; each union reduces count by 1.
  2. Classic UF connectivity counting.
  3. Equivalent to BFS/DFS component count.

Time: O((n+e) α(n))  |  Space: O(n)

9. Smallest String With Swaps - LeetCode#

Problem Statement

Swap any indices in pairs; return lexicographically smallest reachable string.

Code and Explanation 

 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
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

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

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: list[list[int]]) -> str:
        n = len(s)
        uf = UnionFind(n)
        for a, b in pairs:
            uf.union(a, b)

        groups = {}
        for i in range(n):
            root = uf.find(i)
            groups.setdefault(root, []).append(i)

        chars = list(s)
        for indices in groups.values():
            sorted_chars = sorted(chars[i] for i in indices)
            for i, c in zip(sorted(indices), sorted_chars):
                chars[i] = c
        return "".join(chars)
Explanation:

  1. UF groups indices that can be freely swapped.
  2. Sort characters within each group and place smallest at smallest index.
  3. Greedy per component gives global lexicographic minimum.

Time: O(n α(n) + n log n)  |  Space: O(n)

10. Connecting Graphs with Threshold - [Hard Variant]#

Problem Statement

Connect nodes 1..n using edges with weight ≤ threshold. Count components or check full connectivity.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.count = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.parent[ra] = rb
            self.count -= 1

def count_components_threshold(n, edges, threshold):
    uf = UnionFind(n)
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if w > threshold:
            break
        uf.union(u, v)
    return uf.count
Explanation:

  1. Sort edges by weight; union only edges ≤ threshold.
  2. Components shrink as heavier edges become available.
  3. Useful for offline connectivity queries at varying thresholds.

Time: O(E log E + E α(n))  |  Space: O(n)