Data Structures: Your Toolbox

Part II of this course goes beyond the core 18 patterns into the structures and algorithms that separate strong candidates from the rest. We start with a consolidating reference, because almost every interview problem reduces to one question: which data structure gives me the operation I need cheaply? Get the trade-offs into your bones and the right tool jumps out before you have even finished reading the prompt.

The idea

A data structure is a deal: you spend memory and setup time to make one kind of operation fast. Picking well is most of the battle. Here is the whole toolbox, from the everyday structures to the three advanced ones that unlock a surprising number of hard problems.

The everyday structures

Array / string — contiguous memory. Random access by index is O(1); search is O(n); inserting in the middle is O(n) because everything shifts. This is your default container, and in Python a list doubles as a stack.

Hash map / set — the workhorse of coding interviews. Average O(1) insert, delete, and lookup by trading memory for speed. Reach for it whenever you catch yourself about to do a nested loop to “find a matching element” — a hash map usually collapses O(n²) to O(n). (This is the whole Two-Sum insight from Lesson 6.)

Stack & queue — a stack is last-in-first-out (use a list); a queue is first-in-first-out (use collections.deque for O(1) pops from the front). A monotonic stack or deque — one you keep sorted as you push — gives next-greater-element and sliding-window-maximum answers in O(n) (Lessons 4 and 9).

from collections import deque
q = deque([1, 2, 3])
q.append(4)        # push right  — O(1)
q.popleft()        # pop left    — O(1)

Linked list — nodes joined by pointers. The one thing it does better than an array is O(1) insertion or deletion at a node you already hold, with no shifting. The price is no random access (finding the k-th node is O(n)). This is why the reversal and fast/slow-pointer patterns (Lessons 5 and 11) exist.

Binary heap / priority queue — keeps the minimum (or maximum) instantly available. heapq is a min-heap: heappush/heappop are O(log n) and the smallest element is always heap[0] in O(1). Perfect for “top-K”, “k-th largest”, and merging sorted streams (Lesson 14).

import heapq
h = []
heapq.heappush(h, 5); heapq.heappush(h, 1); heapq.heappush(h, 3)
heapq.heappop(h)   # -> 1   (always the smallest)

BST / balanced tree — a binary search tree keeps elements ordered, giving O(log n) search, insert, and delete when balanced (an unbalanced BST degrades to O(n) — a linked list in disguise). Python has no built-in balanced tree; in interviews you either implement BST logic directly (Lesson 13) or reach for a sorted structure like sortedcontainers.SortedList when allowed.

The advanced trio

These three show up in the harder questions, and each is the subject of its own lesson ahead.

Trie (prefix tree) — a tree keyed by characters, so words with shared prefixes share a path. Insert and search a word in O(length), independent of how many words are stored. The tool for autocomplete, dictionary lookups, and prefix queries (Lesson 20).

Union-Find (disjoint set) — answers “are these two things in the same group?” and merges groups, each in near-O(1) time with path compression and union by rank. The go-to for connectivity, counting components, and cycle detection as edges arrive.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        self.parent[self.find(a)] = self.find(b)

Fenwick tree (BIT) / segment tree — when you need both range queries (sum, min, max over a range) and point updates, and a prefix-sum array is too slow to update, these give both in O(log n). A Fenwick tree is the compact choice for prefix sums with updates:

class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)
    def update(self, i, delta):          # add delta at index i (1-based)
        while i < len(self.tree):
            self.tree[i] += delta; i += i & (-i)
    def query(self, i):                  # prefix sum of [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]; i -= i & (-i)
        return s
# Fenwick over [a,b] range sum = query(b) - query(a-1); each op O(log n)

The complexity cheat-sheet

When to reach for it

The mapping from problem phrasing to structure is the real skill:

• “find a pair / have I seen this” → hash map/set.
• “most recent / matching brackets / next greater” → stack.
• “shortest unweighted / level by level” → queue.
• “k largest / smallest / most frequent” → heap.
• “prefix / starts-with / autocomplete” → trie.
• “are these connected / number of groups” → union-find.
• “range sum/min with updates” → Fenwick or segment tree.

Pitfalls

• Unbalanced BST. A plain BST built from sorted input degrades to O(n). If you need guaranteed O(log n), say “balanced” out loud and use the right structure.
• Heap is not searchable. A heap gives you the extreme in O(1) but finding or removing an arbitrary element is O(n). Use the right tool for the query you actually have.
• Reaching for a segment tree too early. If there are no updates, a plain prefix-sum array answers range queries in O(1) with far less code. Only pay for a Fenwick/segment tree when values change.

Recap

Every structure is a trade: memory and setup for one cheap operation. Arrays give O(1) indexing; hash maps give O(1) lookup; stacks/queues give O(1) ends; heaps give the extreme in O(1); BSTs keep order in O(log n); and the advanced trio — trie (prefix O(len)), union-find (connectivity ~O(1)), and Fenwick/segment tree (range + update O(log n)) — unlock the hard problems. Know the table cold and justify your choice out loud; that is exactly the reasoning interviewers are listening for.

Next: Lesson 20 — Tries (Prefix Trees), the first of the advanced structures.