Advanced Synthesis

Nineteen topics in, you've built a toolbox: two pointers, sliding windows, heaps, union-find, DP over sequences and grids, greedy, intervals, sweep lines, tries, graphs. Nothing in this final topic is a brand-new idea in isolation — what's new is that every problem here needs two or more of those tools working together, or needs a familiar tool pushed somewhere it hasn't gone before. This is the capstone, and it's deliberately the hardest topic in the roadmap: if a problem here feels approachable, it's because an earlier topic already built the piece you're reaching for.

Two structures, doing two different jobs, at once

The Skyline Problem is the clearest example: a sweep line (from Intervals) decides when to check the skyline's height, and a multiset (from Heap/Priority Queue's world of "track the current extreme efficiently") decides what that height currently is. Sliding Window Median pairs a sliding window with two balanced multisets standing in for the two-heap median-finder — swapped in specifically because a sliding window needs to remove an *arbitrary* falling-out value, something a heap alone can't do without extra bookkeeping. Trapping Rain Water II takes the 2D grid instinct from graph traversal and fuses it with a min-heap doing Dijkstra-style "always expand the lowest known barrier first" — turning a 1D two-pointer problem's 2D generalization into a shortest-path-flavored problem instead.

Memoization is what separates "correct" from "finishes"

Word Break II and Longest Increasing Path in a Matrix both have a correct-looking solution that's also an exponential-time disaster without one addition: caching results keyed by whatever sub-problem repeats. Word Break II memoizes on the remaining suffix; Longest Increasing Path memoizes on the starting cell. In both cases, the *set* of distinct sub-problems is small (polynomial), but a naive recursive walk revisits the same ones over and over from different starting points — memoization is the difference between a solution that's correct in principle and one that actually returns before the heat death of the universe.

Reframe the question so a clean recurrence exists

Burst Balloons is the sharpest lesson in this topic on why the *first* framing of a DP problem isn't always the one that works. "Which balloon bursts first?" seems natural, but changes every other balloon's neighbors in a way that's hard to fold into a recurrence. "Which balloon bursts last in this range?" is the reframe that unlocks it — because a range's last-burst balloon is guaranteed to still have exactly the range's own boundary values as its neighbors, regardless of what order everything else inside the range was burst in. Recognizing when a DP is stuck because of the framing, not the technique, is itself an advanced-synthesis skill.

Deriving structure from unusual sources

Alien Dictionary and Number of Islands II both build a familiar structure (a graph; a union-find forest) from data that doesn't look like one at first. Alien Dictionary turns a sorted word list into a directed graph by comparing adjacent words character-by-character — the *graph itself* has to be derived before topological sorting (a pattern from Graphs) can even start. Number of Islands II applies union-find *online*, one addition at a time, rather than all at once on a fixed graph — a reminder that union-find's real strength is answering "are these connected right now" incrementally, not just as a one-shot batch computation.

Common mistakes

• Reaching for a brand-new technique when two familiar ones combine — nearly every problem in this topic is a combination, not an invention; look for which two earlier topics' tools apply before assuming neither does.
• Skipping memoization because a recursive solution "looks" polynomial — Word Break II's classic unsegmentable-input trap and Longest Increasing Path's overlapping-suffix problem both look deceptively simple until you trace how many times the same sub-problem gets re-solved.
• Getting stuck on a DP's first framing — Burst Balloons is unsolvable with a naive "burst order left to right" recurrence; the fix is reframing around what's burst *last*, not first.
• Forgetting event-order tiebreaks in a sweep line — The Skyline Problem's shared-x-coordinate ordering (start events before end events, tallest starts and shortest ends first) is what prevents a spurious dip; getting this backwards produces a subtly wrong skyline that only shows up on inputs with touching buildings.
• Trying to remove an arbitrary value from a plain heap — Sliding Window Median's whole design (two multisets instead of two heaps) exists because heaps only expose their top element for removal; anything else needs either lazy deletion or a different structure entirely.