Pattern · Design

Combine Structures to Design

Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Time O(1) per operation for LRU · Space O(capacity)

Taught in Module 40: Designing Data Structures (arrives in wave 4)

Think of it like this

A library with a catalogue (find any book instantly) and a returns trolley in order (know which came back last).

Clues that point here

→ "Design a class" with several operations
→ Each operation has a required complexity, often O(1)
→ LRU, LFU, time-based key-value store
→ Min stack, randomised set

Not this pattern when

✕ One structure already supports every operation fast enough

The template

A skeleton to adapt. The parts in comments are what changes from problem to problem.

Combine Structures to Design · template

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> map;

    LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true);   // access order
    }
    int get(int key) { return map.getOrDefault(key, -1); }
    void put(int key, int value) {
        map.put(key, value);
        if (map.size() > capacity) map.remove(map.keySet().iterator().next());  // least recent
    }
}

Common versions

LRU cache
LFU cache
Min stack
Insert delete getRandom O(1)
Time-based key-value store

Practice problems with this pattern

9.2Min StackMediummain pattern 10.2Implement Queue Using StacksEasymain pattern 10.3Number of Recent CallsEasymain pattern 10.4Design Circular QueueMediummain pattern 17.9BST IteratorMediumalso uses it 18.3Kth Largest Element in a StreamEasyalso uses it 18.5Find Median from Data StreamHardalso uses it 19.1Implement Trie (Prefix Tree)Mediumalso uses it

Command Palette

The template

Common versions

Practice problems with this pattern