Topic 11: Graphs

Graph algorithms are largely categorized into traversal, shortest paths, connectivity components, and cycle/dependency detection.

Relations, when well represented as graphs can be exploited to solve some common problems.

Canonical Questions #

Graph Traversal (DFS & BFS) #

• Explore graph components, find paths, count connected or island areas.

  Traversal could require some basic statistics / counting or something.

  • Flood filling is a great mental model to keep in mind for this.
  • Keep in mind which direction to traverse, sometimes the easier way is to do a reverse-reachability approach.

Problems #

1. Find if Path Exists in Graph (1971)

   Literally just a graph traversal question

   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 defaultdict, deque class Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: """ We could directly do a graph traversal. """ adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) visited = set() q = deque([source]) while q: node = q.popleft() if node == destination: return True for nei in adj[node]: if nei not in visited: visited.add(nei) q.append(nei) return False

   Code Snippet 1: Graph Traversal (BFS)
   Pattern Extraction

   Core Insight: Direct graph traversal (BFS or DFS) from source to destination. The simplest graph reachability problem. Pattern Name: BFS/DFS Reachability Check Canonical Section: Graphs > BFS/DFS Basics Recognition Signals:

   • “Does a path exist between two nodes?”
   • Unweighted undirected graph
   • Boolean output

   Anti-Signals:

   • Need shortest path length – BFS gives this but need to track distance
   • Weighted graph – Dijkstra

   Decision Point: The most basic graph problem. BFS or DFS, either works. Union-Find also works for static reachability.

   Pitfalls and Misconceptions

   1. Trap: Not building an adjacency list first. Why: Edge list requires \(O(E)\) scan to find neighbours. Adjacency list gives \(O(\text{degree})\). Correction: adj = defaultdict(list); for u,v in edges: adj[u].append(v); adj[v].append(u).
   Problem Mutations

   1. What if you needed the shortest path? (stress-tests: existence only) BFS naturally finds shortest paths in unweighted graphs. Track distance during traversal.
   2. What if the graph were dynamic (edges added/removed)? (stress-tests: static) Union-Find for dynamic connectivity. BFS/DFS requires re-traversal per query.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Find if Path Exists in Graph.
   

2. Number of Islands (200)

   It’s a flood fill from all possible islands and trying to reach the others.

   As a memory hack, just reuse the input for visited.

   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

   # BFS approach to flood filling from collections import deque class Solution: def numIslands(self, grid: List[List[str]]) -> int: ROWS, COLS = len(grid), len(grid[0]) DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)] if not ROWS or not COLS: return 0 count = 0 # space trick: reuse input grid for visited tracking # helper BFS: def bfs(r, c): queue = deque([(r,c)]) grid[r][c] = '0' # mark first as visited while queue: row, col = queue.popleft() for dr, dc in DIRS: nr, nc = row + dr, col + dc if is_valid_nei:=(0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == '1'): grid[nr][nc] = '0' # preemptively mark to reduce search spaces, before adding to queue queue.append((nr, nc)) return for r in range(ROWS): for c in range(COLS): if is_island:=(grid[r][c] == '1'): bfs(r, c) count += 1 return count

   Code Snippet 2: Iterative BFS approach to flood filling, every cell may be a start to the BFS

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   # DFS approach to flood filling: this is a recursive DFS that we've done here class Solution: def numIslands(self, grid: List[List[str]]) -> int: ROWS, COLS = len(grid), len(grid[0]) def dfs(r, c): if not (0 <= r < ROWS and 0 <= c < COLS) or grid[r][c] == '0': return grid[r][c] = '0' for dr, dc in [ (0,1), (0,-1), (1,0), (-1,0) ]: dfs(r+dr, c+dc) count = 0 for r in range(ROWS): for c in range(COLS): if grid[r][c] == '1': count += 1 dfs(r, c) return count

   Code Snippet 3: Recursive DFS approach to flood filling (recursive is typically simpler to implement)

   We can also use union find to solve this. Key observations here:

   1. we use a dict here because we want to track tuples ((r, c)) – that’s what the grid variant of the union find boilerplate is about
   2. we wish to attempt multiple union operations but we want to avoid redundant checks, that ’s why we’ve fixed the direction of how we traverse the grid – basically each edge once

      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

      class Solution: def numIslands(self, grid: List[List[str]]) -> int: rows, cols = len(grid), len(grid[0]) parent = {} rank = {} def find(x): # recursive find if parent[x] != x: parent[x] = find(parent[x]) # path compression return parent[x] def union(x, y): rootX, rootY = find(x), find(y) if rootX != rootY: if rank[rootX] > rank[rootY]: parent[rootY] = rootX elif rank[rootX] < rank[rootY]: parent[rootX] = rootY else: parent[rootY] = rootX rank[rootX] += 1 # Initialize parent and rank for land cells for r in range(rows): for c in range(cols): if grid[r][c] == '1': parent[(r, c)] = (r, c) rank[(r, c)] = 0 # Union adjacent land cells (right and down to avoid duplicates) for r in range(rows): for c in range(cols): if grid[r][c] == '1': for dr, dc in [(0, 1), (1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1': union((r, c), (nr, nc)) # Count distinct roots representing islands return len(set(find(x) for x in parent))

      Code Snippet 4: Union find approach to solving flood fill number of islands
   Pattern Extraction

   Core Insight: Each unvisited land cell starts a flood fill (BFS/DFS). Each flood fill discovers one complete island. Count the number of flood fills triggered. Pattern Name: Grid Flood Fill / Connected Component Counting Canonical Section: Graphs > BFS/DFS on Grids Recognition Signals:

   • 2D grid with cells in two states (land/water, 0/1)
   • “Count connected regions” or “number of islands”
   • 4-directional adjacency (up/down/left/right)

   Anti-Signals:

   • 8-directional adjacency – add 4 diagonal directions
   • Need the AREA of each island, not just count – track size during flood fill. Connects to LC 695
   • Dynamic grid (cells change) – union-find with incremental updates

   Decision Point: BFS vs DFS vs Union-Find: all work. BFS avoids stack overflow on large grids. DFS is shorter to implement. Union-Find is best for dynamic grids with online updates.

   Pitfalls and Misconceptions

   1. Trap: Not marking cells as visited BEFORE adding to the BFS queue (marking on pop instead). Why: Without pre-marking, the same cell can be added multiple times by different neighbours, wasting time and causing queue explosion. Correction: Mark as visited WHEN ADDING to queue: grid[nr][nc] = '0'; queue.append((nr, nc)).
   2. Trap: Using a separate visited set when the grid can be modified in-place. Why: \(O(mn)\) extra space for the visited set. Modifying grid[r][c] = '0' uses \(O(1)\) space. Correction: Mutate the grid to mark visited cells.
   3. Trap: Forgetting diagonal checks when the problem specifies 8-connectivity (not this problem, but a common variant error). Why: LC 200 uses 4-directional adjacency. Adding diagonals changes the answer. Correction: Check the problem statement for connectivity type. LC 200 = 4-directional.
   Problem Mutations

   1. What if cells could flip (land to water or vice versa) and you needed island count after each flip? (stress-tests: static grid) Union-Find with incremental updates: each flip is a union/split operation. \(O(\alpha(mn))\) per flip. Connects to LC 305 Number of Islands II.
   2. What if you needed the area of the largest island? (stress-tests: count vs area) Track size during each flood fill. Return the maximum. Connects to LC 695.
   3. What if the grid wrapped around (toroidal)? (stress-tests: bounded grid) Use modular arithmetic for coordinates: nr = (r + dr) % ROWS, nc = (c + dc) % COLS.
   4. What if you could flip at most one water cell to land and wanted the largest island? (stress-tests: no modification) For each water cell, compute the sum of adjacent island sizes. Precompute island sizes with unique IDs. Connects to LC 827 Making A Large Island.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Number of Islands generated via batch canonical enrichment pass.
   

