Pattern Guide
Amortized O(1) Patterns
"O(1) average via "charge" analysis. Two stacks, stack with min, queue from stacks."
Amortized analysis proves that a sequence of n operations costs O(n) total even if individual operations can be expensive. Key patterns: (1) stack with min/max in O(1) using an auxiliary stack; (2) queue from two stacks with O(1) amortized dequeue; (3) lazy deletion (mark deleted, clean on access); (4) Union-Find path compression; (5) sliding window with deque. Each element is processed O(1) times total.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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];
}
}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.
// 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];
}
}- 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.