When one pattern isn't enough

01 · Recognition

How to spot a mixed-pattern problem

Before reaching for anything exotic, interrogate the problem with a short set of questions. If more than one of these comes back "yes," you're very likely looking at a combo, not a single pattern:

• Does it need fast lookup by key AND a sense of order or recency? That's the signature of hashmap + linked list.
• Does it need a moving window or range AND fast min/max within that range? That's sliding window + monotonic deque (or monotonic stack).
• Does it need a greedy, priority-based choice at every step AND a tree-like or graph-like structure to build? That's heap + tree, or greedy + union-find.

02 · Combo #1

LRU Cache: Linked List + Hashmap

A hashmap alone gives you O(1) lookup by key, but it has no built-in notion of "which entry was used least recently" — dictionaries don't remember access order in a way you can cheaply query and reorder. A doubly-linked list alone gives you O(1) removal and reordering of nodes, but finding which node corresponds to a given key means walking the list — O(n).

Put them together and each covers the other's gap: a hashmap maps key → node for instant lookup, while a doubly-linked list keeps every node ordered from most- to least-recently-used. get(key) uses the hashmap to jump straight to the node, then unlinks and re-inserts it at the "most recent" end of the list. put(key, value) does the same insert-or-update, and if the cache is now over capacity, it evicts whatever sits at the "least recent" end — again in O(1), because the linked list already knows exactly which node that is. Neither structure alone can do this in constant time; together, both operations are O(1).

See it built step by step in the LRU Cache visualizer, or read the deeper mechanics of the list side in the Linked List theory page.

03 · Combo #2

Sliding Window Maximum: Sliding Window + Monotonic Deque

A plain sliding window is great at tracking a moving range efficiently — add one element on the right, drop one on the left, all in O(1) per step. But if you need the maximum value inside that window at every step, and you find it by scanning the whole window each time, you're back to O(k) per step and O(n·k) overall — the windowing didn't actually save you anything for this particular question.

The fix is to keep a monotonic deque alongside the window: a double-ended queue of indices, kept in decreasing order of their values. Before pushing a new index, pop off anything smaller from the back (it can never be the max again while a bigger, more recent value is in the window). Pop from the front whenever the index there has slid out of the window. The front of the deque is then always the max of the current window, retrievable in O(1) — and because each index is pushed and popped at most once across the entire pass, the whole algorithm stays O(n), not O(n·k).

Watch this in action in the Sliding Window Maximum visualizer. For the windowing half, see the Sliding Window theory page; the monotonic-deque trick itself is a direct borrow from the monotonic stack idea covered on the Stack theory page.

04 · Combo #3

Next Greater Element: Array Scanning + Monotonic Stack

This one is really filed under Stack as its primary category, and it's simpler than the two combos above — but it's worth a mention here because it's the cleanest, smallest example of the same underlying shape: a plain linear scan across an array, with a monotonic stack maintained alongside it to answer "what's the next bigger value" for each element in O(1) amortized instead of O(n) per query. The pattern — maintain an ordered auxiliary structure while doing a single pass — is exactly what powers the Sliding Window Maximum combo above, just without the "window" part.

Try it in the Next Greater Element visualizer, and see the full monotonic-stack mechanics on the Stack theory page.

05 · Combo #4

Huffman Coding: Greedy + Heap + Tree

Huffman Coding stacks three ideas instead of two, and each one answers a different question:

• Greedy decides the strategy — at every step, always merge the two least-frequent items into one. This choice is what makes the final encoding optimal.
• Min-heap is the data structure that makes "find the two smallest items right now" fast — O(log n) per extraction instead of O(n) if you were scanning a plain list every time.
• Tree is literally the output — every merge creates a new parent node, and the characters that got merged latest (the frequent ones) end up with short root-to-leaf paths, while rare characters end up with long ones. That's the whole point of the encoding: frequent symbols get short codes.

Take any one of the three away and the algorithm breaks: without the greedy rule you don't know what to merge; without the heap the merging is too slow to be practical at scale; without building an actual tree you have no way to turn "merge order" into a usable prefix code.

Explore it in the Huffman Coding visualizer, with background on each piece in the Greedy theory page, the Heap theory page, and the Trees theory page.

06 · Method

A repeatable framework for spotting combos

1. 1 List the problem's actual requirements separatelyFast lookup by key? Fast ordering or recency? Fast min/max over a range? A global optimum at each step? Write each one down as its own line, don't bundle them.
2. 2 Check if one single pattern already covers everythingIf some pattern from the other theory pages satisfies every requirement on your list at once, stop there — it isn't a mixed-pattern problem, and combining structures would only add complexity for no benefit.
3. 3 Otherwise, find which two (rarely three) patterns split the requirementsLook for one technique that covers some of your list and a second that covers the rest — the LRU Cache split is lookup vs. ordering; Sliding Window Maximum's split is windowing vs. fast max.
4. 4 Let each structure do only what it's good atDon't force the hashmap to track order, and don't force the linked list to do key lookup. The moment you're fighting a structure to do a job it's a poor fit for, that's a sign you're missing the second piece.
5. 5 Re-check the combined complexityO(1) plus O(1) should still be O(1) overall — verify the glue code connecting the two structures doesn't quietly introduce an O(n) scan somewhere (a linear search to "find the node," a rebuild of the heap, etc.).

07 · Before you start coding

Common mistakes

• Reaching for a mixed-pattern combo when a single existing pattern already solves the whole problem — overengineering a two-structure solution where one would do.
• Combining two structures but letting them fall out of sync — e.g. updating the hashmap in an LRU Cache but forgetting to also move the corresponding linked-list node, so the two disagree about state.
• Picking the wrong structure for one half of the combo — e.g. using a sorted array instead of a heap when frequent insertions are needed, which quietly turns an O(log n) operation into O(n) without an obvious symptom.
• Not double-checking that the combined solution's overall complexity is actually still efficient once you add up both structures' costs, including the code that keeps them in sync.