Graphs: BFS, DFS and topological sort

Deep copy a connected undirected graph.

Trigger

'Clone', 'deep copy' of a graph with cycles.

Approach

1. The problem is cycles: naive recursion loops forever.
2. Keep a map from original node to its copy. Check it before recursing.
3. That map is both the memo and the visited set — say that, it is the whole solution.

Target complexity

O(V + E) time and space.

Pitfall

Creating the copy after recursing into the neighbours. Register the copy in the map *first*, then recurse.

Say it out loud

“The difficulty is cycles, not copying. I keep a map from original to clone, and I insert the clone into the map *before* I recurse into the neighbours — that single ordering choice is what makes the cycle terminate.”

Solve on LeetCode

Decide whether a set of courses with prerequisites can be completed.

Trigger

'Prerequisites', 'dependencies', 'is there a valid order'.

Approach

1. Reframe out loud: this asks whether a directed graph has a cycle.
2. Kahn's algorithm: in-degrees, queue the zeros, remove and decrement.
3. If any vertex remains with a non-zero in-degree, there is a cycle.
4. Alternative: three-colour DFS — grey means on the current stack.

Target complexity

O(V + E) time and space.

Pitfall

Using union-find. It detects cycles in *undirected* graphs and gives the wrong answer here.

Say it out loud

“This is cycle detection on a directed graph. I'll use Kahn's algorithm — compute in-degrees, process the zeros, and if anything is left over there's a cycle. Worth saying: union-find wouldn't work here, it only handles undirected cycles.”

Solve on LeetCode

Return a valid order to complete all courses, or empty if impossible.

Trigger

The same as above, but asking for the order rather than a yes or no.

Approach

1. Same Kahn's algorithm, but record the dequeue order.
2. That order is a valid topological sort.
3. If the recorded order is shorter than the number of courses, there is a cycle — return empty.

Target complexity

O(V + E) time and space.

Pitfall

Returning a partial order when a cycle exists. Check the length before returning.

Say it out loud

“Same algorithm as the decision version — the order in which Kahn's algorithm dequeues *is* a topological order. The only extra step is checking the result length, because a cycle produces a short answer rather than an error.”

Solve on LeetCode

Count connected regions of land in a grid.

Trigger

'How many groups', 'connected regions' on a grid.

Approach

1. Say the reframe: a grid is a graph, each cell a vertex with up to four neighbours.
2. Scan every cell; on unvisited land, run a flood fill and increment the counter.
3. Mark visited as you go — either a visited set or mutating the grid, and say which and why.
4. Union-find is an alternative; it wins if the grid changes dynamically.

Target complexity

O(m · n) time, O(m · n) space worst case.

Pitfall

Recursive DFS on a large grid in Python — a 1000×1000 all-land grid blows the recursion limit.

Say it out loud

“A grid is a graph in disguise. I sweep the cells, and every time I hit unvisited land I flood fill the whole region and count one. At this size I'd write the fill iteratively — recursive DFS on a million-cell grid would hit Python's recursion limit.”

Solve on LeetCode

Count the connected components in an undirected graph given as an adjacency matrix.

Trigger

'How many groups', 'connected components', undirected.

Approach

1. Two valid answers: DFS/BFS over unvisited vertices, or union-find.
2. Union-find: start with n components and decrement on every successful union.
3. Say the complexity honestly: α(n) amortised, not exactly O(1).

Target complexity

O(n²) because the input is a matrix; union-find operations are α(n) amortised.

Pitfall

Claiming union-find is O(1). It is inverse Ackermann, which is under 5 for any real n but is not constant.

Say it out loud

“Either DFS from each unvisited vertex or union-find. I'll use union-find with path compression and union by rank — that's inverse Ackermann amortised, effectively constant though not exactly O(1). The input being a matrix means the scan itself is n squared regardless.”

Solve on LeetCode

Find the cells from which water can reach both oceans, flowing only to equal or lower neighbours.

Trigger

'Reach both', two sources, a flow constraint.

Approach

1. Forwards is expensive: a search from every cell is O((mn)²).
2. Invert it: start from each ocean's border and walk **uphill** (to equal or higher neighbours).
3. Two reachability sets; the answer is their intersection.

Target complexity

O(m · n) time and space.

Pitfall

Doing it forwards from every cell. It is correct and far too slow.

Say it out loud

“Searching from every cell would be quadratic in the grid size. Instead I invert the direction: start at each ocean's edge and walk uphill, which gives me the set of cells that drain to that ocean. The answer is the intersection of the two sets, and it's linear.”

Solve on LeetCode

Find the edge whose removal turns a graph with one extra edge back into a tree.

Trigger

'One extra edge', 'find the edge that creates the cycle', undirected.

Approach

1. A tree with n vertices has n−1 edges, so exactly one edge closes a cycle.
2. Process edges in order with union-find. The first union that finds both endpoints already connected is the answer.
3. This is exactly what union-find is for — say so.

Target complexity

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

Pitfall

Building the graph and running DFS per edge. Correct and quadratic.

Say it out loud

“Union-find is made for this. I process the edges in order, and the first edge whose two endpoints are already in the same set is the one closing the cycle. That's a single pass rather than a search per edge.”

Solve on LeetCode

Find the number of minutes until every fresh orange has rotted, spreading to adjacent cells.

Trigger

'Spreading from several sources simultaneously', 'minimum time'.

Approach

1. Multi-source BFS: seed the queue with **every** rotten cell at once.
2. Process level by level; each level is one minute.
3. Count the fresh oranges up front so you can detect the unreachable case at the end.

Target complexity

O(m · n) time and space.

Pitfall

Running BFS once per rotten cell. Seeding them all at once is the same algorithm and is linear.

Say it out loud

“This is multi-source BFS — I seed the queue with every rotten cell at once and the wavefront expands in lockstep, so each BFS level is one minute. People overcomplicate this by running one search per source; it's the same algorithm with a different initial queue.”

Solve on LeetCode

Order items subject to both item-level dependencies and group-level cohesion.

Trigger

Dependencies at two levels — the hard version of topological sort.

Approach

1. Two topological sorts, not one: order the groups, then order the items inside each group.
2. Assign every ungrouped item its own singleton group, so the model is uniform.
3. Lift item dependencies that cross groups into group dependencies.
4. A cycle at either level means no valid order.

Target complexity

O(V + E) time and space, run twice.

Pitfall

Trying to do it with one flat topological sort. The group cohesion constraint is not expressible that way.

Say it out loud

“There are two levels of constraint, so there are two topological sorts: one over the groups and one within each group. The setup step that makes it clean is giving every ungrouped item its own group, so I don't need a special case, and lifting cross-group item edges up to the group graph.”

Solve on LeetCode

Find the shortest transformation sequence between two words, changing one letter at a time.

Trigger

'Shortest sequence of steps' where the graph is implicit.

Approach

1. The graph is implicit: words are vertices, one-letter differences are edges. Say that first.
2. Do not build all pairs — that is O(n²·L). Generate neighbours by wildcarding each position.
3. BFS, because every edge has the same weight.
4. Mention bidirectional BFS as the optimisation: it roughly halves the exponent.

Target complexity

O(n · L · 26) time with the wildcard trick, O(n · L) space.

Pitfall

Building the adjacency list by comparing every pair of words. That is the quadratic trap.

Say it out loud

“The graph is implicit, and the mistake would be materialising it by comparing every pair. Instead I generate neighbours by replacing each position with a wildcard and looking up a precomputed bucket. Then it's plain BFS, since every edge costs one.”

Solve on LeetCode