Linear structures: arrays, hash maps and monotonic stacks

Most interview problems are solved by choosing the right linear structure, and the choice follows from one question: what do you need to look up, and by what? Everything else — the hash map, the deque, the monotonic stack — is an answer to a particular version of that.

You need	Use	Why
Index-based access	Array	$O(1)$ and contiguous
Lookup by key	Hash map	$O(1)$ average
Ordered iteration by key	Balanced tree / sorted map	$O(\log n)$ , keeps order
Insert and remove at both ends	Deque	$O(1)$ at either end
Last-in, first-out	Stack	Matching, nesting, backtracking
Frequent insert and delete mid-sequence	Linked list	$O(1)$ given the node

Table 2.1 · Choosing the structure. Linked lists win far less often than their prominence in courses suggests. Their

O(1)

insertion requires already holding the node, and their cache behaviour is so poor that an array beats them at realistic sizes even for the operations they are supposed to win.

Proposition 2.2

How a hash map works

Hash the key to a bucket index, then handle collisions by chaining a list in each bucket or by probing for the next free slot. Average lookup is $O(1)$ because the load factor is kept bounded — the table resizes and rehashes when it fills past a threshold, which is what makes the amortised cost constant.

Holds when

Worst case is $O(n)$ when every key collides, which an adversary can arrange if the hash is predictable.
Open addressing is faster in cache terms; chaining degrades more gracefully at high load.
Keys must be immutable, or a mutation changes the hash and the entry becomes unreachable.

Figure 2.3 · Finding one item among a million. The first three are indistinguishable at this scale and the fourth is the entire reason hashing exists. Note the middle entry: twenty steps is close enough to constant that "sort it once and binary search" beats a hash map whenever you also need order.

The hash map is the trade you make first. A very large share of interview problems reduce to "I am doing a linear scan inside a loop, so this is quadratic" — and the fix is nearly always to precompute a hash map and replace the inner scan with a lookup. Two-sum, finding duplicates, grouping anagrams, counting pairs: all the same move, trading $O(n)$ memory for a factor of $n$ in time. Recognising that shape quickly is worth more than any individual algorithm.

Proposition 2.4

Monotonic stacks and deques

Keep a stack whose contents are always increasing or decreasing, popping anything that violates the order as you push. Each element is pushed and popped once, so the whole scan is linear despite the inner loop — and it answers "next greater element" style questions directly.

Holds when

Next greater or smaller element: a monotonic stack, in one pass.
Sliding-window maximum: a monotonic deque, popping from both ends.
Largest rectangle in a histogram: a monotonic stack, and the canonical hard example.

Linear structures: arrays, hash maps and monotonic stacks

After this lesson you should be able to

How a hash map works

Monotonic stacks and deques

The rest of this lesson is in Premium