🏗️ Design

A learning sheet — "design a data structure" is one move: spot the operation that's slow with your first structure, then bolt on a second one that makes it fast.

🧠 1 · How to think — combine two structures

A "design X" prompt lists operations and a target cost (usually O(1) or O(log n) each). No single textbook structure does everything — a hash map is O(1) but unordered; an array has indices but slow middle-delete; a list keeps order but slow lookup. The whole skill is: name the op that's slow, then pair a second structure that's fast at exactly that op, and keep them in sync.

Watch it get invented — LRU Cache

1. Pick one structure. A hash map gives O(1) get/put — but evicting the least-recently-used key means scanning all of it, O(n).
2. Name the slow op. "Track recency + evict the oldest in O(1)." A list ordered by recency does that — but then finding a key is O(n).
3. Combine. Hash map key → node (for O(1) find) plus a doubly linked list ordered most-recent-first (for O(1) move-to-front and tail eviction). The map's value is the list node, so every splice is O(1).
4. Payoff. Both get and put are O(1) — neither structure could do it alone.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The five core patterns

Every one is "structure A + structure B kept in sync." Each: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens.

4.1 · Map + Doubly Linked List (LRU)

“Map finds the node in O(1); the list reorders and evicts in O(1).”

class DLLNode { key = 0; val = 0; prev: DLLNode | null = null; next: DLLNode | null = null; }

class LRUCache {
  private map = new Map<number, DLLNode>();
  private head = new DLLNode(); private tail = new DLLNode();   // sentinels
  constructor(private cap: number) { this.head.next = this.tail; this.tail.prev = this.head; }
  private remove(n: DLLNode) { n.prev!.next = n.next; n.next!.prev = n.prev; }
  private addFront(n: DLLNode) { n.next = this.head.next; n.prev = this.head; this.head.next!.prev = n; this.head.next = n; }

  get(key: number): number {
    const n = this.map.get(key);
    if (!n) return -1;
    this.remove(n); this.addFront(n);          // touch → most recent
    return n.val;
  }
  put(key: number, val: number): void {
    const ex = this.map.get(key);
    if (ex) { ex.val = val; this.remove(ex); this.addFront(ex); return; }
    if (this.map.size === this.cap) {          // evict LRU = node before tail
      const lru = this.tail.prev!;
      this.remove(lru); this.map.delete(lru.key);   // keep BOTH in sync
    }
    const n = new DLLNode(); n.key = key; n.val = val;
    this.addFront(n); this.map.set(key, n);
  }
}

4.2 · Map + Array (getRandom in O(1))

“Array gives random access; delete by swapping the victim with the last.”

Setup: an array supports O(1) random pick, but O(1) delete only at the end — so to delete any element, swap it with the last, then pop. A map of value → index finds it instantly.

class RandomizedSet {
  private arr: number[] = [];
  private idx = new Map<number, number>();          // value → its index in arr
  insert(v: number): boolean {
    if (this.idx.has(v)) return false;
    this.idx.set(v, this.arr.length); this.arr.push(v); return true;
  }
  remove(v: number): boolean {
    if (!this.idx.has(v)) return false;
    const i = this.idx.get(v)!, last = this.arr[this.arr.length - 1];
    this.arr[i] = last; this.idx.set(last, i);       // move last into the hole + fix its index
    this.arr.pop(); this.idx.delete(v); return true;
  }
  getRandom(): number { return this.arr[(Math.random() * this.arr.length) | 0]; }
}

4.3 · Auxiliary structure (Min Stack, Queue from Stacks)

“Carry a second, parallel structure that answers the extra query for free.”

Setup: a stack can't report its minimum in O(1) — so keep a parallel stack of running minimums. The same idea (an auxiliary structure) implements a queue from two stacks.

