Patterns/Part III - Hashing & Auxiliary Structures/Amortized Patterns

Pattern Reference

Amortized Patterns

"Why O(n) operations can cost O(1) each on average (two-pointer, stack, deque)."

Loading...

Deep Dive Tutorial

Amortized O(1): even though a single operation may be expensive, we "charge" the cost to cheaper previous operations. Example: queue from two stacks — dequeue from "out" stack; if empty, pour all from "in" into "out" (O(n)). But each element crosses from "in" to "out" exactly once, so total over n operations = O(n), amortized O(1). Union-Find: each path compression does O(log n) work, but "charges" nodes on the path, each charged only O(log n) times total.

Amortized data structure patterns
// Stack with O(1) min/max
class MinStack {
    constructor() { this.stack = []; this.minStack = []; }
    push(v) {
        this.stack.push(v);
        this.minStack.push(Math.min(v, this.minStack.length ? this.minStack.at(-1) : v));
    }
    pop() { this.stack.pop(); this.minStack.pop(); }
    top() { return this.stack.at(-1); }
    getMin() { return this.minStack.at(-1); }
}

// Queue from two stacks — O(1) amortized enqueue and dequeue
class TwoStackQueue {
    constructor() { this.inStack = []; this.outStack = []; }
    push(v) { this.inStack.push(v); }
    pop() {
        if (!this.outStack.length) {
            while (this.inStack.length) this.outStack.push(this.inStack.pop());
        }
        return this.outStack.pop();
    }
    peek() {
        if (!this.outStack.length) {
            while (this.inStack.length) this.outStack.push(this.inStack.pop());
        }
        return this.outStack.at(-1);
    }
}

// Lazy deletion: mark items as deleted, skip on access
// Use when removing from middle of a priority queue
class LazyHeap {
    constructor() { this.heap = []; this.deleted = new Map(); }
    push(v) { /* add to heap */ }
    delete(v) { this.deleted.set(v, (this.deleted.get(v) || 0) + 1); }
    top() {
        // Skip deleted elements
        while (this.heap.length && this.deleted.get(this.heap[0])) {
            this.deleted.set(this.heap[0], this.deleted.get(this.heap[0]) - 1);
            this.heap.shift(); // pop from heap
        }
        return this.heap[0];
    }
}

Worked Problems

1
Min Stack
Medium
Solve ↗
2
Implement Queue using Stacks
Easy
Solve ↗
3
LRU Cache
Medium
Solve ↗
4
Find Median from Data Stream (revisited — lazy deletion)
Hard
Solve ↗
zap
Amortized analysis methods:
- Aggregate: total cost / n operations = amortized cost
- Accounting: assign "credits" to cheap ops, spend on expensive ops
- Potential method: Φ = potential energy of state; amortized cost = actual + ΔΦ

Key patterns:
- Two-stack queue: each element enqueued/dequeued once → O(1) amortized
- Stack min: each element pushed/popped from minStack once → O(1) amortized
- Union-Find path compression: O(α(n)) amortized per operation
- Fenwick tree update: O(log n), but aggregate query is O(n)

Lazy deletion: When removing from middle of heap is O(n), mark deleted and skip on top access. Total work = O(n log n) for n deletions.
← All Patterns