3. Number of Provinces (547)

   We can choose to solve this in 2 ways: a union find approach or a bfs-based flood fill approach for connectivity tracking.

   Here’s a BFS approach, which is more performant, easier to reason with and easier to implement:

   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 findCircleNum(self, isConnected: List[List[int]]) -> int: """ We can do a connectivity traversal using a BFS flood fill approach, then we can just count the number of islands / provinces. """ n = len(isConnected) provinces = 0 visited = [0] * n # 0: univisited, 1: visited # now we run the BFS originating from any unvisited: for i in range(n): if not visited[i]: provinces += 1 queue = deque([i]) visited[i] = 1 while queue: node = queue.popleft() for nei in (nei for nei in range(n) if isConnected[node][nei] and not visited[nei]): queue.append(nei) visited[nei] = 1 return provinces

   Code Snippet 5: BFS solution, simple, more performant

   Here’s the union find approach, it’s a little harder to implement:

   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

   class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: """ We have to just do union find and get the total number of unique parents / roots. isConnected is about direct connections. This means direct edges between them. We can get started. """ n = len(isConnected) parent = list(range(n)) rank = [0] * n def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x, y): """ Only side-effects matter for us here, that's why we choose to return nothing """ rx, ry = find(x), find(y) if rank[rx] < rank[ry]: parent[rx] = ry elif rank[ry] < rank[rx]: parent[ry] = rx else: parent[ry] = rx rank[rx] += 1 for a in range(n): for b in range(a + 1, n): if isConnected[a][b]: union(a, b) return len({find(x) for x in range(n)})

   Code Snippet 6: Union-find solution
   Pattern Extraction

   Core Insight: Connected component counting on an adjacency matrix. BFS/DFS from each unvisited node, or Union-Find. Count the number of components. Pattern Name: Connected Component Counting Canonical Section: Graphs > BFS/DFS on Adjacency Matrix Recognition Signals:

   • “How many connected components?”
   • Adjacency matrix (not grid)
   • Each component = one province/group

   Anti-Signals:

   • Grid-based connectivity – Number of Islands (LC 200)
   • Need component sizes, not count – track sizes during traversal

   Decision Point: Adjacency matrix + component counting = DFS/BFS per unvisited node, or Union-Find. Same pattern as Number of Islands but on a graph, not a grid.

   Pitfalls and Misconceptions

   1. Trap: Confusing adjacency matrix with grid. Treating isConnected[i][j] as a cell value rather than an edge. Why: isConnected[i][j] = 1 means cities \(i\) and \(j\) are directly connected. It’s NOT a grid cell. Correction: Iterate over cities (rows), not cells. For city \(i\), its neighbours are all \(j\) where isConnected[i][j] = 1.
   Problem Mutations

   1. What if you needed the largest province? (stress-tests: count vs size) Track component sizes during traversal. Return the maximum.
   2. What if connections could be added dynamically? (stress-tests: static) Union-Find with incremental union operations. Recompute count after each union.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Number of Provinces.
   

4. Max Area of Island (695) This is just accumulating statistics on a flood fill approach to traversing islands.

   There’s a bunch of ways we can do this: flood fill (BFS/DFS) or via a union find.

   BFS is my favourite approach in general.

   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

   # M1: FLOOD FILL BFS from collections import deque class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: if not grid or not grid[0]: return 0 area = 0 ROWS, COLS = len(grid), len(grid[0]) directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] for r in range(ROWS): for c in range(COLS): if grid[r][c] == 1: # we start a BFS for more land-cells. curr_area = 0 # use as root and carry on: queue = deque([(r, c)]) grid[r][c] = 0 # space hack: use the input and mark as visited curr_area += 1 while queue: r, c = queue.popleft() valid_children = ( (r + dr, c + dc) for dr, dc in directions if 0 <= r + dr < ROWS and 0 <= c + dc < COLS and grid[r + dr][c + dc] == 1 ) for child_row, child_col in valid_children: # update accumulators (curr_area, visited) before adding to the queue grid[child_row][child_col] = 0 curr_area += 1 # enqueue queue.append((child_row, child_col)) area = max(area, curr_area) # helps us find the biggest island in the grid return area

   Code Snippet 7: BFS Flood-fill approach

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

   class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: max_area = 0 rows, cols = len(grid), len(grid[0]) for r in range(rows): for c in range(cols): if grid[r][c] == 1: stack = [(r, c)] grid[r][c] = 0 area = 1 # local area, for this island's measure while stack: cr, cc = stack.pop() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = cr+dr, cc+dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1: grid[nr][nc] = 0 stack.append((nr, nc)) area += 1 max_area = max(max_area, area) return max_area

   Code Snippet 8: Flood-fill approach, implemented using DFS

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

   class DSU: def __init__(self): self.parent = {} self.size = {} # same concept as rank, we use a dict here because the keys will be coordinate tuples def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): """ Return value here doesn't matter, we care about the side-effect only, that's why we return nothing. """ xr, yr = self.find(x), self.find(y) if xr != yr: self.parent[xr] = yr self.size[yr] += self.size[xr] def add(self, x): if x not in self.parent: self.parent[x] = x self.size[x] = 1 # Inside solution, union adjacent '1' cells as you read the grid, # then return max(dsu.size.values()) as the answer if any, else 0.

   Code Snippet 9: Union find approach, ill-fitted and complex for this solution but it will work
   Pattern Extraction

   Core Insight: Grid flood fill, same as Number of Islands, but track the size of each connected component. Return the maximum size. Pattern Name: Grid Flood Fill with Size Tracking Canonical Section: Graphs > BFS/DFS on Grids Recognition Signals:

   • 2D grid with land/water
   • “Maximum area” of any island
   • Same as Number of Islands but optimise for area instead of count

   Anti-Signals:

   • Need count of islands, not area – don’t track size, just count initiations

   Decision Point: Same algorithm as Number of Islands + size counter per flood fill.

   Pitfalls and Misconceptions

   1. Trap: Not counting the starting cell in the area. Why: Off-by-one: the BFS/DFS starts at the initial cell, which is part of the island. Correction: Initialise area = 1 (for the starting cell), or count all cells popped from the queue.
   Problem Mutations

   1. What if you could flip one water cell to land? (stress-tests: no modification) Precompute island sizes with unique IDs. For each water cell, sum adjacent island sizes + 1. Connects to LC 827.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Max Area of Island.
   

5. Flood Fill (733) This is pretty straightforward easy question, just need to know the early return case when the source is already coloured and there’s no need to colour anything (including neis)

   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 floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]: ROWS, COLS = len(image), len(image[0]) DIRS = [(0, 1), (0, -1), (-1, 0), (1, 0)] start_color = image[sr][sc] if start_color == color: return image queue = deque([(sr, sc)]) while queue: r, c = queue.popleft() image[r][c] = color for nr, nc in ( (r + dr, c + dc) for dr, dc in DIRS if (0 <= (r + dr) < ROWS) and (0 <= (c + dc) < COLS)): if image[nr][nc] != start_color: continue image[nr][nc] = color queue.append((nr, nc)) return image

   Code Snippet 10: BFS flood fill solution, with early return case if src is already correctly coloured
   Pattern Extraction

   Core Insight: BFS/DFS from the starting pixel, changing all connected pixels of the original colour to the new colour. Pattern Name: Grid BFS/DFS (Flood Fill) Canonical Section: Graphs > BFS/DFS on Grids Recognition Signals:

   • “Fill all connected same-colour pixels”
   • 4-directional adjacency
   • Change colour in-place

   Anti-Signals:

   • Need to fill a different shape (not connected region) – different algorithm

   Decision Point: The simplest grid traversal problem. Template for all grid BFS/DFS.

   Pitfalls and Misconceptions

   1. Trap: Not checking if the starting pixel already has the new colour. Why: If image[sr][sc] = newColor=, the fill would loop infinitely (no way to mark visited, since the colour doesn’t change). Correction: Early return if originalColor = newColor=.
   Problem Mutations

   1. What if the fill were bounded by a border colour? (stress-tests: same-colour connection) Different stopping condition: stop at the border colour instead of different colours.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Flood Fill.
   

6. Walls and Gates (??) (neetcode version)

   This is just distance tracking, we can go layer by layer and get things done. The aux ds (queue / stack) can hold tuples to keep track of parent height. Oh and it’s a multi-source BFS that happens at the same time. This is a case of multi-source BFS really. Nothing special here, we just need to write it in-place and have nothing to return.

   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 islandsAndTreasure(self, grid: List[List[int]]) -> None: if not grid: return queue = deque() ROWS, COLS = len(grid), len(grid[0]) DIRS = [(0, -1), (0, 1), (1, 0), (-1, 0)] INF = 2147483647 # 1: add all gates to queue at distance 0 (multiple source BFS, simultaneously run them) for r, c in ((r, c) for r in range(ROWS) for c in range(COLS) if grid[r][c] == 0): # is treasure: queue.append((r, c)) while queue: r, c = queue.popleft() candidates = ( (r + dr, c + dc) for dr, dc in DIRS if (0 <= r + dr < ROWS) and (0 <= c + dc < COLS) and grid[r + dr][c + dc] == INF) for row, col in candidates: grid[row][col] = grid[r][c] + 1 queue.append((row, col))

   Code Snippet 11: multi-source BFS with state tracking (distance metric)

   Extension:

   • if the cost of traversing an edge from node to its neighbors had a costs (positive) then we would have to consider doing some kinda of Dijkstra’s approach. In this case a simple BFS works perfectly.

