Debrief

Key idea

The pair-counting problem was not a graph problem

Counting pairs in different components looks like it needs the pairs. It does not. Find the component sizes with either traversal or union-find, and the count follows from arithmetic.

For a component of size s in a graph of n nodes, the pairs it forms with everything outside it number s times n minus s. Summing that over every component counts each pair twice, once from each side, so halve it at the end.

The alternative arithmetic is total pairs minus within-component pairs, which is n choose 2 minus the sum of s choose 2. Either is fine. The lesson is that once the components are known, the answer is a formula rather than a search.

Key idea

Trie deletion was the genuinely new part

Inserting and searching were covered. Deleting was not, and it has a real decision in it: when a word is removed, what happens to the nodes that spelled it?

Clearing the end-of-word flag is enough for correctness, and it leaks memory over time as dead branches accumulate. Pruning nodes with no children and no flag keeps the structure tight, and it has to happen on the way back up the recursion, since a node can only be removed once its child has been.

Either answer is acceptable if you state the trade. Silently doing the first without noticing the second is the weaker result.

Why it works

What is left

Four units remain. Two of them are dynamic programming, which is the largest remaining block and the one everything so far has been building toward: it is recursion, from U8, with the results remembered.

If the recursion in this checkpoint felt awkward, that is worth fixing before U14 rather than during it. Everything else remaining, greedy, math, and bit manipulation, is self-contained.