Arrays, Hash Tables & Heaps

Choosing the right data structure — array, hash table, or heap — is often the entire solution to a quant-dev problem.

1. The idea

Arrays give $O (1)$ indexed access but $O (n)$ insertion/deletion in the middle. They're the right choice when you need fast random access and the size is known or append-only at the end.

Hash tables (hash sets/maps) give expected $O (1)$ insertion, deletion, and lookup by key, at the cost of no ordering and, in rare worst cases, $O (n)$ per operation due to collisions. They're the go-to structure for 'have I seen this before' or 'count occurrences' problems.

Heaps (priority queues) give $O (lo g n)$ insertion and removal of the min (or max) element, and $O (1)$ peek at the min/max. They're ideal when you repeatedly need the current smallest/largest element from a changing collection, such as in Dijkstra's algorithm or running medians via a two-heap approach.

2. Why it matters

Quant-dev interviews are frequently 'pick the right data structure' problems in disguise — the correct choice often turns an $O (n^{2})$ solution into $O (n lo g n)$ or $O (n)$ .

3. Core mathematics

Array access / append

O (1)

Amortized O(1) for append with dynamic resizing

Hash table operations

O (1) expected, O (n) worst case

Heap insert / extract-min

O (lo g n)

Heap build from n elements

O (n)

Bottom-up heapify is linear, faster than n inserts

4. How to recognize it

Think of this when…

Asks for the k largest/smallest elements, or a running max/min
Involves checking membership or counting frequency quickly
Needs ordered removal of the current extreme element repeatedly

5. Worked example

Worked example

Given a stream of numbers, maintain the k largest values seen so far, supporting fast updates. What structure and complexity?

1
Use a min-heap of size k: the heap's minimum is the smallest of the current top-k.
$heap size = k$
2
For each new number, if it's larger than the heap's min (or heap has fewer than k elements), push it and pop the min if size exceeds k.
$O (lo g k) per update$
Answer: A size-k min-heap gives O(log k) per update and O(1) to report the current kth largest (the heap's min), versus O(n log n) if re-sorting each time.

6. Common mistakes

Using a max-heap of the whole stream instead of a size-limited min-heap, wasting memory and time
Assuming hash table operations are always O(1) without noting the worst-case collision behavior
Choosing an array with linear search when a hash set would give O(1) membership checks

7. Quick check

To repeatedly extract the minimum from a changing set efficiently, use a:

Expected time for hash table insertion and lookup is:

8. Practice

6 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Dynamic Programming / Continuation Value

Create a free account to save lesson progress.

Recommended next lessonBinary Search →