Amortized Analysis and Complexity Patterns: Dynamic Arrays, Union-Find, Monotonic Deque

By /

Amortized Analysis and Time Complexity Patterns

Amortized analysis evaluates the average performance of operations over a sequence, not worst-case per operation. It is essential for understanding dynamic arrays, hash tables, and Union-Find, and comes up in senior-level algorithm interviews at companies like Google, Meta, and Jane Street.

What is Amortized Analysis?

Some data structures have operations that are occasionally expensive but rarely so. If we charge the expensive operation against the cheap operations that preceded it, the amortized cost per operation is still O(1).

Three methods: Aggregate (total cost / n), Accounting (virtual credits), Potential (mathematical potential function). For interviews, understand the intuition — you rarely need to prove the formal bound.

Dynamic Array (ArrayList / Python List)

A dynamic array doubles in capacity when full. Individual appends: mostly O(1), occasionally O(n) when resizing. Why is append O(1) amortized?

Capacity 1 → fill → resize to 2  (copy 1 element)
Capacity 2 → fill → resize to 4  (copy 2 elements)
Capacity 4 → fill → resize to 8  (copy 4 elements)
...
After n appends: copies = 1 + 2 + 4 + ... + n/2 = n-1

Total work for n appends = n (the appends) + n-1 (copies) = 2n-1 = O(n)
Amortized cost per append = O(n)/n = O(1)

The doubling strategy is critical — growing by a fixed amount (e.g., +10) would give O(n^2) total, O(n) amortized. Doubling gives O(n) total, O(1) amortized.

Hash Table

Hash tables resize (rehash) when the load factor exceeds a threshold (typically 0.75). Rehashing is O(n) but rare. Amortized cost of insert is O(1) by the same argument as dynamic array doubling.

Collision resolution:

  • Chaining: each bucket is a linked list. Worst case O(n) if all keys hash to one bucket. Expected O(1) with a good hash function and load factor < 1.
  • Open addressing: probe for the next empty slot. Better cache performance, but degrades faster at high load factors. Python dicts use open addressing.

Union-Find (Disjoint Set Union)

Union-Find supports: find(x) — return the root of x's set; union(x, y) — merge the sets containing x and y.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):          # path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):      # union by rank
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

With path compression + union by rank: amortized O(α(n)) per operation, where α is the inverse Ackermann function — effectively O(1) for all practical inputs (α(n) ≤ 4 for n < 10^600).

Stack with O(1) Min (LeetCode 155)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []   # tracks current min at each depth

    def push(self, val):
        self.stack.append(val)
        cur_min = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(cur_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def get_min(self): return self.min_stack[-1]

Sliding Window Maximum (Monotonic Deque)

Finding the max of every window of size k in O(n) using a deque that maintains a decreasing order:

from collections import deque
def max_sliding_window(nums, k):
    dq = deque()  # stores indices, values are decreasing
    result = []
    for i, n in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller elements (they can never be max)
        while dq and nums[dq[-1]] = k - 1:
            result.append(nums[dq[0]])
    return result
# Each element is added and removed at most once: O(n) total

Amortized analysis: each index enters and leaves the deque exactly once, so total operations = 2n = O(n) across all windows.

Two-Stack Queue (Amortized O(1) enqueue/dequeue)

class MyQueue:
    def __init__(self):
        self.inbox = []    # receives new elements
        self.outbox = []   # serves dequeue requests

    def enqueue(self, val): self.inbox.append(val)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:          # transfer all: O(n) but rare
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()
# Each element crosses from inbox to outbox exactly once: O(1) amortized

Common Complexity Patterns

Pattern Worst case per op Amortized
Dynamic array append O(n) O(1)
Hash table insert O(n) O(1)
Union-Find (with optimizations) O(log n) O(α(n)) ≈ O(1)
Monotonic deque window O(n) O(1) per element
Two-stack queue dequeue O(n) O(1)
Splay tree operation O(n) O(log n)

Interview Tips

  • When an interviewer asks “but isn't resize O(n)?” — explain amortized analysis with the doubling argument
  • Union-Find comes up in graph problems: number of islands, redundant connection, accounts merge
  • Monotonic deque is the key to any sliding window maximum/minimum problem in O(n)
  • Two-stack queue is a classic question at Google, Apple, and Microsoft
  • For Union-Find, always implement both path compression and union by rank — missing either gives a weaker bound

  • Atlassian Interview Guide
  • Databricks Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide
    • Scroll to Top