7. Rotting Oranges (994) This is a time-simulation (metric tracking) of a flood-fill, where the current hop is the time elapsed.

   This is straightforward, we want to do multisource traversal (from each rotten orange) as a way of doing time-simulation and so we just use a simple BFS traversal. This also just keeps an accumulator aux value (fresh) collected via a pre-processing step for our ease.

   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 orangesRotting(self, grid: List[List[int]]) -> int: ROWS, COLS = len(grid), len(grid[0]) queue = deque() fresh = 0 # accumulate starts points for the BFS start as well as the aux variable, fresh for r in range(ROWS): for c in range(COLS): if grid[r][c] == 2: queue.append((r, c, 0)) elif grid[r][c] == 1: fresh += 1 time = 0 while queue: r, c, t = queue.popleft() 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] == 1: grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc, t+1)) time = t+1 return -1 if fresh > 0 else time

   Code Snippet 12: Simple BFS traversal and time-simulation as the metric tracking (hop count == time)
   Pattern Extraction

   Core Insight: Multi-source BFS from all initially rotten oranges simultaneously. Each BFS level = one minute. Track remaining fresh oranges. Pattern Name: Multi-Source BFS (Simultaneous Wavefront) Canonical Section: Graphs > BFS on Grids Recognition Signals:

   • “Minimum time for all to be affected” from multiple sources
   • Simultaneous spreading from multiple starting points
   • Level-by-level BFS where each level = one time unit

   Anti-Signals:

   • Single source – standard BFS
   • Different spreading speeds per source – Dijkstra

   Decision Point: Multi-source BFS initialises the queue with ALL sources before starting. Each level represents one time step. The time is the number of BFS levels.

   Pitfalls and Misconceptions

   1. Trap: Running separate BFS from each rotten orange. Why: Separate BFS doesn’t account for simultaneous spreading. Results in incorrect timing. Correction: Enqueue ALL rotten oranges at time 0. Process simultaneously.
   2. Trap: Not checking if fresh oranges remain after BFS. Why: Some fresh oranges may be unreachable (surrounded by empty cells). Return -1 if any remain. Correction: After BFS, if fresh_count > 0: return -1.
   Problem Mutations

   1. What if oranges rotted at different speeds? (stress-tests: uniform speed) Dijkstra with variable-weight edges. Connects to weighted shortest path.
   2. What if you could place one rotten orange optimally? (stress-tests: fixed sources) Try each fresh orange as an additional source. \(O(mn \cdot mn)\) brute force.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Rotting Oranges.
   

8. Pacific Atlantic Water Flow (417)

   This is a good reminder that traversal direction should be something that we should take a moment to think about before we start implementing. Here, we realise that the better approach is to go from outwards to in (instead of the actual flow of the water). This is similar to the point where we should consider simpler, complementary approaches to the problems.

   This is a reverse-reachability type. It’s also a multisource traversal!

   Also remember to mark things as visited ASAP so that we don’t introduce redundancies in the search space.

   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

   from collections import deque class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: # early returns for trivial edge case: if not heights or not heights[0]: return [] ROWS, COLS = len(heights), len(heights[0]) DIRS = [(-1,0), (1,0), (0,-1), (0,1)] def bfs(starts): visited = set(starts) queue = deque(starts) while queue: r, c = queue.popleft() # direct for loop is better (easier to read) than generator then for loop: for dr, dc in DIRS: nr, nc = r + dr, c + dc # is reachable coordinate: if ( 0 <= nr < ROWS and 0 <= nc < COLS and (nr, nc) not in visited and heights[nr][nc] >= heights[r][c] ): # mark as visited before enqueing! visited.add((nr, nc)) queue.append((nr, nc)) return visited pacific_starts = [(0, c) for c in range(COLS)] + [(r, 0) for r in range(ROWS)] atlantic_starts = [(ROWS-1, c) for c in range(COLS)] + [(r, COLS-1) for r in range(ROWS)] pacific_reach = bfs(pacific_starts) atlantic_reach = bfs(atlantic_starts) return [ [r, c] for r, c in (pacific_reach & atlantic_reach) ]

   Code Snippet 13: BFS approach to reverse-reachability
   Pattern Extraction

   Core Insight: Reverse the flow: BFS/DFS from ocean borders inward. Cells reachable from the Pacific border can flow to Pacific; same for Atlantic. Answer = intersection of both reachable sets. Pattern Name: Reverse BFS/DFS from Boundaries Canonical Section: Graphs > BFS/DFS on Grids Recognition Signals:

   • “Water flows from high to low” with two targets (oceans)
   • Forward flow analysis is \(O(mn \cdot mn)\). Reverse from boundaries is \(O(mn)\).
   • Two separate reachability sets, answer = intersection

   Anti-Signals:

   • Single ocean – one BFS pass suffices
   • Water flows UP (not down) – reverse the comparison

   Decision Point: The reverse-flow insight is the key: instead of “from each cell, can water reach the ocean?” ask “from the ocean, which cells can be reached by flowing uphill?”

   Pitfalls and Misconceptions

   1. Trap: Forward BFS from each cell to check if it reaches both oceans (\(O(m^2 n^2)\)). Why: Redundant work. Each cell is checked independently. Correction: Two reverse BFS passes: one from Pacific border, one from Atlantic border. Intersect results.
   2. Trap: Getting the height comparison backwards in the reverse flow. Why: Reverse flow goes from lower to higher (water flows downhill, so reverse = uphill). Correction: if heights[nr][nc] > heights[r][c]= (can flow FROM (nr,nc) TO (r,c) in the original direction, so in reverse, we move to (nr,nc) if it’s \(\geq\) current).
   Problem Mutations

   1. What if there were three oceans? (stress-tests: two oceans) Three BFS passes, triple intersection. Same approach, more sets.
   2. What if heights could change dynamically? (stress-tests: static grid) Re-run both BFS passes after each change. No efficient incremental approach without specialized data structures.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Pacific Atlantic Water Flow.
   

9. Surrounded Regions (130)

   This one is about creating temporary marks as we navigate then restoring thing as part of a formatting step.

   This is also a reverse-reachability type of question because we actually find the inverse (safe cells) that we can reach from the border cells since these safe cells won’t be converted. This will help us find the actual unsafe cells that we will convert.

   NOTE: this question has terrible phrasing.

   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

   from collections import deque from typing import List class Solution: def solve(self, board: List[List[str]]) -> None: if not board or not board[0]: return ROWS, COLS = len(board), len(board[0]) DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)] def get_border_o_positions(): """ Returns a set of coordinates for all the Os that are at the borders """ # All 'O's on the border (first/last row or column) top_bottom = ((row, col) for col in range(COLS) for row in (0, ROWS-1) if board[row][col] == 'O') left_right = ((row, col) for row in range(ROWS) for col in (0, COLS-1) if board[row][col] == 'O') return set(top_bottom) | set(left_right) def mark_border_connected_region_as_safe(): border_o_positions = get_border_o_positions() queue = deque() for r, c in border_o_positions: # mark as visited before enqueing the start coordinates: board[r][c] = '*' queue.append((r, c)) while 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 board[nr][nc] == 'O'): board[nr][nc] = '*' queue.append((nr, nc)) mark_border_connected_region_as_safe() # List comprehensions for postprocessing for r, c in ((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] == '*': board[r][c] = 'O'

   Code Snippet 14: reverse-reachability via BFS approach + reusing input space for intermediate working
   Pattern Extraction

   Core Insight: Reverse approach: instead of finding surrounded regions, find UN-surrounded regions (connected to the border). Mark border-connected O’s as safe, then flip all remaining O’s to X’s. Pattern Name: Boundary-Connected BFS/DFS with Complement Marking Canonical Section: Graphs > BFS/DFS on Grids Recognition Signals:

   • “Capture surrounded regions” = flip O’s to X’s unless connected to border
   • Inverse problem: easier to find what’s NOT captured

   Anti-Signals:

   • All regions captured (no border connection) – flip all O’s
   • Need to find the largest surrounded region – track sizes

   Decision Point: Start from border O’s, DFS inward marking as safe. Then sweep the grid: remaining O’s become X’s, safe marks become O’s.

   Pitfalls and Misconceptions

   1. Trap: Trying to identify surrounded regions directly. Why: Checking if a region is surrounded requires verifying no cell touches the border. The complement (border-connected) is easier. Correction: Start from border cells. Mark all border-connected O’s. Everything else is surrounded.
   2. Trap: Modifying the grid during the boundary DFS in a way that confuses the final sweep. Why: If you flip O’s to X’s during boundary DFS, you lose the safe markers. Correction: Mark safe cells with a temporary character (e.g., 'S'). Final sweep: 'S' -> 'O', 'O' -> 'X'.
   Problem Mutations

   1. What if the grid were 3D? (stress-tests: 2D) Same algorithm, 6-directional adjacency. Border cells are on any face of the 3D grid.
   2. What if you needed the count of captured cells? (stress-tests: transformation) Count remaining O’s after marking safe cells. Same algorithm, add a counter.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Surrounded Regions.
   