// Min Stack — O(1) push/pop/top/getMin
class MinStack {
  private st: number[] = [];
  private mins: number[] = [];                        // mins[i] = min of st[0..i]
  push(x: number) { this.st.push(x); this.mins.push(this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x); }
  pop() { this.st.pop(); this.mins.pop(); }
  top() { return this.st[this.st.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

// Queue from two stacks — amortized O(1)
class MyQueue {
  private inS: number[] = []; private outS: number[] = [];
  push(x: number) { this.inS.push(x); }
  private shift() { if (!this.outS.length) while (this.inS.length) this.outS.push(this.inS.pop()!); }
  pop(): number { this.shift(); return this.outS.pop()!; }
  peek(): number { this.shift(); return this.outS[this.outS.length - 1]; }
}

4.4 · Time-ordered (Map + sorted + binary search)

“Per key, keep entries in time order; binary-search the latest ≤ t.”

Setup: values are written with increasing timestamps, so each key's history is naturally sorted — a binary search finds the most recent value at or before a query time in O(log n).

// TimeMap — set(key,val,t) with increasing t; get(key,t) = value at the latest time ≤ t
class TimeMap {
  private map = new Map<string, [number, string][]>();    // key → sorted [time, value]
  set(key: string, val: string, time: number) {
    if (!this.map.has(key)) this.map.set(key, []);
    this.map.get(key)!.push([time, val]);                  // appended in time order
  }
  get(key: string, time: number): string {
    const a = this.map.get(key);
    if (!a) return '';
    let lo = 0, hi = a.length - 1, res = '';
    while (lo <= hi) {                                      // floor: latest time ≤ query
      const mid = (lo + hi) >> 1;
      if (a[mid][0] <= time) { res = a[mid][1]; lo = mid + 1; }
      else hi = mid - 1;
    }
    return res;
  }
}

4.5 · Iterators — controlled traversal

“Pause a traversal between calls by holding its frontier on a stack.”

Setup: an iterator must yield one element per next() and resume later — so you store the in-progress traversal explicitly (a stack), instead of recursing all at once.

// BST Iterator — inorder, one step at a time
class BSTIterator {
  private st: TreeNode[] = [];
  constructor(root: TreeNode | null) { this.pushLeft(root); }
  private pushLeft(n: TreeNode | null) { while (n) { this.st.push(n); n = n.left; } }
  hasNext(): boolean { return this.st.length > 0; }
  next(): number {
    const n = this.st.pop()!;       // smallest remaining
    this.pushLeft(n.right);         // its successor's spine
    return n.val;
  }
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 359 Logger Rate Limiter
class Logger {
  private next = new Map<string, number>();
  shouldPrintMessage(ts: number, msg: string): boolean {
    if ((this.next.get(msg) ?? 0) > ts) return false;   // still inside the 10 s window
    this.next.set(msg, ts + 10);                         // only update when we actually print
    return true;
  }
}

// 1146 Snapshot Array — store only the cells that changed, per snapshot
class SnapshotArray {
  private hist: [number, number][][];                    // hist[i] = [[snapId, value], ...] ascending
  private snapId = 0;
  constructor(n: number) { this.hist = Array.from({ length: n }, () => [[0, 0]] as [number, number][]); }
  set(i: number, v: number): void {
    const h = this.hist[i], last = h[h.length - 1];
    if (last[0] === this.snapId) last[1] = v; else h.push([this.snapId, v]);   // overwrite within the same snap
  }
  snap(): number { return this.snapId++; }
  get(i: number, s: number): number {                    // last version with snapId <= s
    const h = this.hist[i]; let lo = 0, hi = h.length - 1;
    while (lo < hi) { const mid = (lo + hi + 1) >> 1; if (h[mid][0] <= s) lo = mid; else hi = mid - 1; }
    return h[lo][1];
  }
}

// 432 All O`one Data Structure — DLL of count buckets, O(1) everything
class Bucket { keys = new Set<string>(); prev: Bucket | null = null; next: Bucket | null = null; constructor(public count: number) {} }
class AllOne {
  private head = new Bucket(0); private tail = new Bucket(Infinity); private where = new Map<string, Bucket>();
  constructor() { this.head.next = this.tail; this.tail.prev = this.head; }
  private insertAfter(b: Bucket, count: number): Bucket {
    if (b.next!.count === count) return b.next!;
    const nb = new Bucket(count); nb.prev = b; nb.next = b.next; b.next!.prev = nb; b.next = nb; return nb;
  }
  private insertBefore(b: Bucket, count: number): Bucket {
    if (b.prev!.count === count) return b.prev!;
    const nb = new Bucket(count); nb.next = b; nb.prev = b.prev; b.prev!.next = nb; b.prev = nb; return nb;
  }
  private dropIfEmpty(b: Bucket) { if (b !== this.head && b !== this.tail && b.keys.size === 0) { b.prev!.next = b.next; b.next!.prev = b.prev; } }
  inc(key: string): void {
    const cur = this.where.get(key) ?? this.head;
    const nb = this.insertAfter(cur, cur.count + 1);
    nb.keys.add(key); this.where.set(key, nb);
    if (cur !== this.head) { cur.keys.delete(key); this.dropIfEmpty(cur); }
  }
  dec(key: string): void {
    const cur = this.where.get(key)!;
    if (cur.count === 1) this.where.delete(key);         // count 0 → forget the key entirely
    else { const nb = this.insertBefore(cur, cur.count - 1); nb.keys.add(key); this.where.set(key, nb); }
    cur.keys.delete(key); this.dropIfEmpty(cur);
  }
  getMaxKey(): string { const b = this.tail.prev!; return b === this.head ? '' : b.keys.values().next().value!; }
  getMinKey(): string { const b = this.head.next!; return b === this.tail ? '' : b.keys.values().next().value!; }
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• lru LRUCache (map + DLL, sentinels)
• random RandomizedSet (swap-with-last)
• aux MinStack + MyQueue (two stacks)
• time TimeMap (floor binary search)
• iterator BSTIterator

For each: list the required ops + target cost, then name the two structures and what each covers — before the code.