Chapter 1: Fundamentals

Many problems only care about the most recently seen unfinished item, and a stack hands exactly that item back in O(1). It supports push (add to the top), pop (remove and return the top), and peek (read the top without removing it). In Python a plain list works: append() pushes, pop() pops, and stack[-1] peeks. All three touch only the end of the underlying array, so they are O(1) amortised. Two failure modes recur: popping or peeking an empty stack raises an error, so check if stack: first, and using pop(0) or insert(0, x) quietly turns every operation into O(n).

When function A calls B, the machine must remember A's locals and where to resume once B finishes. It does this with a stack of frames: each call pushes a frame holding arguments, locals, and a return address, and each return pops it. Because the innermost call always finishes first, LIFO is exactly the right order. A recursion of depth d keeps d frames alive at once, so it costs O(d) memory even when it allocates nothing else. The failure mode is stack overflow: CPython caps depth near 1000 by default and raises RecursionError, so very deep recursion should become a loop with an explicit stack.

Given a string of (, ), {, }, [, ], decide whether every opener is closed by its matching closer in the correct nesting order. Counting brackets is not enough, because ([)] has balanced counts but crossed nesting. The fix is to remember the unmatched openers in order: push each opener; on a closer, the stack top must be its partner, so pop and compare. The string is valid only if every closer matched and the stack is empty at the end. Each character is pushed and popped at most once: O(n) time and space. Classic bugs skip the empty-stack check on a closer or the final emptiness test.

Whenever work must be served in arrival order, a queue is the structure that guarantees it. It supports enqueue (add to the back), dequeue (remove from the front), and a peek at the front. Unlike a stack, a queue touches both ends, so the backing store must make both cheap. In Python, collections.deque provides append() and popleft() in O(1) because it is a doubly linked list of fixed-size blocks. The classic failure mode is a plain list with pop(0): every call shifts all remaining elements left, costing O(n), so n dequeues cost O(n^2) and a job that should take milliseconds can take minutes.

To find the fewest moves from a start node to every other node, we must explore all nodes one step away before any node two steps away. Breadth-First Search enforces that ordering with a queue: enqueue the source and mark it visited, then repeatedly dequeue a node and enqueue each unvisited neighbour, marking it visited as it enters. Since the queue always holds distance k before distance k+1, the first discovery of a node follows a shortest path in an unweighted graph. Total work is O(V + E) for V vertices and E edges. A classic bug is marking nodes when dequeued, not enqueued, which floods the queue with duplicates.

Rate limiters and dashboards ask how many requests arrived in the last 3000 milliseconds. Storing every timestamp and rescanning costs O(n) per query. The key observation is that times arrive in increasing order, so once a request falls out of the window $[t - 3000, t]$ it can never re-enter. A queue fits exactly: on ping(t), enqueue t, then dequeue from the front while the front is less than t - 3000; the queue length is the answer. Each timestamp is enqueued once and dequeued at most once, so the amortised cost is O(1) per call. The approach breaks if timestamps can arrive out of order.

Arrays give O(1) access, but only by integer index; a hash map extends that speed to arbitrary keys such as strings or tuples. A hash function $h$ maps each key to an integer, and taking it modulo the table size $m$ picks a bucket between 0 and m - 1. A lookup recomputes $h(k)$ and goes straight there, with no scan. A good hash spreads keys uniformly, so each bucket holds about $\alpha = n/m$ keys on average. Keys must be immutable: if a key's hash changed after insertion, lookups would search the wrong bucket, which is why Python forbids lists as dict keys. Python's dict is a heavily tuned open-addressing table.

Because infinitely many keys map into m buckets, two keys will eventually share an index. Chaining keeps a small list per bucket, so a lookup scans only that list, of expected length $\alpha = n/m$. Open addressing stores everything in the array itself and probes a sequence of slots until it finds the key or an empty slot; expected probes for a miss are about $1/(1-\alpha)$, which explodes as $\alpha$ approaches 1. Both keep O(1) average time only if the table resizes as it fills; Python dicts grow near two-thirds full. A weak or adversarial hash can pile every key into one bucket, giving O(n).

Given an array and a target, find the indices of two numbers that sum to the target. Checking every pair costs $\binom{n}{2}$ comparisons, which is O(n^2). The hash-map insight is to change the question: for the current number x, the only partner that works is its complement, target - x, so instead of searching for pairs we ask whether that complement has already been seen. Walk the array once, and for each x look up the complement in a dict mapping value to index; if found, return both indices, otherwise store x. That is O(n) time and O(n) space. Check before inserting, or x may pair with itself.

Bubble sort is the most direct way to fix disorder: whenever two neighbours are out of order, swap them. One left-to-right pass compares each adjacent pair and swaps when the left is larger, so the largest unsorted element is carried to the end like a rising bubble. After pass k, the last k positions are final, so each later pass can stop earlier. Worst and average cases need about $n^2/2$ comparisons, which is O(n^2). With an early-exit flag, a pass with zero swaps proves the array sorted, giving O(n) on already sorted input. It is stable and in place, but its many swaps make it slow in practice.