10. Minimum Jumps to Reach End via Prime Teleportation (3629)

    Pattern Extraction

    AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

    This dropdown was generated during coaching. Verify before integrating.
    

    Core Insight: BFS is straightforward for shortest-path problems, but adjacency queries can be expensive if computed on-the-fly. When adjacency is defined by a mathematical property (shared prime factor, divisibility), preprocess to build a lookup structure, trading space for speed. This transforms expensive per-query computation into O(1) lookups.

    Pattern Name: BFS with Preprocessed Adjacency Lookup (variant: prime-factorization-based state-space augmentation)

    Canonical Section: BFS / Graph Traversal family; related to “state-space augmentation for adjacency acceleration” (cf. LC 127 Word Ladder). Subclass: mathematical-property-defined adjacency.

    Recognition Signals:

    • “Shortest path / minimum hops” with adjacency defined by a mathematical rule (shares prime factor, divisibility, modular arithmetic, etc.)
    • Naive adjacency query is expensive: requires factorization, GCD computation, or scanning all indices
    • Numbers are bounded (max_val is known), enabling preprocessing like sieving
    • Constraint bounds (n ≤ 10^5, max_val ≤ 10^6) suggest preprocessing upfront, not per-query

    Anti-Signals:

    • Simple grid-based BFS where adjacency is local neighbors — precompute nothing; compute on-the-fly
    • All edges given explicitly as edge list — no mathematical pattern to exploit; build adjacency directly
    • Need the actual path reconstruction with complex constraints — preprocessing may complicate bookkeeping
    • Undirected version where asymmetry doesn’t matter — may not need prime tracking

    Decision Point: Does preprocessing enable O(1) or O(log n) adjacency lookups? If yes, commit to sieve + factorization + lookup map. If no, question whether preprocessing is the right move. The pattern works when the preprocessing cost (O(max_val log log max_val) for sieve + O(n sqrt(max_val)) for factorization) is dominated by the BFS savings (O(n) with O(1) lookups instead of O(n²) with O(n) per-step lookups).

    Interviewer Comms: “This is shortest-path BFS, but adjacency is defined by prime factors: from index i, I can jump to any index j where nums[i] and nums[j] satisfy the teleportation rule (in this problem, nums[i] is prime and divides nums[j]). Computing adjacency naively would be expensive. I’ll preprocess: sieve for O(1) prime checks, factorize each number once, build a lookup map from primes to indices where they divide the number. Then BFS queries the map for O(1) neighbor discovery.”

    Pitfalls and Misconceptions

    AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

    This dropdown was generated during coaching. Verify before integrating.
    

    1. Trap: Checking if nums[idx] is prime on-the-fly during BFS instead of precomputing with a sieve. Why: primality testing naively is O(sqrt(num)) per check. If you do this for every BFS step, you pay this cost repeatedly, dominating the BFS itself (which should be O(n)). Correction: Sieve once upfront (O(max_val log log max_val)), then is_prime is O(1) forever after.

    2. Trap: Computing prime factors every time you need adjacency instead of factorizing each number once during preprocessing. Why: factorization is expensive (O(sqrt(num)) per number). Doing it repeatedly in the BFS loop multiplies this cost. Correction: Factorize each unique value in nums once during setup, store results in a structure (or compute on-first-encounter with memoization), then reuse from the lookup map.

    3. Trap: Building prime_to_indices map but then iterating all indices to check for neighbors instead of using the map during BFS. Why: you’ve paid the preprocessing cost but then throw away the speedup by doing O(n) work per BFS step anyway. Correction: Use the map directly: `for prime in prime_factors(nums[idx]): for neighbor_idx in prime_to_indices[prime]: …` or equivalent, achieving O(1) per prime.

    4. Trap: Forgetting visited_prime or tracking it incorrectly. Without it, the same prime value could trigger teleportation lookups multiple times from different indices that have it as a factor. Why: a prime p might appear in nums[2] and nums[5]. Without visited_prime, you’d process prime_to_indices[p] twice. Correction: Track which primes have already been used for teleportation; skip re-processing them. Semantically: “once I’ve visited all indices reachable via prime p, I don’t need to check p again.”

    5. Trap: Prime factorization logic error: checking all integers instead of just primes, off-by-one on the sqrt boundary, or not handling large prime factors. Why: incorrect factorization breaks the adjacency map entirely. Correction: Only check integers up to sqrt(num), and only if they’re prime (use sieve). After the loop, if remainder > 1, it’s also prime. Pseudo-code: `for i in range(2, sqrt(num)+1): if is_prime[i] and num % i = 0: factors.add(i); num // i (repeatedly). If num > 1: factors.add(num)`.

    Problem Mutations

    AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

    This dropdown was generated during coaching. Verify before integrating.
    

    1. What if the teleportation rule were “jump to any index sharing ANY prime factor” instead of “only if nums[idx] is prime”? (tests: generality of preprocessing) Then you iterate all prime factors of nums[idx], not just check if it’s prime. Preprocessing remains the same (sieve, factorize, build map). BFS logic becomes: `for f in prime_factors(nums[idx]): for nei in prime_to_indices[f]: …`. Complexity unchanged; just more looser in what you can reach.

    2. What if max_val were 10^9 and sieving became infeasible (memory blow-up)? (tests: scalability of preprocessing) Sieve is now impossible. Instead, factorize on-the-fly with memoization: compute prime factors for each unique value the first time, cache result, reuse. Complexity is O(n sqrt(max_val)) instead of O(max_val log log max_val), but avoids O(10^9) space. Trade-off: time for space.

    3. What if you needed to return the actual path of jumps (sequence of indices), not just the minimum count? (tests: reconstruction) Add parent pointers during BFS: `parent[nei] = (idx, prime_used)` or just `parent[nei] = idx`. When you reach the end, backtrack: `path = []; curr = n-1; while curr != 0: path.append(curr); curr = parent[curr]; path.reverse()`. BFS logic unchanged; output enrichment only.

    4. What if different jump types had different costs (e.g., adjacent jump costs 1, teleport costs 2)? (tests: optimization criterion) Use Dijkstra’s algorithm instead of BFS. The queue becomes a min-heap (by cost). Preprocessing remains unchanged. Complexity becomes O((n + e) log n) where e is total edges. The structure of the solution (sieve, factorization, map) survives; only the traversal changes.

    5. What if the array were dynamic (values updated online, new elements added)? (tests: static vs. online) Preprocessing becomes per-update, not once upfront. On each update, recompute prime factors for the changed element, update prime_to_indices accordingly. Without persistent data structures, this is O(sqrt(num)) per update. The BFS itself doesn’t change; the preprocessing is now amortised per-query.

    Main idea is that we need to do a bunch of preprocessing to make the BFS efficient. The idea therefore is to do both prime sieving AND keeping track of prime factors.

    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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

    from math import sqrt class Solution: def minJumps(self, nums: List[int]) -> int: n = len(nums) max_val = max(nums) # preproc 1: prime numbers within limit def sieve(limit): """ Returns a list of prime numbers within limit (inclusive) """ is_prime = [True] * (limit + 1) # effectively makes this 1-indexed is_prime[0], is_prime[1] = False, False # remember we only need to do till sqrt of the limit for num in range(2, int(sqrt(limit) + 1)): if is_prime[num]: # negate its multiples: for j in range(num * num, limit + 1, num): is_prime[j] = False return is_prime is_prime = sieve(max_val) # is the reference prime-sieve # prime factorization with cached prime check: def prime_factors(num): """ Returns a set of prime factors for a number: """ factors = set() temp = num # prime factorisation for i in range(2, int(sqrt(num)) + 1): if not is_prime[i]: continue while temp % i == 0: factors.add(i) temp //= i if temp == 1: break if temp > 1: # then temp is a prime too factors.add(temp) return factors # creates a map from prime factor to list of indices in nums with number divisible by that prime, these are the teleport indices prime_to_indices = defaultdict(list) for idx, num in enumerate(nums): factors = prime_factors(num) for f in factors: prime_to_indices[f].append(idx) # now we do the BFS with hop counting: visited = [False] * n visited[0] = True visited_prime = set() # track prime whose teleportations are visited q = deque([(0, 0)]) # (idx, hops) while q: idx, hops = q.popleft() # reached the end: if idx == n - 1: return hops # adjacent moves: for nei in [idx - 1, idx + 1]: if 0 <= nei < n and not visited[nei]: visited[nei] = True q.append((nei, hops + 1)) # teleports: indices made available by prime val if prime and not visited that prime before num = nums[idx] if is_prime[num] and num not in visited_prime: visited_prime.add(num) for nei in prime_to_indices[num]: if not visited[nei]: visited[nei] = True q.append((nei, hops + 1)) return -1

    Code Snippet 15: BFS that is assisted by aux prime-sieve and prime factors map to supply candidates for neighbours

    In the solution above, the lookup map was the most important part that assists the BFS — the rest of the things like prime factorisation, sieve of Eratosthenes just builds up to it.

    1 2 3 4 5 6

    # creates a map from prime factor to list of indices in nums with number divisible by that prime, these are the teleport indices prime_to_indices = defaultdict(list) for idx, num in enumerate(nums): factors = prime_factors(num) for f in factors: prime_to_indices[f].append(idx)

    Code Snippet 16: the prime to indices lookup map

Shortest Path (Unweighted Graph) #

• BFS-based shortest path finding in unweighted graphs (fixed cost).
• If there were costs involved then we could explore a Bellman-Ford / Dijkstra’s approach.

Problems #

1. Word Ladder (127)⭐️

   Pattern Extraction

   Pattern Name: State-Space Augmentation for Adjacency Acceleration Canonical section: Create or extend graph-state-space-transformations if it doesn’t exist.

   Recognition signals:

   • Direct adjacency is expensive (O(N²), O(N·W), etc.)
   • Nodes can be grouped by a common property (pattern, hash, range, etc.)
   • You can create an intermediate layer that clusters nodes.
   • Graph is static (no online updates needed).

   Anti-signals (when NOT to use this):

   • Edges are already cheap to compute.
   • The intermediate layer would be too large (defeats purpose).
   • You need to query online (the augmented structure is a one-time build).
   • State space is already implicit or pre-indexed.

   Generalisation: This pattern appears in:

   • Word Ladder (pattern lookup for neighbors)
   • Alien Dictionary (graph construction via sorted order)
   • N-Sum (two-pointer + sorted structure)
   • Stock DP (state compression via valid-prior-states lookup)

   The meta-pattern: transform the problem’s natural adjacency into a faster, intermediate representation.

   Problem Mutations, extensions

   1. What if words could be any length? (variable L)
      1. Pattern generation still works, but \(O(L·N)\) scaling becomes more critical. Bidirectional BFS becomes necessary.
   2. What if the graph were directed? (e.g., “hot” → “cot” allowed, but “cot” → “hot” not allowed)
      1. BFS still works; visited set still works; pattern silencing still works. The algorithm is robust.
   3. What if we needed to return the actual path, not just length?
      1. Track parent pointers during BFS, then backtrack from endWord. Pattern silencing complicates this (you’d lose parent chains), so you’d either skip silencing or track parents in a separate structure.
   4. What if the problem were online? (new words added during traversal)
      1. Silencing breaks. You’d need to rebuild pattern_to_words dynamically or skip the optimization.

   While originally, this feels like some sort of edit-distance DP problem, we realise that it’s a graph traversal of configurations.

   We need to modify the state space to represent the configurations and then traverse through that state space. So the main part of this question is about how that modification / augmenting of the graph is done.

   We need to be able to use wildcards and we can create a lookup table for pattern to words. This lookup table is something we can build by replacing each character in a word with * and mapping those patterns to possible words. This improves our adjacency lookup (from \(O(N^{2})\) to \(O(L N)\), where \(L\) is the word-length).

   In our traversal, we wish to reach each node (pattern) once in the overall procedure, so there has to be an easy way for us to silence it / mark it as visited upon reaching that node.

   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 defaultdict, deque class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 L = len(beginWord) # better mapping, this is our custom lookup: pattern_to_words = defaultdict(list) for word in wordList: for i in range(L): pattern = word[:i] + "*" + word[i + 1:] pattern_to_words[pattern].append(word) # now we run BFS: queue = deque([(beginWord, 1)]) # word, level visited = {beginWord} while queue: word, level = queue.popleft() for i in range(L): pattern = word[:i] + "*" + word[i + 1:] for nei in pattern_to_words[pattern]: if nei == endWord: return level + 1 if nei not in visited: visited.add(nei) queue.append((nei, level + 1)) # NB: prevents repeat lookups, we silence that pattern check so that each pattern is used only once per search. pattern_to_words[pattern] = [] return 0

   Code Snippet 17: Augmented lookup map for neis that assists BFS with distance tracking
   Pattern Extraction

   Core Insight: BFS in an implicit graph where nodes are words and edges connect words differing by one character. BFS gives the shortest transformation sequence. Pattern Name: BFS on Implicit Word Graph Canonical Section: Graphs > Shortest Path (Unweighted) Recognition Signals:

   • “Shortest transformation sequence” between two words
   • Each step changes exactly one character
   • Unweighted implicit graph (BFS for shortest path)

   Anti-Signals:

   • Need ALL shortest paths – BFS + backtracking. Connects to LC 126
   • Transformation can change multiple characters – different problem

   Decision Point: Unweighted shortest path = BFS. The key optimisation is how you generate neighbours: for each position, try all 26 characters and check dictionary membership, rather than comparing against all words in the dictionary. Interviewer Comms: “I model this as BFS on an implicit graph. Each word is a node; edges connect words differing by one character. I generate neighbours by trying all 26 substitutions at each position, checking if the result is in the word set. BFS gives the shortest path length. \(O(M^2 \cdot N)\) where \(M\) = word length, \(N\) = dictionary size.”

   Pitfalls and Misconceptions

   1. Trap: Generating neighbours by comparing against every word in the dictionary. Why: \(O(N \cdot M)\) per word, \(O(N^2 \cdot M)\) total. For large dictionaries, this is too slow. Correction: For each position, try all 26 characters: \(O(26 \cdot M)\) per word. Check membership in a set: \(O(M)\) per check.
   2. Trap: Not removing words from the dictionary after visiting them. Why: Without removal, the BFS revisits words, potentially cycling. Correction: Remove visited words from the word set (or use a separate visited set).
   3. Trap: Using DFS instead of BFS. Why: DFS doesn’t guarantee shortest path. BFS does. Correction: Always BFS for shortest path in unweighted graphs.
   Problem Mutations

   1. What if you needed ALL shortest paths? (stress-tests: single shortest) BFS to build the level graph, then DFS/backtracking to enumerate all shortest paths. Connects to LC 126 Word Ladder II.
   2. What if transformations could change up to \(k\) characters per step? (stress-tests: single character) Graph structure changes: edges connect words within Hamming distance \(k\). BFS still works but neighbour generation is more complex.
   3. What if the dictionary were very large (\(10^5\) words)? (stress-tests: moderate dictionary) Bidirectional BFS: start from both beginWord and endWord, meet in the middle. Reduces search space from \(O(b^d)\) to \(O(b^{d/2})\).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Word Ladder.
   

Topological Sort & Cycle Detection #

• Detect cycles in directed or undirected graphs and generate valid node orderings in DAGs

Problems #