Selection sort builds the answer front to back by asking one question per position: which element belongs here? It keeps a sorted prefix and an unsorted suffix; each pass scans the suffix for its minimum and swaps it into the first unsorted slot. The scan always inspects every remaining element, so it performs exactly $n(n-1)/2$ comparisons whatever the input: best, average, and worst cases are all O(n^2). Its one strength is making at most n - 1 swaps, useful when writes are expensive, as on flash memory. Its weaknesses are no adaptivity to sorted input and instability, because a long-distance swap can jump an element over its equal twin.

Insertion sort mirrors sorting a hand of cards: keep the left part sorted and slide each new card leftwards until it sits in place. For index i, save the value, shift every larger element of the sorted prefix one slot right, and drop the value into the gap. The number of shifts equals the number of inversions I, the pairs that are out of order, so the running time is O(n + I). Sorted input has I = 0 and runs in O(n); reverse-sorted input has I = n(n-1)/2 and runs in O(n^2). This adaptivity, plus stability and tiny constant factors, is why Timsort uses insertion sort for short runs.

Suppose a spreadsheet is already ordered by name and you now sort it by grade; you probably expect students with equal grades to stay alphabetical. That expectation is stability: a sort is stable if any two elements with equal keys appear in the output in the same relative order as in the input. Bubble and insertion sort are stable because they only move an element past strictly larger neighbours; selection sort is not, since its long swaps can leapfrog an equal element. Stability enables multi-pass sorting: sort by the secondary key first, then by the primary key, and ties keep the secondary order. Python's sorted() guarantees stability.

When a problem on n items is hard, two problems on n/2 items plus a cheap combine step are often much easier. Divide and conquer has three steps: divide into subproblems, conquer each recursively down to a trivial base case, and combine the answers. Cost follows the recurrence $T(n) = a\,T(n/b) + f(n)$, where a is the number of subproblems, n/b their size, and f(n) the divide-plus-combine work. Merge sort has a = b = 2 and f(n) = O(n), giving O(n log n). Merge sort splits easily and combines hard; quick sort partitions hard and combines trivially. The failure mode is unbalanced splits, where halving degrades into shaving off one element.

Merging two already sorted lists is easy and linear, and merge sort turns sorting into repeated merging. Split the array at the midpoint, recursively sort each half, then merge: keep a pointer at the front of each half, copy the smaller front element to the output, and advance that pointer; when one half runs out, copy the rest of the other. There are log n levels, each doing O(n) merge work, so the cost is $\Theta(n \log n)$ in the best, average, and worst cases. Taking from the left half on ties keeps it stable. The price is an O(n) auxiliary buffer, which matters when memory is tight.

Quick sort avoids merge sort's buffer by doing the work before recursing. Choose a pivot, then partition the array in place so smaller elements sit left of the pivot and larger ones sit right; the pivot is now in its final position, so recurse on the two sides and no combine step is needed. Balanced splits give O(n log n), and a random pivot yields about $2n \ln n$ comparisons on average. The failure mode is a bad pivot: always picking the smallest element, as a first-element pivot does on sorted input, gives the recurrence $T(n) = T(n-1) + O(n)$ and O(n^2) time. It is in place but not stable.

Most custom orders are really the default order applied to a derived value: a string's length, a record's date, a lowercase name. A key function captures that: sorted(xs, key=f) computes f(x) once per element and sorts elements by comparing those keys with the normal less-than. Typical keys are len, str.lower, and lambda r: r[1]. Calling the key n times, instead of on every one of the O(n log n) comparisons, is why keys beat comparison functions on speed. Keys must be mutually comparable: mixing None with integers raises TypeError in Python 3. Because Python's sort is stable, elements with equal keys keep their input order.

Leaderboards and reports need a primary order plus tie-breakers, and a key can return a tuple to express all of them at once. Python compares tuples lexicographically: the first elements decide, and only on a tie does it look at the second, and so on. So key=lambda s: (-s.score, s.name) gives score descending, then name ascending. Negation reverses numeric fields but not strings; for a descending string field, use stable multi-pass sorting instead: sort by the secondary key first, then by the primary key with reverse=True. Common bugs are negating a string, which raises TypeError, and forgetting a tie-breaker, which leaves ties in arbitrary input order.

Some orders cannot be computed from one element alone: whether a should precede b depends on both. The largest-number puzzle is the classic case, since 9 must precede 34 but the rule is about how the digits concatenate. A comparison function cmp(a, b) returns a negative number if a goes first, zero on a tie, and a positive number otherwise, and functools.cmp_to_key(cmp) wraps it so sorted can use it. It runs O(n log n) times, so it is slower than a key. It must be consistent: antisymmetric and transitive, so a before b and b before c imply a before c. Violations make results depend on input order.