1. Course Schedule (207)

   We realise that we just need to return feasibility, so it’s a simpler problem than asking for the actual topo-order. The problem is just about cycle detection.

   This is a simpler version of the problem that just expects a boolean return on whether we can do a topo sort (i.e. whether it’s a DAG).

   There’s 2 ways to do this: graph colouring (to ensure no cycles) or just straight up doing kahn’s algo to attempt a topo sort and determine how many got handled:

   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 Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # list of lists, access using relative idx adj = [[] for _ in range(numCourses)] # careful: we are ultimately trying to clear the topo sort, so we are building edge from a -> b if a is a prereq of b for course, pre in prerequisites: adj[pre].append(course) # single visited with 3 states, space optimisation! visited = [0] * numCourses # 0 = unvisited, 1 = visiting, 2 = visited def dfs(node): if visited[node] == 1: # Cycle! return False if visited[node] == 2: # done state, can return early return True visited[node] = 1 for nei in adj[node]: if not dfs(nei): return False visited[node] = 2 return True for i in range(numCourses): if not dfs(i): return False return True

   Code Snippet 18: Graph Coloring via DFS (3-color graph) for Cycle-Detection \(O(V + E)\) time, \(O(V)\) space

   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 defaultdict, deque class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # Build adjacency list and in-degree array adj = defaultdict(list) # in-degree: For each node, count how many edges point to it = how many prerequisites it has. in_degree = [0] * numCourses for course, pre in prerequisites: adj[pre].append(course) # prereq → course (edge creation) in_degree[course] += 1 # course needs one more prereq # 1. Find all courses with no prerequisites. Any element in the queue is "ready to be taken" queue = deque(i for i in range(numCourses) if in_degree[i] == 0) visited = 0 # How many courses we've "finished" # 2. Process all courses "ready" to be taken while queue: node = queue.popleft() # count as finished / visited visited += 1 for neighbor in adj[node]: # All courses that depend on this one in_degree[neighbor] -= 1 # One prereq is now done! if in_degree[neighbor] == 0: # this neighbor is not ready to be taken queue.append(neighbor) # 3. If we managed to "take" all courses, there is no cycle! return visited == numCourses

   Code Snippet 19: Kahn's Algo for Topo-sorting, used for cycle-checks
   problem mutations and extensions

   1. What if we needed to return an actual topo order?
      • DFS: collect nodes on state transition to 2 (post-order)
      • Kahn’s: track processing order in queue
      • Kahn’s is cleaner here.
   2. What if the graph were undirected?
      • DFS coloring breaks (no concept of “back edge” in undirected; cycle = any revisit)
      • Use Union-Find instead
      • OR: simplify DFS to binary visited
   3. What if we had \(10^6\) courses and \(10^7\) prerequisites?
      • Adjacency list is essential (matrix would OOM)
      • Both DFS and Kahn’s would be \(O(V + E) \approx 10^7\), acceptable
   4. What if we queried “is course A a prerequisite of course B” repeatedly?
      • Adjacency matrix gives O(1) query
      • Adjacency list + BFS gives O(V + E) per query
      • Trade-off: build matrix on first query, or use set-based adj list
   5. What if we had online updates? (add/remove prerequisites dynamically)
      • DFS: rebuild entire coloring on each update (O(V + E) per update)
      • Kahn’s: rebuild in-degree array (O(V + E) per update)
      • Union-Find (for undirected) can detect cycle on insertion in O(α(V)) amortised
      • Hint for the future: topological sort problems don’t handle online updates well
   Pattern Extraction

   Core Insight: Cycle detection in a DAG is the inverse of topological sort feasibility — if you can topologically sort, no cycle exists. Equivalently: a directed graph is a DAG iff every node is either unvisited, in the current recursion path (visiting), or fully processed (visited). A cycle manifests as a back edge: an edge to a node in the current path.

   Pattern Name: DAG Cycle Detection via Graph Coloring (DFS variant) or Topological Feasibility Check (Kahn’s variant)

   Canonical Section: Cycle Detection family → Directed Graphs subclass; OR Topological Sort family → Cycle Detection application

   Recognition Signals:

   • “Can we complete all tasks respecting dependencies?” or “Is it possible to order nodes respecting edges?” → topological sort problem
   • Boolean return only (“yes cycle” / “no cycle”) → direct cycle detection is sufficient; don’t overthink order reconstruction
   • Directed graph + acyclicity question → graph coloring or Kahn’s feasibility
   • Prerequisites / task dependencies / course ordering → directed graph with implicit topological constraint

   Anti-Signals:

   • Undirected graph + cycle detection → Union-Find is the canonical choice (back-edge concept differs; DFS coloring would falsely trigger on reverse edges or require binary visited, losing efficiency)
   • Need the actual topological order as output → DFS post-order or Kahn’s tracking (though Kahn’s is cleaner for reconstruction)
   • Online updates (add/remove edges dynamically) → Union-Find is O(α(n)) amortised per insertion; DFS/Kahn’s require full rebuild (O(V+E) per update), making them prohibitively expensive for online cycle detection

   Decision Point: DFS coloring vs Kahn’s. DFS coloring directly detects back edges via state machine (state 1 = in current recursion path → back edge found). Kahn’s topologically sorts and returns true iff all V nodes processed. Both are O(V+E) time and O(V) space. DFS coloring is slightly more elegant and direct for boolean-only return. Kahn’s is slightly safer in interviews (fewer state variables, more straightforward to explain). Neither is objectively better; pick based on comfort and interview momentum. The discriminator is usually: “Do I need the actual order?” → use Kahn’s and track order. “Just feasibility?” → either works; DFS coloring is often faster to code.

   Interviewer Comms: “I need to detect whether there’s a cycle in a directed graph of prerequisites. I’ll use DFS with a three-color state system: 0 (unvisited), 1 (currently visiting, in the recursion stack), 2 (fully visited, done with this subtree). If I ever encounter a node in state 1, that’s a back edge — a cycle. I’ll call DFS from every unvisited node. If any returns false, the graph has a cycle. If all complete, it’s a DAG.”

   Pitfalls and Misconceptions

   1. Trap: Using binary visited (0/1) instead of 3-color state in DFS coloring. Why: Binary visited can’t distinguish between “I’m currently processing this node in the current DFS path” (which indicates a back edge) and “I’ve already finished this node in a previous DFS call” (which is safe to skip). You’d either falsely detect cycles or miss real ones. Correction: Use three states: 0 (unvisited), 1 (visiting, in current path), 2 (finished). Cycle detection happens exactly when you encounter state 1.

   2. Trap: Building the adjacency list backwards: course → prerequisite instead of prerequisite → course. Why: If you reverse the direction, DFS traverses things that depend on the current node, not things the current node depends on. This inverts the cycle detection and produces incorrect results. Correction: If course A is a prerequisite of course B, add edge A → B. DFS then correctly explores the dependency chain: starting from A, we visit everything that depends on A (transitively).

   3. Trap: Forgetting to check visited == numCourses at the end of Kahn’s algorithm. Why: Kahn’s processes all sources (in-degree 0) and their dependent nodes. If a cycle exists, some nodes are trapped and never reach in-degree 0. If you don’t verify that all V nodes were processed, you’ll return True for graphs with cycles. Correction: Always check: return visited == numCourses. This is the lynch-pin that converts “topological sort attempt” into “cycle detection.”

   4. Trap: Omitting the early-return check for visited[node] == 2 in DFS coloring. Why: Without this, you re-traverse finished subtrees multiple times. The algorithm degrades from O(V+E) to O(V²) in worst case (dense graph or long chains). Correction: After transitioning a node to state 2 (finished), skip it entirely on future DFS calls. This memoization is critical for efficiency.

   5. Trap: Building the adjacency list with an adjacency matrix instead of an adjacency list (for large V and sparse E). Why: Adjacency matrix is O(V²) space. For V = 2000, that’s 4M entries. For V = 10^6, it’s 10^12 space (OOM). Your graph is sparse (E ≤ 5000 or E ≈ V), so the matrix is wasteful. Correction: Always use adjacency list (list of lists or defaultdict) for sparse graphs. Only use matrix when E ≈ V² and you need O(1) edge-existence queries.

   Problem Mutations

   1. What if we needed to return an actual topological order (not just boolean)? (tests: return-value scope, tracking order vs. just detection)

      • DFS: collect nodes during post-order traversal (when marking state 2), then reverse. Slightly awkward.
      • Kahn’s: nodes dequeued in topological order; track order directly. Cleaner.
      • Verdict: Kahn’s is superior when output is required. DFS coloring is purpose-built for boolean detection only.

   2. What if the graph were undirected? (tests: concept of “back edge,” detection mechanism)

      • DFS coloring breaks: undirected edges create reverse edges automatically, which falsely look like cycles under the “back edge to state 1” rule.
      • Use Union-Find: insert edges one-by-one; if both endpoints are in the same connected component, cycle detected.
      • OR: use binary DFS (0/1 visited), but this loses efficiency and doesn’t generalize to directed graphs.
      • Verdict: Undirected cycle detection is a different canonical pattern (Union-Find is the primary).

   3. What if we had 10^6 courses and 10^7 prerequisites? (tests: space and time scalability, data structure necessity)

      • Complexity: Both algorithms remain O(V + E) ≈ 10^7 operations (acceptable).
      • Space: Adjacency matrix would require 10^12 space (OOM); adjacency list is essential (only stores actual edges).
      • DFS stack depth: O(V) worst case (linear dependency chain). For V = 10^6, this is tight but acceptable.
      • Verdict: Adjacency list is non-negotiable. DFS and Kahn’s scale equally well.

   4. What if we repeatedly queried “is course A a prerequisite of course B?” (tests: trade-off between preprocessing cost and per-query cost)

      • Adjacency matrix: O(V²) space upfront, O(1) per query (prohibitive space for large V).
      • Adjacency list + reachability: O(V + E) per query (expensive if many queries).
      • Practical trade-off: build a set-based adjacency list for O(1) edge checks (add O(E) space to store sets), or precompute reachability matrix (Floyd-Warshall, O(V³) time).
      • Verdict: For a single boolean check, adjacency list is optimal. For repeated queries, consider preprocessing.

   5. What if we had online updates (add/remove prerequisites dynamically)? (tests: amortized complexity, viability of static preprocessing)

      • DFS/Kahn’s: both rebuild the entire state on each update (O(V + E) per update). Expensive and impractical for frequent updates.
      • Union-Find: detects cycle on insertion in O(α(V)) amortised (vastly superior for online).
      • Verdict: Topological sort problems are inherently static/offline. Online cycle detection in directed graphs prefers Union-Find (or other incremental data structures). This is a strong signal that the problem context matters: if updates are possible, reconsider the algorithm choice.

2. Course Schedule II (210)

   This is a natural extension where we need to generate the actual topologically sorted array of nodes. Similarly, we can use Kahn’s Algo or do a DFS-based graph colouring for our purpose (just do a post-order inclusion). For the DFS approach, remember that the way we choose to mark visited will end up affecting whether or not we might need to reverse the schedule. I just prefer that Kahn’s Algo.

   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

   from collections import defaultdict class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: adj = defaultdict(list) indegree = [0] * numCourses # calculate the indegrees: for course, pre in prerequisites: adj[pre].append(course) indegree[course]+= 1 # find no prereqs: # ready-queue queue = deque([course for course in range(numCourses) if indegree[course] == 0]) schedule = [] # NB: we can use the length of this as "num visited" to check for cycle, no aux counter variable necessary. while queue: node = queue.popleft() schedule.append(node) for neighbor in adj[node]: indegree[neighbor] -= 1 # neighbour ready to be taken: if indegree[neighbor] == 0: queue.append(neighbor) # if cycle found: if not len(schedule) == numCourses: return [] return schedule

   Code Snippet 20: Kahn's Algo to generate topo-sorting

   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 Solution: def findOrder(self, numCourses, prerequisites): # Preprep: # NOTE: maps prereq -> course adj = [[] for _ in range(numCourses)] for course, pre in prerequisites: adj[pre].append(course) state = [0] * numCourses # 0=unvisited, 1=visiting, 2=visited order = [] def dfs(node): # detected cycle in the same round! if state[node] == 1: return False if state[node] == 2: return True # mark new as visiting: state[node] = 1 for nei in adj[node]: # explore depth in neighbours: if not dfs(nei): return False # finally, mark as visited -- this node is ready to be taken state[node] = 2 # mark this course as taken order.append(node) return True for i in range(numCourses): # if unvisited: if state[i] == 0: if not dfs(i): return [] return order[::-1] # remember to reverse because it's a postorder accumulation that we have done here.

   Code Snippet 21: DFS-graph coloring to generate Topo sorting
   Pattern Extraction

   AI usage disclosure AI tool · rubber-ducking of arguments

   This dropdown was generated during coaching. Verify before integrating.
   

   Core Insight: Topological sort is not a single algorithm; it’s a constraint satisfaction problem with two natural solution orientations. Kahn’s processes nodes in reverse-dependency order (sources first), producing topo order directly. DFS explores depth-first, producing reverse-topo order naturally, requiring inversion. The choice is not about correctness but about which output orientation emerges with less friction.

   Pattern Name: Topological Sort with Order Reconstruction

   Canonical Section: Topological Sort family (or Advanced Graphs / Directed Acyclic Graphs)

   Recognition Signals:

   • “Give me a valid schedule” or “compute a valid ordering respecting dependencies”
   • Directed acyclic graph (prerequisites, build systems, task dependencies)
   • Must produce an explicit order (not just boolean feasibility)
   • Constraints often include “any valid order is acceptable” or specific optimization (earliest finish time)
   • Input size often V ≤ 2000, E ≤ 5000 (sparse); suggests adjacency list, not matrix

   Anti-Signals:

   • Only need boolean (is DAG possible?) → LC 207; simpler, no order reconstruction
   • Undirected graph → topological sort is not applicable (no partial order semantics)
   • Need all valid topological orders → NP-hard enumeration; use backtracking DFS
   • Weighted graph with task durations and critical path → AON (Activity-On-Node) scheduling; topo sort is a component, not the full solution

   Decision Point: Kahn’s vs. DFS. Kahn’s: iterative, processes sources first, topo order emerges naturally without reversal. DFS: recursive, explores depth-first, post-order collection naturally produces reverse-topo (requiring reversal). Kahn’s is simpler to explain in interviews; DFS is more flexible if you need to detect specific dependency chains as you traverse. Default to Kahn’s unless you’re already mid-DFS for another reason.

   Interviewer Comms: “This is a topological sort — I need a valid ordering of nodes that respects all edges. I’ll use Kahn’s algorithm: count in-degrees, start with nodes that have no prerequisites (in-degree 0), process them one-by-one, decrement in-degrees of dependent nodes, and add newly-ready nodes to the queue. The dequeue order is a valid topological sort. If the queue empties before I’ve processed all nodes, the graph has a cycle.”

   Pitfalls and Misconceptions

   AI usage disclosure AI tool · rubber-ducking of arguments

   This dropdown was generated during coaching. Verify before integrating.
   

   1. Trap: Forgetting to reverse the order in DFS-based topo sort. Appending nodes during post-order (after processing children) produces reverse-topological order. Why: In a DAG, if \(A \to B\), DFS recurses on B before appending B, then returns to A and appends A. Result: \([…, B, A]\) in the collected order, which is backwards. Correction: Either append during pre-order (before recursing, gives topo order directly) or reverse at the end (post-order is standard, so reverse). Kahn’s avoids this entirely by processing sources first.

   2. Trap: Collecting nodes at the wrong phase in DFS. Pre-order (before recursion) gives topo order directly; post-order (after recursion) gives reverse-topo and requires reversal. Why: Pre-order visits a node before its dependencies are resolved (in the DFS tree, not the original graph). Post-order visits a node after its subtree is done, which corresponds to reverse-dependency order on a DAG. Correction: If you append during post-order (standard for DAG topo sort), reverse at the end. Kahn’s sidesteps this by not using recursion order at all.

   3. Trap: Not checking for cycles before returning the order. A graph with a cycle has no valid topological sort. Why: Nodes in a cycle can never be scheduled (each is a prerequisite of something that depends on it). DFS and Kahn’s both detect cycles, but you must check before returning the order. Correction: Kahn’s: verify \(\text{len}(\text{schedule}) == \text{numCourses}\). DFS: verify all dfs calls return True (no early False). Return empty list if cycle detected.

   4. Trap: Confusing in-degree (how many prerequisites a node has) with out-degree (how many nodes depend on it). Building the adjacency list backwards breaks Kahn’s. Why: Kahn’s processes sources (in-degree 0), not sinks. If you build the graph as \(\text{course} \to \text{prerequisite}\) instead of \(\text{prerequisite} \to \text{course}\), in-degree becomes out-degree and the algorithm processes dependents first (wrong). Correction: If course depends on pre, add edge \(\text{pre} \to \text{course}\) and increment \(\text{in\_degree}[\text{course}]\).

   5. Trap: Using a priority queue or sorting instead of a plain queue in Kahn’s. This produces a specific topo order, not just any valid one. Why: The problem states “any valid topological order,” so order within the queue doesn’t matter for correctness. A priority queue imposes an additional constraint (lexicographic, for example), changing the output. Correction: Use a plain deque or list as a queue. If the problem specifies “lexicographically smallest order,” then use a priority queue and state this explicitly.

   Problem Mutations

   AI usage disclosure AI tool · rubber-ducking of arguments

   This dropdown was generated during coaching. Verify before integrating.
   

   1. What if you need to return all valid topological orders? (tests: enumeration vs. single-path) Kahn’s and DFS both give a single valid order. Enumerating all requires backtracking DFS: at each step, try every node with current in-degree 0 (or state 0 in DFS), recurse, backtrack. Complexity becomes exponential. This shifts from topo sort to topo sort enumeration, a rare but harder problem.

   2. What if you must prioritize certain courses? (tests: constrained sorting) Kahn’s: pre-populate the queue with prioritized nodes (if they have in-degree 0), then add others. DFS: call dfs on prioritized nodes first in the main loop. Impact: same topo sort, but specific order chosen. Correctness unchanged.

   3. What if the graph is weighted (task durations) and you need earliest finish time? (tests: optimization layer) Add node weights. Kahn’s: as you dequeue node \(u\), propagate \(\text{finish}[v] = \max(\text{finish}[v], \text{finish}[u] + \text{weight}[u])\) to all dependents \(v\). This is AON (Activity-On-Node) scheduling; topo sort is a prerequisite, not the full algorithm.

   4. What if prerequisites are added or removed dynamically? (tests: static vs. online) Kahn’s and DFS both require full rebuild (\(O(V+E)\) per update). For true online cycle detection with incremental order updates, you’d need a dynamic graph data structure, rarely asked in interviews.

   5. What if you need the order to be lexicographically smallest? (tests: output specification) Kahn’s: use a priority queue (min-heap) instead of a deque. DFS: sort the adjacency lists or iterate children in order. Complexity becomes \(O((V+E) \log V)\) for Kahn’s. Correctness unchanged; topo sort is still valid, just a specific one.

3. Graph Valid Tree (??) (neetcode link)

   This is a traversal on an undirected graph to check if it’s a tree.

   We can use the basic math properties for early returns (n - 1 edges in a tree for a tree of n nodes).

   In this case, we also handle the undirected nature by splitting it into two directed edges (we also need to do the parent tracking for this!). This problem then just reduces to a simple cycle-check that we can do with DFS.

   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

   from collections import defaultdict class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: # optimisation: early return based on math: there should be n - 1 edges for a tree with n nodes if len(edges) != n - 1: return False # must be exact number of edges adj = defaultdict(list) for a, b in edges: adj[a].append(b) adj[b].append(a) visited = set() stack = [(0, -1)] # (current, parent) while stack: node, parent = stack.pop() if node in visited: return False # cycle detected visited.add(node) for nei in adj[node]: if nei == parent: continue # don't backtrack stack.append((nei, node)) return len(visited) == n

   Code Snippet 22: Iterative DFS approach to doing cycle check on trees (undirected graph subset)

4. Sort Items by Groups Respecting Dependencies (1203) ⭐️

   Pattern Extraction

   AI usage disclosure AI tool · rubber-ducking of arguments

   This dropdown was generated during coaching. Verify before integrating.
   

   Core Insight: Hierarchical constraints can be solved by decomposing them into independent subproblems at each level, then merging. The key move is recognising that cross-level dependencies induce constraints at the higher level, so you can topo sort both levels independently.

   Pattern Name: Hierarchical Topological Sort (Two-Level DAG)

   Canonical Section: Topological Sort family → Advanced variants; OR Advanced Graphs → Multi-level constraints

   Recognition Signals:

   • Multiple constraint hierarchies (“items in groups with dependencies”, “tasks in phases with precedence”)
   • Input structure suggests levels (group attribute, phase attribute, rank attribute)
   • Dependencies exist both within and across levels
   • No inherent ordering within a level; order must be derived from dependencies
   • Classic hint: “respect constraints at two different scales”

   Anti-Signals:

   • Single-level topo sort (vanilla LC 207/210) → don’t decompose
   • Undirected dependencies → Union-Find is more natural than topo sort
   • Weighted optimization (minimize cost of ordering) → use dynamic programming on topo sort, not the sort itself
   • Three or more levels with different constraint semantics → may require tree-based or recursive approach

   Decision Point: Two-phase approach (independent topo sorts + merge) vs. supergraph (single topo sort with virtual nodes). Both are O(V+E). Two-phase is easier to implement and explain in interviews; supergraph is mathematically elegant but requires careful node indexing. Choose two-phase unless supergraph reasoning is already underway.

   Interviewer Comms: “Items are grouped, and items have dependencies respecting both group boundaries and item precedence. I’ll decompose this into two topo sorts: groups (using only cross-group dependencies to establish group order) and items (using all dependencies to establish item order). Then I merge by iterating through the group order and appending items from each group in their topo-sorted order. This ensures both constraints are satisfied.”

   Pitfalls and Misconceptions

   AI usage disclosure AI tool · rubber-ducking of arguments

   This dropdown was generated during coaching. Verify before integrating.
   

   1. Trap: Forgetting to copy indegree dictionaries before passing to topo sort. Kahn’s algorithm mutates indegrees in-place (decrementing as edges are processed). Why: If you call topo(nodes1, adj1, indeg) and then topo(nodes2, adj2, indeg) on the same indeg object, the second call operates on a corrupted state (already-decremented indegrees from the first call). Correction: Pass `indeg.copy()` to each topo sort call, or use a separate indegree array for each graph.

   2. Trap: Building group edges for all item dependencies, not just cross-group ones. This creates redundant or incorrect group dependencies. Why: If item A and item B are in the same group and A → B, adding a group edge A.group → B.group is redundant (item topo sort already enforces A before B). Worse, multiple items crossing groups can create duplicate or conflicting edges. Correction: Only add a group edge when `group[prev_item] != group[item]`. Same-group dependencies are handled entirely by item topo sort.

   3. Trap: Not handling ungrouped items (group[i] == -1) explicitly. Treating them as a separate case or omitting them from group topo sort. Why: Ungrouped items are “virtual groups unto themselves” — each needs its own group node in the group topo sort to establish proper ordering. Without this, cross-dependencies from ungrouped items won’t be respected. Correction: Assign each ungrouped item a unique pseudo-group ID (e.g., incrementing from `m`). This transforms the problem into “all items have groups” and eliminates case logic.

   4. Trap: Assuming the item topo sort alone is sufficient; skipping the group topo sort. This fails when items from different groups have dependencies but the group order is wrong. Why: Item topo sort respects item-level edges but doesn’t “know about” group boundaries. Two items in different groups might topo-sort in the wrong group order, violating the constraint that all items from group A come before all items from group B. Correction: Both topo sorts are mandatory. Item topo sort ensures item ordering; group topo sort ensures group ordering. Merge them by iterating group order and appending items.

   5. Trap: Merging results incorrectly: either interleaving items and groups wrong, or not using the items_order at all. Why: The merge step is the “glue” that combines two independent sorts. If you build the result as `for item in items_order: res.append(item)` (ignoring group order), you violate group constraints. If you build it as `for group in group_order: res.extend(all_items_in_group)` (ignoring items_order), you violate item constraints within groups. Correction: Correct merge: `for group in group_order: res.extend(group_to_items[group])` where `group_to_items` is populated from `items_order`. This respects both.

   Problem Mutations

   AI usage disclosure AI tool · rubber-ducking of arguments

   This dropdown was generated during coaching. Verify before integrating.
   

   1. What if there are three levels of hierarchy (e.g., company → department → item)? (tests: generalization) Extend to three-phase: topo sort companies (cross-company item dependencies), topo sort departments (cross-department dependencies within companies), topo sort items (all dependencies). Merge hierarchically. Complexity is O(k · (V+E)) for k levels, still acceptable if k is small.

   2. What if items within a group must stay in a fixed order (not reorderable)? (tests: constraint rigidity) Items in a group have an intrinsic ordering (e.g., input order) that cannot be changed. Add item edges for all consecutive pairs within the group to enforce this. The two-phase approach handles this: just add the extra edges to item_adj and increment item_indeg accordingly.

   3. What if the goal is to minimize “group context switches” (consecutive items from the same group)? (tests: optimization, not just feasibility) Topo sort is a necessary constraint, but not sufficient. After topo sorting, you must select an ordering that clusters groups. Use a greedy approach: among all valid item orders respecting the topo sort, pick one that minimizes switches. This becomes a separate optimization layer on top of topo sort.

   4. What if group assignments are not fixed and can be optimized? (tests: decision expansion) Items can be reassigned to groups. The goal becomes: find an assignment and ordering that satisfy dependencies while optimizing some cost (e.g., minimize number of groups). This is a different problem class (assignment + scheduling), and topo sort is no longer the main algorithm.

   5. What if dependencies have time constraints (item A must start ≥ 5 time units before item B)? (tests: optimization metric) This is AON (Activity-On-Node) scheduling. Build group order with topo sort, then propagate earliest-start and latest-finish times through the item dependency graph. Topo sort establishes the ordering; time propagation computes the schedule. Complexity is still O(V + E) but requires two passes (forward for earliest-start, backward for latest-finish).

   This is a higher order question whereby we need to topo sort by 2 dimensions: topo sorting within items, topo sorting of groups. This gives us a 2-phased approach.

   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 52 53 54 55 56 57 58 59 60 61 62 63

   from collections import defaultdict, deque from typing import List class Solution: def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]: # Step 0: Assign unique group IDs to ungrouped items, keep them in unique groups new_gid = m for i in range(n): if group[i] == -1: group[i] = new_gid new_gid += 1 # Step 1: Prepare adjacency lists + indegrees group_adj, group_indeg = defaultdict(list), defaultdict(int) item_adj, item_indeg = defaultdict(list), defaultdict(int) # Step 2: Build both graphs for item in range(n): for prev_item in beforeItems[item]: # Build item dependency graph item_adj[prev_item].append(item) item_indeg[item] += 1 # Build group dependency graph, only if they belong to different groups if group[prev_item] != group[item]: src, dest = group[prev_item], group[item] group_adj[src].append(dest) group_indeg[dest] += 1 # Step 3: Topological sort helper def topo(nodes, adj, indeg): q = deque(x for x in nodes if indeg[x] == 0) res = [] while q: u = q.popleft() res.append(u) for nei in adj[u]: indeg[nei] -= 1 if indeg[nei] == 0: q.append(nei) return res if len(res) == len(nodes) else [] # Step 4: Get group order & item order group_nodes = list(range(new_gid)) group_order = topo(group_nodes, group_adj, group_indeg.copy()) # GOTCHA: remember to copy over else the reference indegree may be mutated if not group_order: return [] item_nodes = list(range(n)) items_order = topo(item_nodes, item_adj, item_indeg.copy()) if not items_order: return [] # Step 5: Arrange items by group according to items_order group_to_items = defaultdict(list) for item in items_order: group_to_items[group[item]].append(item) # Step 6: Build the final result res = [] for g in group_order: res.extend(group_to_items[g]) return res

   Code Snippet 23: Topo sorting on 2 dimensions: a 2-phased approach

   Another big-brain approach is to use an augmented graph for this (so we have a supergraph) but this hurts my head.

   The insight: virtual group nodes act as hierarchical control nodes. By adding edges group_node(g) → items_in_group(g), you enforce that all items in a group come after the group node in topo order. This creates a “funnel” effect: items are forced to cluster by group. The supergraph is more elegant mathematically (one topo sort, no merge logic), but harder to reason about (indirection via virtual nodes, node indexing scheme). For an interview, the two-phase approach is safer: simpler to explain, lower cognitive load, easier to debug.

   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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

   from collections import defaultdict, deque from typing import List class Solution: def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]: """ Single-graph approach for 1203. Instead of 2 separate topo sorts (items, then groups), we build one unified DAG containing: ​ - virtual group nodes ​ - item nodes and run ONE topological sort on all of them. """ # --- STEP 1: Assign unique group IDs to ungrouped items --- # Problem states group[i] == -1 if no group. We give these items # their own 'singleton' pseudo-group to enforce adjacency. new_group_id = m for i in range(n): if group[i] == -1: group[i] = new_group_id new_group_id += 1 total_groups = new_group_id # updated count after assignment # --- STEP 2: Node indexing scheme --- # 0..n-1 → item nodes # n..n+total_groups-1 → virtual group nodes def group_node(g_id: int) -> int: """ Map a group ID to its virtual node index in the graph """ return n + g_id # --- Data structures for graph + indegree --- G = defaultdict(list) # adjacency list indeg = defaultdict(int) # indegree dictionary # Initialize indegrees to zero for all nodes all_nodes = list(range(n)) + [group_node(g) for g in range(total_groups)] for node in all_nodes: indeg[node] = 0 # --- STEP 3: Connect each group node to the items it contains --- # This ensures items of the same group appear *after* the group's # node in topo order, making them contiguous in the final output. for item in range(n): gnode = group_node(group[item]) G[gnode].append(item) indeg[item] += 1 # --- STEP 4: Add edges for dependencies --- # For every beforeItems[i], item i must appear AFTER prev_item. for item in range(n): for prev_item in beforeItems[item]: if group[item] == group[prev_item]: # Same group → direct dependency between items G[prev_item].append(item) indeg[item] += 1 else: # Different groups → dependency between group nodes G[group_node(group[prev_item])].append(group_node(group[item])) indeg[group_node(group[item])] += 1 # --- STEP 5: Kahn's Algorithm (BFS Topological Sort) --- q = deque([node for node in all_nodes if indeg[node] == 0]) topo_order = [] while q: u = q.popleft() topo_order.append(u) for v in G[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) # --- STEP 6: Check for cycles --- # A cycle anywhere (items or groups) means no valid order exists. if len(topo_order) != len(all_nodes): return [] # --- STEP 7: Extract only items from topo_order --- # Group nodes were just helpers to enforce contiguous grouping. result = [node for node in topo_order if node < n] return result

   Code Snippet 24: Big-brain supergraph solution – tedius but not impossible