Data structures,
in motion.

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// bench_test.go — the only honest way to compare two implementations.
// Run: go test -bench=. -benchmem -count=6 ./... | tee new.txt
//      benchstat old.txt new.txt   # tells you whether the difference is real
func BenchmarkContains(b *testing.B) {
    for _, n := range []int{16, 256, 4096, 65536} {
        haystack := rand.Perm(n)
        set := make(map[int]struct{}, n)
        for _, v := range haystack {
            set[v] = struct{}{}
        }
        needle := n - 1                          // worst case for the scan

        b.Run(fmt.Sprintf("slice/%d", n), func(b *testing.B) {
            for b.Loop() {                       // Go 1.24+; b.N loop before that
                _ = slices.Contains(haystack, needle)
            }
        })
        b.Run(fmt.Sprintf("map/%d", n), func(b *testing.B) {
            for b.Loop() {
                _, _ = set[needle]
            }
        })
    }
}

// slice/16      6.1 ns    map/16      5.4 ns   <-- no difference worth having
// slice/65536  21400 ns   map/65536   5.6 ns   <-- three orders of magnitude
// The crossover, not the asymptote, is what decides your design.

# bench.py — timeit, because a stopwatch around one call measures the clock.
import random
import timeit

def compare(n: int) -> None:
    haystack = random.sample(range(n * 4), n)
    hay_set = set(haystack)
    needle = haystack[-1]                        # worst case for the scan

    # number= is chosen so each variant runs for a measurable stretch;
    # repeat() then takes the *minimum*, which is the least noisy statistic.
    seq = min(timeit.repeat(lambda: needle in haystack, number=1000, repeat=7))
    hsh = min(timeit.repeat(lambda: needle in hay_set, number=1000, repeat=7))
    print(f"n={n:>6}  list {seq * 1e6:7.1f} us   set {hsh * 1e6:6.1f} us   "
          f"ratio {seq / hsh:6.1f}x")

for n in (16, 256, 4096, 65536):
    compare(n)

# n=    16  list     6.9 us   set    3.4 us   ratio    2.0x
# n= 65536  list 21500.0 us   set    3.5 us   ratio 6100.0x
#
# `in` on a list is O(n) and `in` on a set is O(1). Identical syntax,
# different curve. This is the single most common accidental O(n^2)
# in Python: a membership test on a list inside a loop over another list.

// ContainsBench.java — JMH, because the JIT will happily delete a loop
// whose result nobody uses, and then you benchmark nothing at all.
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Fork(value = 2, warmups = 1)
@Warmup(iterations = 5)                          // let C2 compile and settle
@Measurement(iterations = 8)
public class ContainsBench {

    @Param({"16", "256", "4096", "65536"})
    public int n;

    private List<Integer> list;
    private Set<Integer> set;
    private Integer needle;

    @Setup
    public void setUp() {
        list = ThreadLocalRandom.current().ints(n, 0, n * 4).boxed().toList();
        set = new HashSet<>(list);
        needle = list.get(n - 1);                 // worst case for the scan
    }

    // Returning the value hands it to the Blackhole, so it cannot be
    // optimised away. This is the whole reason to use JMH over a loop and
    // System.nanoTime().
    @Benchmark public boolean listContains() { return list.contains(needle); }
    @Benchmark public boolean setContains()  { return set.contains(needle); }
}

// layout.go — identical asymptotics, very different machines.

type Node struct {                               // 24 bytes of payload,
    Value int64                                  // plus an 8-byte pointer,
    Next  *Node                                  // plus allocator overhead,
}                                                // scattered across the heap

func SumList(head *Node) int64 {
    var total int64
    for n := head; n != nil; n = n.Next {        // one cache miss per hop
        total += n.Value
    }
    return total
}

func SumSlice(xs []int64) int64 {
    var total int64
    for _, v := range xs {                       // 8 values per cache line,
        total += v                               // and the next line is already
    }                                            // on its way
    return total
}

// n = 10,000,000 on a warm machine:
//   SumSlice   6.8 ms      SumList   402 ms      59x, same O(n)
//
// A []Node (values, not pointers) recovers most of the gap. Prefer
// slices of structs to slices of pointers unless you need identity or
// the elements are genuinely large.

# layout.py — in Python every int in a list is already a pointer, so the
# question is not "list or linked list" but "objects or a buffer".
import array
import sys

xs = list(range(1_000_000))                      # 8 MB of pointers ...
buf = array.array("q", range(1_000_000))         # ... plus ~28 bytes per int

print(sys.getsizeof(xs) / 1e6, "MB of pointers")         # 8.06
print(sys.getsizeof(buf) / 1e6, "MB, values inline")     # 8.00, and that is all

# sum(xs)  ~4.5 ms   -- dereference, unbox, add, per element
# sum(buf) ~9.0 ms   -- array.array re-boxes on the way out, so this is
#                       *slower* despite the better layout: the win is
#                       memory, not speed
#
# numpy is the version that gets both, because the loop moves into C:
#   np.arange(1_000_000).sum()   ~0.4 ms, 8 MB, one pass, no boxing.
#
# The lesson is not "use numpy". It is that CPython's data model puts a
# pointer hop between you and every value, so the constant factor on a
# pure-Python O(n) loop is ~100x a compiled one. Choose the algorithm
# first; then choose whether the loop should run in Python at all.

// Layout.java — the difference between a value and a reference to one.

// Every element here is a pointer to a boxed Integer somewhere on the
// heap: 16 bytes of header plus 4 of payload, scattered by the allocator.
List<Integer> boxed = IntStream.range(0, 10_000_000).boxed().toList();

// Here the values are the array. One allocation, 40 MB, perfectly linear.
int[] flat = IntStream.range(0, 10_000_000).toArray();

long sumBoxed(List<Integer> xs) {
    long total = 0;
    for (Integer x : xs) total += x;             // deref + unbox per element
    return total;
}

long sumFlat(int[] xs) {
    long total = 0;
    for (int x : xs) total += x;                 // 16 ints per cache line
    return total;
}

// sumFlat    ~7 ms       sumBoxed   ~95 ms      13x, same O(n)
//
// Integer caches -128..127, so small-value benchmarks look far better
// than production. Use int[], long[] and double[] on hot paths, and
// reach for the primitive streams (IntStream, LongStream) rather than
// Stream<Integer>.

// stack.go — Go grows goroutine stacks on demand (2 KB start, up to
// 1 GB by default), so deep recursion usually *works* and then abruptly
// does not, with "goroutine stack exceeds limit" and no recovery.

func SumRec(n *Node) int64 {                     // O(depth) stack
    if n == nil {
        return 0
    }
    return n.Value + SumRec(n.Next)              // not a tail call: Go has none
}

// The iterative form is the same algorithm with the frames deleted.
func SumIter(n *Node) int64 {                    // O(1) stack
    var total int64
    for ; n != nil; n = n.Next {
        total += n.Value
    }
    return total
}

// For trees, where iteration is genuinely less clear, carry your own
// stack. It is a slice, it costs one allocation, and it cannot overflow
// before the heap does.
func InOrder(root *TreeNode, visit func(int)) {
    stack := make([]*TreeNode, 0, 32)
    for cur := root; cur != nil || len(stack) > 0; {
        for ; cur != nil; cur = cur.Left {
            stack = append(stack, cur)           // walk left, remembering
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        visit(cur.Val)
        cur = cur.Right
    }
}

# stack.py — CPython's limit is a *guard*, not the real stack size.
import sys

sys.getrecursionlimit()                          # 1000 by default

# Raising it does not give you more C stack; it removes the check that
# was protecting you from a hard segfault. Since 3.12 pure-Python frames
# no longer consume C stack, which helps -- but the ceiling is still
# finite and the failure below it is much less friendly.
sys.setrecursionlimit(20_000)                    # a smell, not a fix

def in_order_recursive(node, out):               # O(depth) frames
    if node is None:
        return
    in_order_recursive(node.left, out)
    out.append(node.val)
    in_order_recursive(node.right, out)

def in_order(root):                              # O(depth) list, no frames
    out, stack, cur = [], [], root
    while cur is not None or stack:
        while cur is not None:                   # walk left, remembering
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right
    return out

# A balanced tree of a million nodes is 20 deep and recursion is fine.
# A million-node tree built by inserting sorted keys is a linked list
# 1,000,000 deep, and only the iterative version survives it. Which one
# you have depends on data you do not control.

// Stack.java — the JVM gives each thread a fixed stack, default about
// 512 KB to 1 MB. Deep recursion throws StackOverflowError, which is an
// Error, not an Exception: do not catch it and carry on.

// -Xss4m raises it per thread. That is a workaround with a cost:
// thousands of threads at 4 MB of reserved stack each adds up fast.

void inOrderRecursive(TreeNode node, List<Integer> out) {   // O(depth) frames
    if (node == null) return;
    inOrderRecursive(node.left, out);
    out.add(node.val);
    inOrderRecursive(node.right, out);
}

List<Integer> inOrder(TreeNode root) {                      // O(depth) heap
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {                                // walk left, remembering
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    return out;
}

// Use ArrayDeque, never java.util.Stack: Stack extends Vector, so every
// push and pop is synchronised and it exposes indexed access into the
// middle of a stack, which is not a thing a stack should have.

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// slice.go — a slice is a 24-byte header: pointer, length, capacity.
// Copying a slice copies the header, not the elements. This is the
// source of most Go slice surprises.

xs := make([]int, 0, 1024)                       // len 0, cap 1024: zero reallocations
for i := range 1024 {                            // for the next 1024 appends
    xs = append(xs, i)
}

// If you know the size, allocate it once. This is the single highest-
// value habit in Go performance work, and it is one argument.
out := make([]string, 0, len(in))                // not: var out []string
for _, v := range in {
    out = append(out, transform(v))
}

// Deleting: O(n) if order matters, O(1) if it does not.
xs = slices.Delete(xs, i, i+1)                   // shifts the tail down
xs[i] = xs[len(xs)-1]; xs = xs[:len(xs)-1]       // swap-remove, order lost

// The trap: append may or may not share the backing array. Whether the
// caller sees your writes depends on capacity, which is not in the type.
func bad(xs []int) { xs = append(xs, 1) }        // caller may or may not see it

// A three-index slice caps the capacity, so append is forced to copy
// and can never scribble on the parent's tail.
head := xs[0:5:5]                                // len 5, cap 5

// Sub-slicing keeps the WHOLE backing array alive. Holding one small
// slice of a 100 MB read is a 100 MB leak; slices.Clone breaks it.
small := slices.Clone(big[:10])

# list.py — a CPython list is a growable array of pointers. Every
# element costs 8 bytes in the array plus the object it points at.

xs = [0] * 1024                                  # preallocated, one allocation
xs = list(range(1024))                           # also one, and it knows the size

# A comprehension beats append-in-a-loop: same complexity, better
# constant, because it skips the method lookup and call per item.
out = [transform(v) for v in src]                # preferred

# O(n) operations that look O(1):
xs.insert(0, v)                                  # shifts every element
xs.pop(0)                                        # same
del xs[3]                                        # same
v in xs                                          # linear scan

# Building a queue out of a list is the most common O(n^2) in Python.
# collections.deque is a doubly linked list of 64-slot blocks, so both
# ends are O(1) and it still has decent locality.
from collections import deque
q = deque(maxlen=1000)                           # and it can be a ring buffer
q.append(v); q.popleft()                         # both O(1)

# The mutable-default and shared-reference traps, which are the same bug:
grid = [[0] * 3] * 3                             # three references to ONE row
grid[0][0] = 1                                   # -> [[1,0,0],[1,0,0],[1,0,0]]
grid = [[0] * 3 for _ in range(3)]               # three distinct rows

# Slicing copies. xs[:] is an O(n) copy, not a view -- which is exactly
# what you want for safe iteration while mutating, and exactly what you
# do not want in a loop.
for v in xs[:]:                                  # iterate a snapshot
    if drop(v):
        xs.remove(v)                             # O(n) each -- see the note below

// Lists.java — ArrayList wraps an Object[]. Growth is 1.5x, and the
// grow-copy uses Arrays.copyOf, which is an intrinsic (a memcpy).

List<String> out = new ArrayList<>(in.size());   // size it if you know it
for (String v : in) out.add(transform(v));

// O(n) operations on an ArrayList, all of them System.arraycopy:
list.add(0, v);                                  // shifts everything right
list.remove(0);                                  // shifts everything left
list.contains(v);                                // linear scan with equals()

// Removing inside an enhanced for loop throws ConcurrentModification-
// Exception. removeIf does it in one O(n) pass, which is both correct
// and asymptotically better than remove() in a loop.
list.removeIf(v -> drop(v));

// The three "lists" that are not what you want:
//   Vector      - synchronised on every call, legacy
//   LinkedList  - O(1) at the ends, but terrible locality; use ArrayDeque
//   Arrays.asList(a) - a fixed-size VIEW of the array; add() throws

// Since Java 9, List.of is immutable, rejects nulls, and is compact.
// Since 10, copyOf snapshots. Prefer both to hand-rolled defensive copies.
List<String> fixed = List.of("a", "b", "c");
List<String> snapshot = List.copyOf(mutable);

// And for hot numeric paths, none of the above: int[] has no boxing,
// no headers, and sixteen elements per cache line.
int[] counts = new int[n];

// list.go — the two techniques worth memorising, both of them pointer
// discipline rather than cleverness.

type Node struct {
    Val  int
    Next *Node
}

// 1. Reverse in place. Three pointers, one pass, no allocation.
func Reverse(head *Node) *Node {
    var prev *Node
    for cur := head; cur != nil; {
        next := cur.Next                         // remember before clobbering
        cur.Next = prev                          // flip
        prev, cur = cur, next                    // advance both
    }
    return prev                                  // prev is the old tail
}

// 2. Floyd's cycle detection. Fast moves two, slow moves one; if there
// is a loop they must meet inside it, in O(n) time and O(1) space.
// Restarting one pointer at the head then advancing both one step at a
// time lands them on the entry to the cycle -- that part is not obvious,
// and it falls out of the arithmetic of where they met.
func CycleStart(head *Node) *Node {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast {                        // a cycle exists
            for p := head; p != slow; p, slow = p.Next, slow.Next {
            }
            return slow                          // the node the loop enters at
        }
    }
    return nil
}

// A dummy head node removes every "is this the first element" branch
// from insert and delete. Use one; the code halves in size.

# linked.py — you will almost never write one of these in Python, but
# the two techniques generalise to every sequence you cannot index.
from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    next: Optional["Node"] = None

def reverse(head: Optional[Node]) -> Optional[Node]:
    prev = None
    while head is not None:
        head.next, prev, head = prev, head, head.next   # one line, one pass
    return prev

def cycle_start(head: Optional[Node]) -> Optional[Node]:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                         # identity, not equality
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

# The real-world version of this structure is an LRU cache, and the
# standard library already has one -- built on exactly a dict plus a
# circular doubly linked list, in C.
from functools import lru_cache

@lru_cache(maxsize=1024)                         # O(1) get, O(1) evict
def expensive(key: str) -> int:
    ...

# functools.cache is lru_cache(maxsize=None): unbounded, so it is a
# memory leak with a friendly name unless the key space is finite.

// Lists2.java — LinkedHashMap gives you the LRU cache in six lines,
// because it maintains exactly the hash-map-plus-linked-list structure
// you would otherwise build by hand.

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int cap;

    LruCache(int cap) {
        super(16, 0.75f, /* accessOrder = */ true);   // the whole trick
        this.cap = cap;
    }

    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cap;                     // evict on the way out of put()
    }
}

// accessOrder=true moves an entry to the end of the list on every get,
// which is the O(1) move-to-front an array cannot do. With it false
// (the default) you get insertion order, which is what you want when
// the map is really an ordered record rather than a cache.

// java.util.LinkedList exists and you should almost never use it. It is
// a doubly linked list with an object header and two pointers per
// element, and its get(i) is O(n) despite implementing List. For a
// queue or a stack use ArrayDeque, which is a growable ring buffer:
Deque<Task> queue = new ArrayDeque<>();
queue.addLast(t);                                // enqueue
Task next = queue.pollFirst();                   // dequeue, null if empty

// deque.go — Go has no deque type. A slice is a fine stack; for a queue
// with bounded memory, write the ring buffer, it is thirty lines.

// Stack: a slice, and that is the whole implementation.
stack = append(stack, v)                         // push
v, stack = stack[len(stack)-1], stack[:len(stack)-1]  // pop

// Queue: the naive version leaks. `q = q[1:]` advances the pointer but
// keeps the whole backing array alive, so a long-running queue grows
// without bound even at constant depth.
type Ring[T any] struct {
    buf        []T
    head, tail int
    n          int
}

func NewRing[T any](cap int) *Ring[T] { return &Ring[T]{buf: make([]T, cap)} }

func (r *Ring[T]) Push(v T) bool {
    if r.n == len(r.buf) {
        return false                             // full: caller decides — block,
    }                                            // drop, or grow
    r.buf[r.tail] = v
    r.tail = (r.tail + 1) % len(r.buf)
    r.n++
    return true
}

func (r *Ring[T]) Pop() (T, bool) {
    var zero T
    if r.n == 0 {
        return zero, false
    }
    v := r.buf[r.head]
    r.buf[r.head] = zero                         // release the reference, or the
    r.head = (r.head + 1) % len(r.buf)           // GC keeps the popped object
    r.n--
    return v, true
}

// In practice a buffered channel is Go's ring buffer, with the locking
// already done: make(chan T, 1024).

# deque.py — collections.deque is O(1) at both ends and written in C.
from collections import deque

stack = []                                       # a list IS the right stack
stack.append(v); v = stack.pop()                 # both O(1) amortised

q = deque()                                      # the right queue
q.append(v); v = q.popleft()                     # both O(1)

# maxlen turns it into a ring buffer that silently drops from the far
# end -- exactly what you want for "the last 1000 log lines".
recent = deque(maxlen=1000)

def window_max(nums: list[int], k: int) -> list[int]:
    """Maximum of every window of size k, in O(n) total.

    The deque holds *indices* whose values are strictly decreasing, so
    the front is always the current maximum. Each index enters once and
    leaves once, which is where the linear bound comes from.
    """
    dq: deque[int] = deque()
    out = []
    for i, v in enumerate(nums):
        while dq and dq[0] <= i - k:             # front fell out of the window
            dq.popleft()
        while dq and nums[dq[-1]] <= v:          # everything smaller is dead:
            dq.pop()                             # v is newer AND bigger
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

# A heap would also work and would be O(n log k). The deque is O(n),
# because it never reconsiders an element it has thrown away.

// Deques.java — ArrayDeque is the one to reach for: a growable ring
// buffer, no synchronisation, faster than LinkedList and than Stack.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(v);                                   // addFirst
int top = stack.pop();                           // removeFirst, throws if empty

Deque<Task> queue = new ArrayDeque<>();
queue.offer(t);                                  // addLast, false if capacity-bound
Task next = queue.poll();                        // removeFirst, null if empty

// Learn the pairs: add/remove/element throw on failure, offer/poll/peek
// return a sentinel. Mixing them is how a queue ends up throwing
// NoSuchElementException in production at 3 a.m.

int[] windowMax(int[] nums, int k) {             // O(n), monotonic deque
    int[] out = new int[nums.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();      // holds indices, values decreasing
    for (int i = 0; i < nums.length; i++) {
        while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
        dq.addLast(i);
        if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()];
    }
    return out;
}

// For producer/consumer across threads, none of the above: use
// ArrayBlockingQueue (bounded, so it applies backpressure) or
// LinkedBlockingQueue. An unbounded queue in front of a slow consumer
// is an OutOfMemoryError with extra steps.

// maps.go — Go 1.24 replaced the old bucketed map with Swiss tables:
// open addressing, SIMD probing of 8 slots at a time, better locality.
// The semantics did not change; the constant did.

counts := make(map[string]int, len(words))       // size the hint if you know it
for _, w := range words {
    counts[w]++                                  // zero value: no "if absent" branch
}

// The comma-ok form is the only way to tell "absent" from "present and
// zero". If that distinction matters, you must use it.
if v, ok := counts[w]; ok {
    use(v)
}

// A set is a map to the empty struct, which occupies no space at all.
seen := make(map[string]struct{}, n)
seen[w] = struct{}{}
_, dup := seen[w]

// You cannot take the address of a map element, because a resize moves
// it. Store pointers if you need to mutate in place.
//   m[k].field = v          // compile error for a struct value
type Row struct{ Hits int }
m := map[string]*Row{}
m[k] = &Row{}; m[k].Hits++                       // fine: the pointer is stable

// Iteration order is randomised on purpose. Sort the keys when you need
// determinism -- in tests, in output, in anything hashed downstream.
for _, k := range slices.Sorted(maps.Keys(counts)) {
    fmt.Println(k, counts[k])
}

// Maps never shrink. Deleting every key frees the entries but keeps the
// buckets; a map that peaked at ten million holds that memory until it
// is replaced with a fresh one.

# dicts.py — a CPython dict is a compact index array plus a dense entry
# array, which is why it preserves insertion order essentially for free.
from collections import Counter, defaultdict

counts = Counter(words)                          # one pass, C speed
counts.most_common(10)                           # heapq under the hood, O(n log k)

# defaultdict removes the "if key not in d" branch. The factory is
# called on a MISSING KEY LOOKUP, so a plain read inserts:
groups = defaultdict(list)
for item in items:
    groups[item.kind].append(item)               # no setdefault dance
_ = groups["never-seen"]                         # this just created an entry

# setdefault is the non-mutating-on-read alternative, at the cost of
# building the default every call.
groups.setdefault(k, []).append(v)

# Sets are dicts without values, and the set algebra is the reason to
# reach for them: all of these are O(len of the smaller side).
new = incoming - known                           # difference
both = incoming & known                          # intersection

# The hashability rule, which is really an immutability rule:
{[1, 2]: "x"}                                    # TypeError: unhashable type 'list'
{(1, 2): "x"}                                    # fine -- tuples are immutable

# A dataclass is unhashable once it is mutable, and that is deliberate:
#   @dataclass(frozen=True)  -> hashable, safe as a key
#   @dataclass               -> eq=True sets __hash__ = None

# str and bytes hashes are randomised per process (PYTHONHASHSEED), so
# never persist a hash() value or expect it to match across runs.

// Maps.java — HashMap is an array of bins; a bin is a linked list until
// it reaches 8 entries in a table of at least 64, at which point it
// becomes a red-black tree. That is the collision insurance policy.

Map<String, Integer> counts = new HashMap<>();
for (String w : words) counts.merge(w, 1, Integer::sum);   // the idiom

// computeIfAbsent for grouping; the value is built once, on first use.
Map<Kind, List<Item>> groups = new HashMap<>();
for (Item it : items) groups.computeIfAbsent(it.kind(), k -> new ArrayList<>()).add(it);

// getOrDefault does NOT insert; get() returning null is ambiguous when
// null is a legal value, which is one reason not to store nulls.
int n = counts.getOrDefault(w, 0);

// THE contract: equals and hashCode must agree, and both must be stable
// for as long as the object is a key. A record gives you both, derived
// from the components, and is immutable -- so records are the correct
// default for map keys.
record CacheKey(String tenant, long id) {}       // equals + hashCode for free

// Mutating a key after insertion loses the entry: it hashes to a
// different bin, so get() misses and remove() cannot find it either.
// The entry is still there, holding memory, forever.

// Ordering, when you need it:
//   LinkedHashMap - insertion (or access) order, O(1) like HashMap
//   TreeMap       - sorted by key, O(log n), and gives you range queries
//   ConcurrentHashMap - the one to use across threads; NOT synchronized-
//                       Map, which locks the whole table on every call

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// tree.go — the three orders, then the two things you actually compute.

type TreeNode struct {
    Val         int
    Left, Right *TreeNode
}

func Walk(n *TreeNode, visit func(int)) {
    if n == nil {
        return
    }
    // visit(n.Val)          <- pre-order goes here
    Walk(n.Left, visit)
    visit(n.Val)                                 // in-order
    Walk(n.Right, visit)
    // visit(n.Val)          <- post-order goes here
}

// Level order: a queue, and one loop per level so you know where the
// rows break. That inner "for range len(q)" is the whole trick.
func Levels(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    var out [][]int
    q := []*TreeNode{root}
    for len(q) > 0 {
        row := make([]int, 0, len(q))
        next := make([]*TreeNode, 0, len(q)*2)
        for _, n := range q {                    // exactly one level
            row = append(row, n.Val)
            if n.Left != nil {
                next = append(next, n.Left)
            }
            if n.Right != nil {
                next = append(next, n.Right)
            }
        }
        out, q = append(out, row), next
    }
    return out
}

// Height is post-order: you cannot know yours until both children know
// theirs. Almost every "compute something about a subtree" is this shape.
func Height(n *TreeNode) int {
    if n == nil {
        return 0
    }
    return 1 + max(Height(n.Left), Height(n.Right))
}

# tree.py — a generator makes the traversal lazy, which matters when
# the caller wants the first match rather than all of them.
from collections import deque
from typing import Iterator, Optional

class Node:
    __slots__ = ("val", "left", "right")         # no __dict__: ~40% less memory

    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def in_order(n: Optional[Node]) -> Iterator[int]:
    if n is None:
        return
    yield from in_order(n.left)
    yield n.val                                  # move this line for pre/post
    yield from in_order(n.right)

def levels(root: Optional[Node]) -> list[list[int]]:
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        row = []
        for _ in range(len(q)):                  # snapshot the level's width
            n = q.popleft()
            row.append(n.val)
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        out.append(row)
    return out

# The generator version composes with everything: itertools.islice for
# the first k, next() for the first match, zip() to compare two trees.
first_over_100 = next((v for v in in_order(root) if v > 100), None)

# On a search tree this stops as soon as it finds one, because in_order
# is lazy -- the recursive list-building version would walk it all.

// Trees.java — records make an immutable tree pleasant, and sealed
// interfaces let the compiler check that you handled every shape.

sealed interface Tree permits Leaf, Branch {}
record Leaf() implements Tree {}
record Branch(int val, Tree left, Tree right) implements Tree {}

// Pattern matching in a switch: exhaustive, so a new variant is a
// compile error rather than a runtime surprise.
static int height(Tree t) {
    return switch (t) {
        case Leaf ignored -> 0;
        case Branch b -> 1 + Math.max(height(b.left()), height(b.right()));
    };
}

static void inOrder(Tree t, IntConsumer visit) {
    if (t instanceof Branch b) {
        inOrder(b.left(), visit);
        visit.accept(b.val());                   // move for pre/post order
        inOrder(b.right(), visit);
    }
}

static List<List<Integer>> levels(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>(List.of(root));
    while (!q.isEmpty()) {
        int width = q.size();                    // snapshot before adding children
        List<Integer> row = new ArrayList<>(width);
        for (int i = 0; i < width; i++) {
            TreeNode n = q.poll();
            row.add(n.val);
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        out.add(row);
    }
    return out;
}

// sorted.go — Go has no ordered map, and for most workloads it does not
// need one: a sorted slice with binary search beats a pointer-based tree
// on every operation except insert-in-the-middle, because it is
// contiguous.

type Index struct {
    keys []string                                // kept sorted
    vals []Record                                // parallel
}

func (ix *Index) Get(k string) (Record, bool) {
    i, ok := slices.BinarySearch(ix.keys, k)     // O(log n)
    if !ok {
        return Record{}, false
    }
    return ix.vals[i], true
}

// The insertion point is the answer to "the first key >= k" -- the same
// lower_bound that TreeMap.ceilingKey gives you.
func (ix *Index) Range(lo, hi string) []Record {
    a, _ := slices.BinarySearch(ix.keys, lo)     // first >= lo
    b, _ := slices.BinarySearch(ix.keys, hi)     // first >= hi
    return ix.vals[a:b]
}

func (ix *Index) Put(k string, v Record) {
    i, ok := slices.BinarySearch(ix.keys, k)
    if ok {
        ix.vals[i] = v
        return
    }
    ix.keys = slices.Insert(ix.keys, i, k)       // O(n) memmove -- fast per
    ix.vals = slices.Insert(ix.vals, i, v)       // byte, but O(n)
}

// Rule of thumb: read-mostly, up to a few hundred thousand entries, use
// the slice. Write-heavy or larger, use a B-tree package. A hand-rolled
// red-black tree is the wrong answer at every size.

# sorted.py — bisect is the standard library's ordered structure, and it
# is a pair of functions rather than a class, so it works on any list.
import bisect

keys = []                                        # kept sorted

bisect.insort(keys, k)                           # O(log n) search + O(n) insert

i = bisect.bisect_left(keys, k)                  # first index with keys[i] >= k
found = i < len(keys) and keys[i] == k

lo = bisect.bisect_left(keys, "2026-01-01")      # range query on a sorted list
hi = bisect.bisect_right(keys, "2026-01-31")     # is two bisects and a slice
window = keys[lo:hi]

# bisect takes a key= function since 3.10, so you can index objects
# without building a parallel list of keys.
i = bisect.bisect_left(events, when, key=lambda e: e.timestamp)

# The percentile / bucketing idiom: find which band a value falls in,
# in O(log n) rather than a chain of elifs.
BOUNDS = [60, 70, 80, 90]
GRADES = "FDCBA"
GRADES[bisect.bisect_right(BOUNDS, score)]

# For heavy insert loads, sortedcontainers.SortedList is pure Python,
# has no C extension, and is genuinely faster than a tree because it
# keeps a list of short lists -- cache locality beating asymptotics again.

// Sorted.java — TreeMap is a red-black tree, and the navigation methods
// are the reason to choose it over HashMap. They are not obtainable from
// a hash table at any price.

NavigableMap<Instant, Reading> series = new TreeMap<>();

Map.Entry<Instant, Reading> atOrBefore = series.floorEntry(t);   // O(log n)
Map.Entry<Instant, Reading> next       = series.higherEntry(t);

// subMap is a VIEW: no copy, and writes through to the backing map.
// This is the range query, and it is the whole reason time series and
// rate limiters use TreeMap.
SortedMap<Instant, Reading> lastHour =
        series.subMap(now.minus(Duration.ofHours(1)), true, now, false);

// Expiring old entries is one call, because headMap is also a view and
// clear() on a view removes from the parent.
series.headMap(cutoff).clear();                  // O(k) in what it removes

// TreeMap orders by compareTo or by the comparator you pass -- NOT by
// equals. If compare() says two keys are equal, the map treats them as
// the same key even when equals() disagrees. That inconsistency is the
// classic TreeMap bug.
Map<String, Integer> ci = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
ci.put("Key", 1);
ci.put("KEY", 2);                                // overwrites: size() is 1

// heap.go — container/heap is an interface, not a container: you supply
// the storage and the comparison, it supplies the sift logic.

type Job struct {
    Priority int
    Name     string
    index    int                                 // maintained by heap.Fix
}

type PQ []*Job

func (q PQ) Len() int            { return len(q) }
func (q PQ) Less(i, j int) bool  { return q[i].Priority < q[j].Priority }  // min-heap
func (q PQ) Swap(i, j int)       { q[i], q[j] = q[j], q[i]; q[i].index = i; q[j].index = j }
func (q *PQ) Push(x any)         { j := x.(*Job); j.index = len(*q); *q = append(*q, j) }
func (q *PQ) Pop() any {
    old := *q
    n := len(old)
    it := old[n-1]
    old[n-1] = nil                               // let the GC have it
    *q = old[:n-1]
    return it
}

pq := &PQ{}
heap.Init(pq)
heap.Push(pq, &Job{Priority: 3, Name: "compact"})
next := heap.Pop(pq).(*Job)                      // O(log n)

// The reason to keep `index` is heap.Fix: change a job's priority in
// place and re-sift from where it sits, in O(log n) instead of O(n).
// Dijkstra with decrease-key needs exactly this.
job.Priority = 1
heap.Fix(pq, job.index)

// Top-k over a stream, in O(n log k) and O(k) memory: keep the k
// LARGEST by holding a MIN-heap and evicting the root.
for _, v := range stream {
    if pq.Len() < k {
        heap.Push(pq, v)
    } else if v.Priority > (*pq)[0].Priority {
        heap.Pop(pq)
        heap.Push(pq, v)
    }
}

# heapq.py — heapq operates on a plain list. There is no Heap class,
# which surprises people and then turns out to be liberating.
import heapq

h: list[int] = []
heapq.heappush(h, 5)                             # O(log n)
smallest = heapq.heappop(h)                      # O(log n)
peek = h[0]                                      # O(1) -- it is just index 0

heapq.heapify(existing_list)                     # O(n), not O(n log n)

# heappushpop is one sift instead of two: use it in the top-k loop.
for v in stream:
    if len(h) < k:
        heapq.heappush(h, v)
    else:
        heapq.heappushpop(h, v)                  # keeps the k largest

# nlargest/nsmallest do the above for you and pick the right strategy:
# sorted() when k is close to n, a heap when it is not.
top = heapq.nlargest(10, records, key=lambda r: r.score)

# It is a MIN-heap only. For a max-heap, negate:
heapq.heappush(h, -priority)

# Tuples compare lexicographically, which gives you priority queues for
# free -- but the tie-break falls through to the payload, and comparing
# two Task objects raises TypeError. Insert a counter as a tie-breaker:
from itertools import count
seq = count()
heapq.heappush(pq, (priority, next(seq), task))  # never compares `task`

# merge() streams any number of sorted iterables in sorted order using
# exactly one heap entry per input -- the external-sort merge, lazily.
for line in heapq.merge(*sorted_files, key=parse_ts):
    ...

// Heaps.java — PriorityQueue is a binary heap. Two facts about it cause
// most of the bugs: it is a MIN-heap by default, and iterating it does
// NOT give sorted order -- only repeated poll() does.

PriorityQueue<Job> pq = new PriorityQueue<>(Comparator.comparingInt(Job::priority));
pq.add(job);                                     // O(log n)
Job next = pq.poll();                            // O(log n), null when empty
Job peek = pq.peek();                            // O(1)

// for (Job j : pq)  -- iterates in ARRAY order, which is heap order,
// which looks almost sorted and is not. This is a real bug source.

// Top-k largest: a min-heap of size k, evicting the smallest.
PriorityQueue<Integer> topK = new PriorityQueue<>(k);
for (int v : stream) {
    if (topK.size() < k) topK.add(v);
    else if (v > topK.peek()) { topK.poll(); topK.add(v); }
}

// remove(Object) is O(n): it scans for the element before sifting. If
// you need decrease-key, PriorityQueue cannot do it efficiently --
// either keep an index map yourself, or use the standard Dijkstra trick
// of pushing a duplicate and skipping stale entries on the way out.

// Across threads: PriorityBlockingQueue is unbounded (backpressure is
// your problem) and DelayQueue is the scheduler variant, releasing an
// element only once its delay has expired.

// trie.go — autocomplete, routing tables and dictionary lookups.
// A map per node keeps it simple; a [26]*Node array is faster and only
// works for a known alphabet.

type Trie struct {
    kids map[rune]*Trie
    term bool                                    // a word ends here
}

func New() *Trie { return &Trie{kids: map[rune]*Trie{}} }

func (t *Trie) Insert(word string) {             // O(len(word))
    node := t
    for _, r := range word {
        next, ok := node.kids[r]
        if !ok {
            next = New()
            node.kids[r] = next
        }
        node = next
    }
    node.term = true
}

func (t *Trie) node(prefix string) *Trie {
    node := t
    for _, r := range prefix {
        next, ok := node.kids[r]
        if !ok {
            return nil
        }
        node = next
    }
    return node
}

// The operation a hash map cannot do: everything under a prefix, in
// sorted order, in time proportional to the OUTPUT rather than to the
// number of keys stored.
func (t *Trie) WithPrefix(prefix string, limit int) []string {
    start := t.node(prefix)
    if start == nil {
        return nil
    }
    var out []string
    var walk func(n *Trie, acc []rune)
    walk = func(n *Trie, acc []rune) {
        if len(out) >= limit {
            return
        }
        if n.term {
            out = append(out, prefix+string(acc))
        }
        for _, r := range slices.Sorted(maps.Keys(n.kids)) {   // sorted order
            walk(n.kids[r], append(acc, r))
        }
    }
    walk(start, nil)
    return out
}

# trie.py — a nested dict is a trie, and for most jobs that is enough.
END = object()                                   # a sentinel key meaning "word ends"

def build(words: list[str]) -> dict:
    root: dict = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})       # one line, one allocation
        node[END] = True
    return root

def starts_with(root: dict, prefix: str, limit: int = 10) -> list[str]:
    node = root
    for ch in prefix:
        node = node.get(ch)
        if node is None:
            return []
    out: list[str] = []

    def walk(n: dict, acc: str) -> None:
        if len(out) >= limit:
            return
        if END in n:
            out.append(prefix + acc)
        for ch in sorted(k for k in n if k is not END):
            walk(n[ch], acc + ch)

    walk(node, "")
    return out

# When to use one, and when not to:
#   yes - autocomplete, longest-prefix routing, spell check, a word
#         list you query by prefix constantly
#   no  - "I have strings as keys". A dict is smaller and faster for
#         exact lookup; a trie costs a node per character and loses
#         badly on memory unless prefixes really are shared.
#
# For fixed dictionaries, pyahocorasick (Aho-Corasick) finds ALL of
# thousands of patterns in one pass over the text -- a trie plus failure
# links, and the right answer for keyword scanning.

// Trie.java — a HashMap per node is the readable version; an array of
// 26 children is roughly twice as fast when the alphabet is fixed.

final class Trie {
    private final Map<Character, Trie> kids = new TreeMap<>();   // sorted kids
    private boolean terminal;

    void insert(String word) {                   // O(word.length())
        Trie node = this;
        for (char c : word.toCharArray()) {
            node = node.kids.computeIfAbsent(c, k -> new Trie());
        }
        node.terminal = true;
    }

    private Trie descend(String prefix) {
        Trie node = this;
        for (char c : prefix.toCharArray()) {
            node = node.kids.get(c);
            if (node == null) return null;
        }
        return node;
    }

    List<String> withPrefix(String prefix, int limit) {
        Trie start = descend(prefix);
        List<String> out = new ArrayList<>();
        if (start != null) collect(start, new StringBuilder(prefix), out, limit);
        return out;
    }

    private static void collect(Trie n, StringBuilder acc, List<String> out, int limit) {
        if (out.size() >= limit) return;
        if (n.terminal) out.add(acc.toString());
        for (var e : n.kids.entrySet()) {        // TreeMap: sorted
            acc.append(e.getKey());
            collect(e.getValue(), acc, out, limit);
            acc.deleteCharAt(acc.length() - 1);  // backtrack, no copying
        }
    }
}

// The StringBuilder-with-backtracking pattern above is worth stealing:
// it turns an O(depth) string copy at every node into an append and a
// delete. The same trick appears in every backtracking search.

// dsu.go — two int slices, twenty lines, and it is used by Kruskal's
// MST, connected components, image segmentation and cycle detection in
// undirected graphs.

type DSU struct {
    parent []int
    size   []int
    groups int
}

func NewDSU(n int) *DSU {
    d := &DSU{parent: make([]int, n), size: make([]int, n), groups: n}
    for i := range d.parent {
        d.parent[i], d.size[i] = i, 1            // everyone is their own root
    }
    return d
}

// Path halving: point every other node at its grandparent. One pass,
// no recursion, and asymptotically as good as full compression.
func (d *DSU) Find(x int) int {
    for d.parent[x] != x {
        d.parent[x] = d.parent[d.parent[x]]
        x = d.parent[x]
    }
    return x
}

// Union by size. Returns false if they were already together, which is
// exactly the cycle test Kruskal needs.
func (d *DSU) Union(a, b int) bool {
    ra, rb := d.Find(a), d.Find(b)
    if ra == rb {
        return false
    }
    if d.size[ra] < d.size[rb] {
        ra, rb = rb, ra                          // smaller hangs under larger
    }
    d.parent[rb] = ra
    d.size[ra] += d.size[rb]
    d.groups--
    return true
}

// Note what it cannot do: there is no Split. Union-find is one-way, so
// a problem with deletions needs a different structure -- or, commonly,
// processing the events in reverse so deletions become unions.

# dsu.py — the same twenty lines. The classic use is counting connected
# components in one pass over the edges, with no graph built at all.

class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         # already connected -> a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

# Connected components of an undirected graph, without adjacency lists:
dsu = DSU(n)
for a, b in edges:
    dsu.union(a, b)
print(dsu.groups, "components")

# Recursive find() with full compression is prettier and will blow the
# stack on a long chain, which is exactly the input that makes chains.
# Use the loop.

// Dsu.java — int arrays, no objects, no boxing. This is one of the few
// places where the "write it yourself" answer is unambiguously right:
// the JDK has no union-find.

final class Dsu {
    private final int[] parent;
    private final int[] size;
    private int groups;

    Dsu(int n) {
        parent = new int[n];
        size = new int[n];
        groups = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {                            // iterative: no stack depth
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];       // path halving
            x = parent[x];
        }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        groups--;
        return true;
    }

    int groups() { return groups; }
    boolean connected(int a, int b) { return find(a) == find(b); }
}

// Kruskal's minimum spanning tree is now four lines: sort the edges by
// weight, and keep each one whose union() returns true. The DSU is what
// makes "would this edge close a cycle?" an O(1) question.

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// mergesort.go — the one worth being able to write from memory, because
// the recurrence T(n) = 2T(n/2) + O(n) is the shape of half this page.

func MergeSort(xs []int) []int {
    if len(xs) < 2 {
        return xs
    }
    mid := len(xs) / 2
    left := MergeSort(slices.Clone(xs[:mid]))
    right := MergeSort(slices.Clone(xs[mid:]))
    return merge(left, right)
}

// The merge is the algorithm. Note `<=`: taking from the left on a tie
// is exactly what makes the sort stable. `<` would not.
func merge(a, b []int) []int {
    out := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            out, i = append(out, a[i]), i+1
        } else {
            out, j = append(out, b[j]), j+1
        }
    }
    return append(append(out, a[i:]...), b[j:]...)
}

// Quicksort's partition, for contrast: no buffer, and the whole cost is
// in choosing the pivot. Median-of-three on the first, middle and last
// element turns "sorted input is O(n^2)" into "you would have to try".
func partition(xs []int, lo, hi int) int {
    mid := lo + (hi-lo)/2
    if xs[mid] < xs[lo] { xs[mid], xs[lo] = xs[lo], xs[mid] }
    if xs[hi] < xs[lo]  { xs[hi], xs[lo] = xs[lo], xs[hi] }
    if xs[hi] < xs[mid] { xs[hi], xs[mid] = xs[mid], xs[hi] }
    pivot := xs[mid]
    i, j := lo, hi
    for i <= j {
        for xs[i] < pivot { i++ }
        for xs[j] > pivot { j-- }
        if i <= j {
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i+1, j-1
        }
    }
    return i
}

# sorts.py — write these once to understand them, then never again.

def merge_sort(xs: list[int]) -> list[int]:
    if len(xs) < 2:
        return xs
    mid = len(xs) // 2
    left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])

    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:                  # `<=` is what makes it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

# Three-way (Dutch national flag) partitioning: the fix for quicksort on
# data with many duplicates. Everything equal to the pivot ends up in
# the middle and is never looked at again, so an array of one repeated
# value goes from O(n^2) to O(n).
def quicksort(xs: list[int]) -> list[int]:
    if len(xs) < 2:
        return xs
    pivot = xs[len(xs) // 2]
    lt = [x for x in xs if x < pivot]
    eq = [x for x in xs if x == pivot]
    gt = [x for x in xs if x > pivot]
    return quicksort(lt) + eq + quicksort(gt)

# Counting sort: no comparisons, so the n log n bound simply does not
# apply. O(n + k) for keys in a small known range -- ages, HTTP status
# codes, bucket indices, anything with a few thousand distinct values.
def counting_sort(xs: list[int], k: int) -> list[int]:
    counts = [0] * k
    for x in xs:
        counts[x] += 1
    return [v for v, c in enumerate(counts) for _ in range(c)]

// Sorts.java — and the reason the JDK ships two completely different
// algorithms, chosen by the element type.

static void mergeSort(int[] a, int[] buf, int lo, int hi) {
    if (hi - lo < 2) return;
    int mid = (lo + hi) >>> 1;                   // >>> not /2: no overflow
    mergeSort(a, buf, lo, mid);
    mergeSort(a, buf, mid, hi);
    if (a[mid - 1] <= a[mid]) return;            // already ordered: skip the merge

    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i < mid) buf[k++] = a[i++];
    while (j < hi) buf[k++] = a[j++];
    System.arraycopy(buf, lo, a, lo, hi - lo);
}

// That one-line early exit is the seed of Timsort: real data arrives in
// runs, and a sort that detects them is linear on the common case.

// Arrays.sort(int[])     -> dual-pivot quicksort. In place, unstable,
//                           but stability is meaningless for primitives
//                           since equal ints are indistinguishable.
// Arrays.sort(Object[])  -> Timsort. Stable, O(n) on sorted input,
//                           needs an O(n) buffer.
// Arrays.parallelSort()  -> fork/join merge sort above ~8k elements.

// The contract you must not break: compare() has to be a total order.
// Violate transitivity and Timsort throws "Comparison method violates
// its general contract!" at random, on inputs above 32 elements.
Comparator<Item> bad = (x, y) -> x.score() > y.score() ? 1 : -1;   // never 0!
Comparator<Item> good = Comparator.comparingDouble(Item::score);

// sortapi.go — since 1.21 the generic slices package replaces the old
// sort.Slice reflection-based API. It is both faster and type-safe.

slices.Sort(nums)                                // ordered types, ascending
slices.SortFunc(users, func(a, b User) int {     // -1 / 0 / +1, like strcmp
    return cmp.Compare(a.Age, b.Age)
})
slices.SortStableFunc(users, byName)             // when a previous order matters

// Multi-key: compare the first, and only fall through on a tie. cmp.Or
// (Go 1.22) returns the first non-zero, which reads exactly like SQL's
// ORDER BY dept, name DESC.
slices.SortFunc(rows, func(a, b Row) int {
    return cmp.Or(
        cmp.Compare(a.Dept, b.Dept),
        cmp.Compare(b.Name, a.Name),             // reversed: b before a
    )
})

// Sorting by an expensive key: decorate, sort, undecorate. Computing
// the key inside the comparator evaluates it O(n log n) times.
type keyed struct {
    key  string
    item Item
}
ks := make([]keyed, len(items))
for i, it := range items {
    ks[i] = keyed{expensiveKey(it), it}          // exactly n calls
}
slices.SortFunc(ks, func(a, b keyed) int { return cmp.Compare(a.key, b.key) })

// slices.IsSorted is O(n) and worth an assertion in tests; slices.Min,
// slices.Max and slices.Index are all O(n) and beat sorting outright
// when you only need one element.

# sortapi.py — key= is computed exactly once per element, cmp= is gone
# (removed in Python 3), and both facts are deliberate.

users.sort(key=lambda u: u.age)                  # in place, returns None
ordered = sorted(users, key=lambda u: u.age)     # new list

# operator.attrgetter/itemgetter are faster than a lambda -- the loop
# stays in C instead of calling back into the interpreter n times.
from operator import attrgetter, itemgetter
users.sort(key=attrgetter("dept", "name"))       # tuple key: multi-column
rows.sort(key=itemgetter(2))

# Mixed ascending/descending on a tuple key: negate numbers, or -- since
# the sort is STABLE -- sort by the minor key first, then the major.
rows.sort(key=attrgetter("name"))                # minor key first
rows.sort(key=attrgetter("dept"))                # major key second, stably

# functools.cmp_to_key exists for the rare genuine comparator (natural
# sort, locale collation). It is slow: it wraps every element in an
# object whose __lt__ calls your function.
from functools import cmp_to_key
files.sort(key=cmp_to_key(natural_compare))

# Timsort's superpower: concatenating two sorted lists and re-sorting is
# O(n), not O(n log n), because it finds the two runs and merges them.
# "Append the new batch and re-sort" is a genuinely good pattern here.
existing.extend(new_batch)
existing.sort(key=attrgetter("ts"))              # linear-ish in practice

// SortApi.java — Comparator is a small combinator library, and using it
// properly removes essentially all hand-written compare methods.

users.sort(Comparator.comparingInt(User::age));
users.sort(Comparator.comparing(User::dept)
                     .thenComparing(User::name, Comparator.reverseOrder()));

// nullsFirst/nullsLast wrap any comparator so nulls stop throwing.
users.sort(Comparator.comparing(User::manager,
                                Comparator.nullsLast(Comparator.naturalOrder())));

// comparingInt/Long/Double avoid boxing the key on every comparison.
// comparing(User::age) boxes n log n times; comparingInt does not.

// The three-line trap, and it is common: subtraction overflows.
Comparator<User> broken = (a, b) -> a.id() - b.id();     // int overflow
Comparator<User> fixed   = Comparator.comparingInt(User::id);

// Sorting a stream: sorted() is a stateful full-barrier operation --
// it buffers everything, so it cannot be lazy and cannot stream.
List<User> top = users.stream()
        .sorted(Comparator.comparingInt(User::score).reversed())
        .limit(10)                               // sorts ALL n, then takes 10
        .toList();

// For top-k, a bounded PriorityQueue is O(n log k) instead of
// O(n log n) -- see the selection section below.

// bsearch.go — the standard library covers the ordinary cases; the one
// worth understanding is the predicate form.

i, found := slices.BinarySearch(xs, target)      // i is the insertion point
if !found {
    xs = slices.Insert(xs, i, target)            // keeps xs sorted
}

// sort.Search is binary search over a PREDICATE, not over values: it
// returns the smallest i in [0, n) for which f(i) is true, assuming f
// is false then true. That "assuming" is the whole contract.
i = sort.Search(len(xs), func(i int) bool { return xs[i] >= target })   // lower bound
j := sort.Search(len(xs), func(i int) bool { return xs[i] > target })   // upper bound
count := j - i                                   // how many equal `target`

// The powerful use: the array need not exist. Binary search the ANSWER
// of a monotone question. "What is the smallest capacity that finishes
// the work in `limit` hours?" -- feasible() is false, false, ..., true.
lo, hi := 1, maxLoad
best := sort.Search(hi-lo, func(k int) bool { return feasible(lo + k) }) + lo

// The overflow bug that lived in the JDK for nine years and in Bentley's
// published version for twenty:
//   mid := (lo + hi) / 2        // overflows once lo+hi exceeds maxint
//   mid := lo + (hi-lo)/2       // does not

# bsearch.py — bisect IS lower_bound and upper_bound, named after what
# they do to the list rather than after what they answer.
import bisect

lo = bisect.bisect_left(xs, target)              # first index with xs[i] >= target
hi = bisect.bisect_right(xs, target)             # first index with xs[i] >  target
count = hi - lo                                  # occurrences, in O(log n)
present = lo < len(xs) and xs[lo] == target      # the "found" test, written out

# Binary search on the answer, written by hand because there is no
# array: the classic "minimum capacity to ship in D days" shape.
def min_feasible(lo: int, hi: int, ok) -> int:
    """Smallest v in [lo, hi] with ok(v) true, where ok is monotone."""
    while lo < hi:
        mid = (lo + hi) // 2                     # Python ints never overflow
        if ok(mid):
            hi = mid                             # mid might be the answer: keep it
        else:
            lo = mid + 1                         # mid is not: discard it
    return lo

# The invariant to hold in your head, and the reason this loop is right:
#   ok(x) is false for every x < lo, and true for hi (or hi is the
#   past-the-end sentinel). Each iteration shrinks the window and
#   preserves that, so when lo == hi it is the answer.
#
# Write `hi = mid` and `lo = mid + 1`. The asymmetry is not a typo: it
# is what guarantees the window shrinks and the loop terminates.

// BSearch.java — Arrays.binarySearch encodes "not found" in the sign,
// which is efficient and catches people out for a decade.

int i = Arrays.binarySearch(xs, target);
if (i < 0) {
    int insertionPoint = -(i + 1);               // the documented decoding
    // negative means absent; -(i+1) is where it would go
}

// It also does NOT promise which one it finds among duplicates. For
// bounds, write the loop -- it is five lines and it is the version you
// want anyway.
static int lowerBound(int[] a, int target) {     // first index with a[i] >= target
    int lo = 0, hi = a.length;                   // note: hi is EXCLUSIVE
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;               // unsigned shift: no overflow
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;                                   // == a.length when all are smaller
}

// TreeMap gives you the same three answers on a live, mutable map:
//   ceilingKey(k)  -- lower bound
//   higherKey(k)   -- upper bound
//   floorKey(k)    -- the largest key <= k
// all O(log n), and unlike a sorted array they survive insertion.

// Collections.binarySearch on a LinkedList is O(n log n): it does
// log n lookups, each O(n). The JDK checks for RandomAccess and falls
// back to an iterator walk, which is better but still not what you want.

// select.go — quickselect is quicksort that throws away half the work.
// After partitioning, the pivot is in its final position; if that is
// past k, only the left side can contain the answer.

func QuickSelect(xs []int, k int) int {          // the k-th smallest, 0-based
    lo, hi := 0, len(xs)-1
    for lo < hi {
        p := partition(xs, lo, hi)               // same partition as quicksort
        switch {
        case p == k:
            return xs[k]
        case p < k:
            lo = p + 1                           // answer is to the right
        default:
            hi = p - 1                           // answer is to the left
        }
    }
    return xs[k]
}

// Why it is O(n): each pass halves the remaining range on average, so
// the total work is n + n/2 + n/4 + ... = 2n. Sorting does log n full
// passes; this does two.
//
// It MUTATES the slice. Clone first if the caller still needs the order.

// The streaming alternative, which never holds more than k:
func TopK(stream iter.Seq[Score], k int) []Score {
    h := &MinHeap{}                              // smallest of the best-k at the root
    for s := range stream {
        if h.Len() < k {
            heap.Push(h, s)
        } else if s.Value > (*h)[0].Value {
            heap.Pop(h)                          // evict the weakest survivor
            heap.Push(h, s)
        }
    }
    out := make([]Score, h.Len())
    for i := len(out) - 1; i >= 0; i-- {
        out[i] = heap.Pop(h).(Score)             // pops ascending, so fill back
    }
    return out
}

# select.py — the standard library already picks the right strategy.
import heapq
import random

# nlargest uses a bounded heap when k << n and falls back to sorted()
# when k is a large fraction of n. Trust it.
top = heapq.nlargest(10, scores, key=lambda s: s.value)

# statistics.median is O(n log n) because it sorts. For one median over
# a large array, quickselect is the linear alternative:
def quickselect(xs: list[int], k: int) -> int:
    """k-th smallest, 0-based. Randomised pivot, so sorted input is fine."""
    while True:
        if len(xs) == 1:
            return xs[0]
        pivot = random.choice(xs)                # randomised: no adversarial case
        lt = [x for x in xs if x < pivot]
        eq = [x for x in xs if x == pivot]
        if k < len(lt):
            xs = lt                              # recurse left only
        elif k < len(lt) + len(eq):
            return pivot                         # the pivot IS the answer
        else:
            k -= len(lt) + len(eq)               # recurse right, reindexed
            xs = [x for x in xs if x > pivot]

# For a running median over a stream, neither works: use two heaps, a
# max-heap of the lower half and a min-heap of the upper, kept within
# one element of the same size. The median is then one or two peeks.

// Select.java — the bounded-heap version, which is the one you will
// actually deploy, because it works over an unbounded stream.

static List<Score> topK(Stream<Score> stream, int k) {
    PriorityQueue<Score> heap =                   // MIN-heap of the best k
            new PriorityQueue<>(k, Comparator.comparingInt(Score::value));
    stream.forEach(s -> {
        if (heap.size() < k) heap.add(s);
        else if (s.value() > heap.peek().value()) {
            heap.poll();                         // drop the weakest survivor
            heap.add(s);
        }
    });
    List<Score> out = new ArrayList<>(heap);     // heap order, NOT sorted
    out.sort(Comparator.comparingInt(Score::value).reversed());
    return out;                                  // O(n log k + k log k)
}

// Compare with the obvious version, which sorts a million elements to
// look at ten of them:
//   stream.sorted(byValue.reversed()).limit(10).toList()  // O(n log n)
//
// At n = 1,000,000 and k = 10 the heap does ~3.3 million comparisons
// and the sort does ~20 million, and the heap holds 10 objects rather
// than buffering all of them. That is the whole argument.

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// graph.go — for dense integer ids, a [][]int is the fastest graph there
// is: one allocation per node, contiguous neighbours, no hashing.

type Graph struct {
    adj [][]int32                                // adj[u] = neighbours of u
}

func NewGraph(n int) *Graph { return &Graph{adj: make([][]int32, n)} }

func (g *Graph) AddEdge(u, v int32) {
    g.adj[u] = append(g.adj[u], v)
    g.adj[v] = append(g.adj[v], u)               // drop this line for a digraph
}

// When ids are strings, map them to dense integers once. Every
// algorithm below then indexes arrays instead of hashing, which is
// usually a 3-5x difference on a large graph.
type Ids struct {
    byName map[string]int32
    names  []string
}

func (ix *Ids) Get(name string) int32 {
    if id, ok := ix.byName[name]; ok {
        return id
    }
    id := int32(len(ix.names))
    ix.byName[name] = id
    ix.names = append(ix.names, name)
    return id
}

// Weighted edges: a struct, kept small so several fit in a cache line.
type Edge struct {
    To     int32
    Weight int32
}

// A CSR (compressed sparse row) layout goes further: two flat slices,
// offsets and targets, so the whole graph is two allocations. Worth it
// above a few million edges, and the format every graph library uses
// internally.
type CSR struct {
    offset []int32                               // len V+1
    target []int32                               // len E; neighbours of u are
}                                                // target[offset[u]:offset[u+1]]

# graph.py — a defaultdict of lists is the readable default and is
# almost always what you want.
from collections import defaultdict

graph: dict[str, list[str]] = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)                           # omit for a directed graph

# Careful: reading a missing key on a defaultdict CREATES it, so
# `for nb in graph[node]` silently grows the graph while you traverse.
# Use .get(node, ()) in the read path, or a plain dict built up front.
for nb in graph.get(node, ()):
    ...

# Weighted: a list of (neighbour, weight) tuples.
weighted: dict[str, list[tuple[str, int]]] = defaultdict(list)
weighted[u].append((v, w))

# A grid is a graph whose edges are implied by arithmetic -- do not
# build one. This generator is the entire adjacency structure:
def neighbours(r: int, c: int, rows: int, cols: int):
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

# networkx is excellent for analysis and exploration, and slow: it holds
# a dict-of-dicts-of-dicts per node. For anything in a hot path, write
# the twenty lines.

// Graph.java — records for edges, arrays for adjacency. Keep node ids
// dense and int-typed; a Map<String, List<String>> costs a hash on every
// single neighbour lookup inside the innermost loop of every algorithm.

record Edge(int to, int weight) {}

final class Graph {
    private final List<List<Edge>> adj;

    Graph(int n) {
        adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    }

    void addEdge(int u, int v, int w) {
        adj.get(u).add(new Edge(v, w));
        adj.get(v).add(new Edge(u, w));          // omit for a digraph
    }

    List<Edge> neighbours(int u) { return adj.get(u); }
    int size() { return adj.size(); }
}

// Interning string ids to dense ints, once:
Map<String, Integer> ids = new HashMap<>();
IntFunction<String> name = i -> names.get(i);
int id = ids.computeIfAbsent(rawName, k -> { names.add(k); return names.size() - 1; });

// For very large graphs, drop to primitive arrays entirely: int[]
// offsets and int[] targets (CSR). It removes every object header and
// makes neighbour iteration a contiguous scan, which on a graph with
// tens of millions of edges is the difference between fitting in cache
// and not.

// search.go — BFS and Dijkstra, written to show that they are one
// algorithm with two frontiers.

// BFS: shortest path in EDGES. The queue is what makes it correct --
// nodes come out in non-decreasing distance order.
func BFS(g *Graph, src int32) []int32 {
    dist := make([]int32, len(g.adj))
    for i := range dist {
        dist[i] = -1
    }
    dist[src] = 0
    q := []int32{src}
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        for _, v := range g.adj[u] {
            if dist[v] == -1 {                   // mark on ENQUEUE, not on
                dist[v] = dist[u] + 1            // dequeue, or a node can be
                q = append(q, v)                 // queued twice
            }
        }
    }
    return dist
}

// Dijkstra: same shape, heap instead of queue. The "lazy deletion"
// variant pushes duplicates and skips stale ones on the way out, which
// avoids needing decrease-key and is what nearly everyone ships.
func Dijkstra(g [][]Edge, src int32) []int64 {
    const inf = math.MaxInt64
    dist := make([]int64, len(g))
    for i := range dist {
        dist[i] = inf
    }
    dist[src] = 0

    pq := &NodeHeap{{Node: src, Dist: 0}}
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(NodeDist)
        if cur.Dist > dist[cur.Node] {
            continue                             // stale entry: already improved
        }
        for _, e := range g[cur.Node] {
            if nd := cur.Dist + int64(e.Weight); nd < dist[e.To] {
                dist[e.To] = nd
                heap.Push(pq, NodeDist{Node: e.To, Dist: nd})
            }
        }
    }
    return dist
}

// When every weight is 0 or 1, a deque beats the heap: push 0-weight
// edges on the front and 1-weight on the back. O(V+E), no log factor.
// This "0-1 BFS" is worth knowing; it comes up constantly in grids.

# search.py — the same two, and the third that people reach for a graph
# library to avoid writing.
import heapq
from collections import deque

def bfs(graph, src):
    """Fewest EDGES from src. Only correct when all edges cost the same."""
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in graph.get(u, ()):
            if v not in dist:                    # mark on enqueue
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def dijkstra(graph, src):
    """Cheapest path. Non-negative weights only."""
    dist = {src: 0}
    pq = [(0, src)]                              # (distance, node) -- tuples compare
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue                             # stale duplicate: skip it
        for v, w in graph.get(u, ()):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

# A* is dijkstra with one line changed: the heap is keyed by
# cost-so-far PLUS an estimate of the cost remaining. The estimate must
# never overestimate, or the answer stops being optimal. On a grid with
# unit steps, Manhattan distance is the standard admissible heuristic.
#     heapq.heappush(pq, (nd + h(v), nd, v))

# DFS: write it with an explicit stack. The recursive version is prettier
# and dies at a depth of 1000.
def dfs(graph, src):
    seen, stack = {src}, [src]
    while stack:
        u = stack.pop()
        for v in graph.get(u, ()):
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return seen

// Search.java — BFS on primitive arrays, Dijkstra on a PriorityQueue.

int[] bfs(Graph g, int src) {
    int[] dist = new int[g.size()];
    Arrays.fill(dist, -1);
    dist[src] = 0;
    Deque<Integer> q = new ArrayDeque<>();
    q.add(src);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (Edge e : g.neighbours(u)) {
            if (dist[e.to()] == -1) {            // mark on enqueue
                dist[e.to()] = dist[u] + 1;
                q.add(e.to());
            }
        }
    }
    return dist;
}

long[] dijkstra(Graph g, int src) {
    long[] dist = new long[g.size()];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;

    // long[]{distance, node} avoids a record allocation per push; the
    // comparator reads element 0.
    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
    pq.add(new long[]{0, src});

    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        int u = (int) cur[1];
        if (cur[0] > dist[u]) continue;          // stale entry
        for (Edge e : g.neighbours(u)) {
            long nd = cur[0] + e.weight();
            if (nd < dist[e.to()]) {
                dist[e.to()] = nd;
                pq.add(new long[]{nd, e.to()});  // lazy decrease-key
            }
        }
    }
    return dist;
}

// The bug that makes Dijkstra silently wrong: a negative edge weight.
// The algorithm assumes a popped node is final, and a negative edge can
// improve it afterwards. There is no error -- just a wrong answer. If
// weights can be negative you need Bellman-Ford, at O(V*E).

// topo.go — Kahn's algorithm, with the cycle report as a first-class
// result rather than a boolean.

func TopoSort(n int, deps [][]int32) ([]int32, error) {
    indeg := make([]int32, n)
    for _, vs := range deps {                    // deps[u] = things that need u
        for _, v := range vs {
            indeg[v]++
        }
    }

    ready := make([]int32, 0, n)
    for i, d := range indeg {
        if d == 0 {
            ready = append(ready, int32(i))
        }
    }

    order := make([]int32, 0, n)
    for len(ready) > 0 {
        // Everything in `ready` right now is independent: a build system
        // runs this whole slice in parallel and then re-fills it.
        u := ready[len(ready)-1]
        ready = ready[:len(ready)-1]
        order = append(order, u)
        for _, v := range deps[u] {
            if indeg[v]--; indeg[v] == 0 {
                ready = append(ready, v)
            }
        }
    }

    if len(order) != n {
        stuck := make([]int32, 0, n-len(order))
        for i, d := range indeg {
            if d > 0 {
                stuck = append(stuck, int32(i))  // in, or downstream of, a cycle
            }
        }
        return nil, fmt.Errorf("dependency cycle involving %v", stuck)
    }
    return order, nil
}

# topo.py — the standard library has had this since 3.9, and it is the
# parallel-aware version, not just a flat order.
from graphlib import CycleError, TopologicalSorter

graph = {"report": {"seed", "index"}, "seed": {"schema"}, "index": {"schema"}}

# The simple form: one valid order.
order = list(TopologicalSorter(graph).static_order())
# ['schema', 'seed', 'index', 'report']

# The useful form: get_ready() returns everything runnable RIGHT NOW,
# which is the set you hand to a thread pool. done() unblocks dependents.
ts = TopologicalSorter(graph)
ts.prepare()                                     # raises CycleError here if cyclic
while ts.is_active():
    batch = ts.get_ready()                       # a tuple of independent tasks
    for task in run_in_parallel(batch):
        ts.done(task)

# Cycle detection by hand, when you want the cycle itself. Three
# colours: 0 unvisited, 1 on the current path, 2 finished. An edge to a
# colour-1 node is a back edge, and the stack above it is the cycle.
def find_cycle(graph):
    colour, stack = {}, []

    def visit(u):
        colour[u] = 1
        stack.append(u)
        for v in graph.get(u, ()):
            if colour.get(v) == 1:               # back edge
                return stack[stack.index(v):] + [v]
            if colour.get(v, 0) == 0:
                if (found := visit(v)):
                    return found
        colour[u] = 2
        stack.pop()
        return None

    return next((c for u in graph if colour.get(u, 0) == 0 and (c := visit(u))), None)

// Topo.java — Kahn's algorithm with the batch structure exposed, which
// is what makes it a scheduler rather than just a sort.

static List<List<Integer>> waves(int n, List<List<Integer>> dependents) {
    int[] indeg = new int[n];
    for (List<Integer> vs : dependents)
        for (int v : vs) indeg[v]++;

    Deque<Integer> ready = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) ready.add(i);

    List<List<Integer>> out = new ArrayList<>();
    int emitted = 0;
    while (!ready.isEmpty()) {
        int width = ready.size();                // this wave is independent
        List<Integer> wave = new ArrayList<>(width);
        for (int i = 0; i < width; i++) {
            int u = ready.poll();
            wave.add(u);
            emitted++;
            for (int v : dependents.get(u))
                if (--indeg[v] == 0) ready.add(v);
        }
        out.add(wave);                           // hand each wave to an executor
    }

    if (emitted != n) {
        List<Integer> stuck = IntStream.range(0, n).filter(i -> indeg[i] > 0).boxed().toList();
        throw new IllegalStateException("dependency cycle involving " + stuck);
    }
    return out;
}

// The number of waves is the critical path length: the shortest wall
// clock the build can achieve with unlimited parallelism. Printing it
// tells you whether adding machines will help at all.

// mst.go — Kruskal is four lines once you have the DSU from part three.
// That is the payoff for having written it.

type WEdge struct {
    U, V   int32
    Weight int64
}

func Kruskal(n int, edges []WEdge) ([]WEdge, int64) {
    slices.SortFunc(edges, func(a, b WEdge) int {
        return cmp.Compare(a.Weight, b.Weight)   // the greedy order
    })

    dsu := NewDSU(n)
    tree := make([]WEdge, 0, n-1)
    var total int64
    for _, e := range edges {
        if dsu.Union(int(e.U), int(e.V)) {       // false == would close a cycle
            tree = append(tree, e)
            total += e.Weight
            if len(tree) == n-1 {
                break                            // a spanning tree has exactly n-1
            }
        }
    }
    return tree, total
}

// If len(tree) < n-1 when the loop ends, the graph was disconnected and
// what you have is a minimum spanning FOREST -- one tree per component.
// That is usually the right answer rather than an error.

// Single-linkage clustering falls out for free: stop early. Running
// Kruskal until exactly k components remain gives the clustering that
// maximises the smallest gap between clusters.
func Cluster(n int, edges []WEdge, k int) *DSU {
    slices.SortFunc(edges, func(a, b WEdge) int { return cmp.Compare(a.Weight, b.Weight) })
    dsu := NewDSU(n)
    for _, e := range edges {
        if dsu.groups == k {
            break
        }
        dsu.Union(int(e.U), int(e.V))
    }
    return dsu
}

# mst.py — Prim, which is Dijkstra with one word changed.
import heapq

def prim(graph: dict[int, list[tuple[int, int]]], start: int = 0):
    """Minimum spanning tree by growing one component.

    Compare with dijkstra() above: the ONLY difference is that the heap
    key is the edge weight `w` rather than the accumulated `d + w`.
    Dijkstra minimises distance from the source; Prim minimises the cost
    of attaching one more node to the tree.
    """
    seen = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    tree, total = [], 0

    while pq and len(seen) < len(graph):
        w, u, v = heapq.heappop(pq)
        if v in seen:
            continue                             # stale: v joined another way
        seen.add(v)
        tree.append((u, v, w))
        total += w
        for nxt, nw in graph[v]:
            if nxt not in seen:
                heapq.heappush(pq, (nw, v, nxt))

    return tree, total

# Kruskal in Python, using the DSU from part three:
def kruskal(n: int, edges: list[tuple[int, int, int]]):
    dsu = DSU(n)
    tree, total = [], 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):                      # False means it closes a cycle
            tree.append((u, v, w))
            total += w
    return tree, total

// Mst.java — Kruskal with the Dsu from part three. Note how little code
// the algorithm itself is: the work is all in the two data structures.

record WEdge(int u, int v, long weight) {}

static List<WEdge> kruskal(int n, List<WEdge> edges) {
    List<WEdge> sorted = new ArrayList<>(edges);
    sorted.sort(Comparator.comparingLong(WEdge::weight));

    Dsu dsu = new Dsu(n);
    List<WEdge> tree = new ArrayList<>(n - 1);
    for (WEdge e : sorted) {
        if (dsu.union(e.u(), e.v())) {           // false: both ends already joined
            tree.add(e);
            if (tree.size() == n - 1) break;
        }
    }
    return tree;                                 // size < n-1 => disconnected graph
}

// Why greedy is provably correct here, which is worth knowing because
// greedy is usually wrong: the CUT PROPERTY. Split the nodes into any
// two non-empty groups. The lightest edge crossing that split is in
// SOME minimum spanning tree -- if a tree omits it, adding it creates a
// cycle, and removing any other crossing edge from that cycle gives a
// tree no heavier. Every edge Kruskal accepts is the lightest crossing
// the cut between its two components, so every acceptance is safe.

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// dp.go — Go has no memoisation decorator, so the cache is explicit.
// That is not a loss: it makes the state space visible, which is the
// thing you are supposed to be thinking about.

// Step 1: the honest recursion. O(2^n), and correct.
func coinsNaive(amount int, coins []int) int {
    if amount == 0 {
        return 0
    }
    best := math.MaxInt
    for _, c := range coins {
        if c <= amount {
            if sub := coinsNaive(amount-c, coins); sub != math.MaxInt {
                best = min(best, sub+1)
            }
        }
    }
    return best
}

// Step 2: memoise. The state is a single int, so the cache is a slice.
// O(amount * len(coins)).
func coinsMemo(amount int, coins []int) int {
    memo := make([]int, amount+1)
    for i := range memo {
        memo[i] = -1                             // -1 = not computed yet
    }
    var solve func(int) int
    solve = func(a int) int {
        if a == 0 {
            return 0
        }
        if memo[a] != -1 {
            return memo[a]
        }
        best := math.MaxInt
        for _, c := range coins {
            if c <= a {
                if sub := solve(a - c); sub != math.MaxInt {
                    best = min(best, sub+1)
                }
            }
        }
        memo[a] = best
        return best
    }
    return solve(amount)
}

// Step 3: bottom-up. Same complexity, no recursion, no stack, and the
// loop order IS the dependency order -- every a-c is smaller than a.
func coins(amount int, cs []int) int {
    dp := make([]int, amount+1)
    for a := 1; a <= amount; a++ {
        dp[a] = math.MaxInt
        for _, c := range cs {
            if c <= a && dp[a-c] != math.MaxInt {
                dp[a] = min(dp[a], dp[a-c]+1)
            }
        }
    }
    return dp[amount]
}

# dp.py — in Python step 2 is one line, which makes it the fastest
# language to explore a recurrence in.
from functools import cache

# Step 1 and 2 together. The decorator IS the memoisation: it keys the
# cache on the argument tuple, so the arguments must be hashable.
@cache
def coins(amount: int, coins_t: tuple[int, ...]) -> float:
    if amount == 0:
        return 0
    return min((coins(amount - c, coins_t) + 1
                for c in coins_t if c <= amount), default=float("inf"))

# Two rules for @cache on a recursive function:
#   - every argument must be hashable, so pass tuples, not lists
#   - the cache is global and unbounded; it outlives the call. Use
#     lru_cache(maxsize=...) or clear it if the inputs are unbounded.

# Step 3, when the recursion depth would exceed 1000 or the constant
# factor matters:
def coins_iter(amount: int, cs: list[int]) -> float:
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        dp[a] = min((dp[a - c] + 1 for c in cs if c <= a), default=float("inf"))
    return dp[amount]

# Reconstructing the ANSWER, not just its cost: keep the choice.
def coins_which(amount: int, cs: list[int]) -> list[int] | None:
    dp = [0] + [None] * amount                   # dp[a] = coin used to reach a
    reach = [0] + [False] * amount
    for a in range(1, amount + 1):
        for c in cs:
            if c <= a and reach[a - c]:
                dp[a], reach[a] = c, True
                break
    if not reach[amount]:
        return None
    out = []
    while amount:                                # walk the choices backwards
        out.append(dp[amount])
        amount -= dp[amount]
    return out

// Dp.java — an int[] cache and a sentinel. Java has no memo decorator
// either; computeIfAbsent on a Map works but boxes every key.

static final int UNSET = -1, IMPOSSIBLE = Integer.MAX_VALUE;

// Step 2: top-down with an explicit cache.
static int coinsMemo(int amount, int[] coins, int[] memo) {
    if (amount == 0) return 0;
    if (memo[amount] != UNSET) return memo[amount];

    int best = IMPOSSIBLE;
    for (int c : coins) {
        if (c <= amount) {
            int sub = coinsMemo(amount - c, coins, memo);
            if (sub != IMPOSSIBLE) best = Math.min(best, sub + 1);
        }
    }
    return memo[amount] = best;
}

// Step 3: bottom-up. Prefer this in Java -- the default stack is around
// 512 KB and a recursion of depth 100,000 will not survive it.
static int coins(int amount, int[] cs) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, IMPOSSIBLE);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : cs)
            if (c <= a && dp[a - c] != IMPOSSIBLE)
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount];
}

// Note the guard `dp[a - c] != IMPOSSIBLE` in both. Without it,
// IMPOSSIBLE + 1 overflows to Integer.MIN_VALUE and min() cheerfully
// picks it -- an "unreachable amount costs minus two billion coins" bug
// that produces a plausible-looking wrong answer rather than a crash.

// edit.go — the rolling-row version, which is what you ship when you
// only need the distance. Two rows instead of m*n.

func EditDistance(a, b string) int {
    ra, rb := []rune(a), []rune(b)               // runes: "café" is 4, not 5
    if len(ra) < len(rb) {
        ra, rb = rb, ra                          // keep the short side as the row
    }

    prev := make([]int, len(rb)+1)
    curr := make([]int, len(rb)+1)
    for j := range prev {
        prev[j] = j                              // turning "" into b[:j] costs j
    }

    for i := 1; i <= len(ra); i++ {
        curr[0] = i                              // turning a[:i] into "" costs i
        for j := 1; j <= len(rb); j++ {
            sub := prev[j-1]
            if ra[i-1] != rb[j-1] {
                sub++
            }
            curr[j] = min(
                prev[j]+1,                       // delete a[i-1]
                curr[j-1]+1,                     // insert b[j-1]
                sub,                             // substitute, or free on a match
            )
        }
        prev, curr = curr, prev                  // swap, do not allocate
    }
    return prev[len(rb)]
}

// Early exit for a fuzzy-search threshold: if the smallest value in a
// whole row already exceeds the limit, every later row is worse, so you
// can stop. On a dictionary scan this is the difference between usable
// and not.
//
// Longest common subsequence is the same table with a different
// recurrence -- max instead of min, and only the diagonal advances on a
// match. That is what `diff` computes, then reads back as the edit script.

# edit.py — the full table, because the backtrace is the interesting
# half and the reason `diff` output looks the way it does.

def edit_table(a: str, b: str) -> list[list[int]]:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i                             # delete everything
    for j in range(m + 1):
        dp[0][j] = j                             # insert everything
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = min(
                dp[i - 1][j] + 1,                # delete a[i-1]
                dp[i][j - 1] + 1,                # insert b[j-1]
                dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]),   # substitute/match
            )
    return dp

def edit_script(a: str, b: str) -> list[str]:
    """Walk backwards from the corner, taking whichever choice produced it."""
    dp = edit_table(a, b)
    i, j, out = len(a), len(b), []
    while i > 0 or j > 0:
        if i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            out.append(f"-{a[i - 1]}"); i -= 1
        elif j > 0 and dp[i][j] == dp[i][j - 1] + 1:
            out.append(f"+{b[j - 1]}"); j -= 1
        else:
            if a[i - 1] != b[j - 1]:
                out.append(f"~{a[i - 1]}{b[j - 1]}")
            i -= 1; j -= 1
    return out[::-1]

# edit_script("kitten", "sitting") -> ['~ks', '~ie', '+g'] with the
# matched letters skipped: three edits, which is the distance.
#
# difflib.SequenceMatcher in the standard library solves the related
# problem (longest matching blocks) with a different algorithm tuned for
# human-readable diffs rather than minimal edit count.

// Edit.java — one int[] row, which is all the distance needs.

static int editDistance(String a, String b) {
    if (a.length() < b.length()) { String t = a; a = b; b = t; }

    int[] prev = new int[b.length() + 1];
    int[] curr = new int[b.length() + 1];
    for (int j = 0; j <= b.length(); j++) prev[j] = j;

    for (int i = 1; i <= a.length(); i++) {
        curr[0] = i;
        for (int j = 1; j <= b.length(); j++) {
            int sub = prev[j - 1] + (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1);
            curr[j] = Math.min(Math.min(prev[j] + 1, curr[j - 1] + 1), sub);
        }
        int[] swap = prev; prev = curr; curr = swap;   // reuse both arrays
    }
    return prev[b.length()];
}

// charAt() is UTF-16 code units, not characters: an emoji is two units
// and this will happily compute a distance in half-characters. For
// text from users, work in code points:
//     int[] cps = a.codePoints().toArray();

// The same table shape, four common recurrences:
//   edit distance          min(del, ins, sub)
//   longest common subseq  match ? diag+1 : max(up, left)
//   longest common substr  match ? diag+1 : 0, and track the max
//   0/1 knapsack           max(without item, value + best of remainder)
// Learn the shape once and all four are the same twenty lines.

// classics.go — Kadane and LIS, the two whose clever versions beat the
// obvious table outright.

// Kadane: maximum sum of any contiguous run, in one pass. The state is
// "best run ENDING HERE", which either extends the previous run or
// starts fresh -- and that choice is the whole algorithm.
func MaxSubarray(xs []int) (best, lo, hi int) {
    best, cur, start := math.MinInt, 0, 0
    for i, v := range xs {
        if cur <= 0 {
            cur, start = v, i                    // the past is a liability: drop it
        } else {
            cur += v
        }
        if cur > best {
            best, lo, hi = cur, start, i
        }
    }
    return best, lo, hi
}

// Longest increasing subsequence in O(n log n). tails[k] holds the
// smallest possible tail of an increasing subsequence of length k+1;
// it is always sorted, so the position is a binary search.
func LIS(xs []int) int {
    tails := make([]int, 0, len(xs))
    for _, v := range xs {
        i, _ := slices.BinarySearch(tails, v)
        if i == len(tails) {
            tails = append(tails, v)             // v extends the longest run
        } else {
            tails[i] = v                         // v gives length i+1 a better tail
        }
    }
    return len(tails)                            // NOTE: the length, not the run
}

// `tails` is not itself a valid subsequence -- a common misreading. To
// recover the actual run, record a predecessor index for each element
// as you place it, then walk backwards from the last one appended.

# classics.py — knapsack, and the space optimisation that catches
# people out.

def knapsack(weights: list[int], values: list[int], cap: int) -> int:
    """0/1 knapsack: each item may be taken at most once."""
    dp = [0] * (cap + 1)                         # dp[w] = best value within w
    for wt, val in zip(weights, values):
        # BACKWARDS. Forwards would let this item be picked twice,
        # because dp[w - wt] would already include it. That single
        # reversal is the difference between 0/1 and unbounded knapsack.
        for w in range(cap, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]

def unbounded_knapsack(weights, values, cap) -> int:
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for w in range(wt, cap + 1):             # forwards: reuse is allowed
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]

# O(nW) is "pseudo-polynomial": W is a VALUE, not an input length, so a
# capacity of 10^9 makes this table impossible even with ten items.
# Knapsack is NP-hard; the DP is only fast because W is usually small.

def lis_with_run(xs: list[int]) -> list[int]:
    """The actual subsequence, not just its length."""
    import bisect
    tails, tail_idx, prev = [], [], [-1] * len(xs)
    for i, v in enumerate(xs):
        k = bisect.bisect_left(tails, v)
        if k == len(tails):
            tails.append(v); tail_idx.append(i)
        else:
            tails[k], tail_idx[k] = v, i
        prev[i] = tail_idx[k - 1] if k else -1
    out, i = [], tail_idx[-1] if tail_idx else -1
    while i >= 0:
        out.append(xs[i]); i = prev[i]
    return out[::-1]

// Classics.java — word break, which is the one that most often shows up
// disguised as something else (tokenising, URL routing, segmentation).

static boolean wordBreak(String s, Set<String> dict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;                                // the empty prefix is splittable

    int longest = dict.stream().mapToInt(String::length).max().orElse(0);

    for (int i = 1; i <= n; i++) {
        // Only look back as far as the longest word: turns O(n^2) into
        // O(n * longest), which for real dictionaries is linear.
        for (int j = Math.max(0, i - longest); j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

// substring() is O(length) and allocates, so this does O(n^2) character
// copying on top of the O(n^2) loop. A trie over the dictionary removes
// both: walk forward from j one character at a time, and stop the
// instant the prefix leaves the trie.

static int maxSubarray(int[] xs) {               // Kadane, O(n), O(1)
    int best = Integer.MIN_VALUE, cur = 0;
    for (int v : xs) {
        cur = Math.max(v, cur + v);              // extend, or start again here
        best = Math.max(best, cur);
    }
    return best;
}

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// window.go — the sliding-window template. Almost every "longest or
// shortest run such that ..." problem is this eight-line shape with a
// different condition.

func LongestUnique(s string) (best, at int) {
    last := make(map[byte]int, 64)               // byte -> last index seen
    lo := 0
    for hi := 0; hi < len(s); hi++ {
        if prev, seen := last[s[hi]]; seen && prev >= lo {
            lo = prev + 1                        // jump past the duplicate; never back
        }
        last[s[hi]] = hi
        if hi-lo+1 > best {
            best, at = hi-lo+1, lo
        }
    }
    return best, at
}

// Opposite ends, on sorted input. Each iteration eliminates one whole
// row or column of the pair matrix, which is why n steps suffice for
// n^2 pairs.
func TwoSum(sorted []int, target int) (int, int, bool) {
    i, j := 0, len(sorted)-1
    for i < j {
        switch sum := sorted[i] + sorted[j]; {
        case sum == target:
            return i, j, true
        case sum < target:
            i++                                  // no pair with sorted[i] can work
        default:
            j--                                  // no pair with sorted[j] can work
        }
    }
    return 0, 0, false
}

// In-place filter: read and write pointers over one array. This is the
// same idea and it is how every "remove duplicates from a sorted array
// without allocating" is written.
func Compact(xs []int) []int {
    w := 0
    for r := range xs {
        if r == 0 || xs[r] != xs[r-1] {
            xs[w] = xs[r]
            w++
        }
    }
    return xs[:w]                                // slices.Compact does exactly this
}

# window.py — the variable-size window, and the fixed-size one, which
# are different enough to be worth separating.
from collections import Counter

def longest_unique(s: str) -> str:
    """Longest substring with no repeated character. O(n)."""
    last: dict[str, int] = {}
    lo = best = at = 0
    for hi, ch in enumerate(s):
        if (prev := last.get(ch, -1)) >= lo:
            lo = prev + 1                        # the left edge only ever advances
        last[ch] = hi
        if hi - lo + 1 > best:
            best, at = hi - lo + 1, lo
    return s[at:at + best]

def min_window_covering(s: str, need: str) -> str:
    """Shortest substring containing every character of `need`. O(n).

    The 'shortest' variant grows the right edge until the window is
    valid, then shrinks the left as far as it can while staying valid.
    Both edges still only move forward.
    """
    want = Counter(need)
    missing = len(need)
    lo = best_lo = 0
    best = float("inf")
    for hi, ch in enumerate(s):
        if want[ch] > 0:
            missing -= 1
        want[ch] -= 1
        while missing == 0:                      # valid: try to shrink
            if hi - lo + 1 < best:
                best, best_lo = hi - lo + 1, lo
            want[s[lo]] += 1
            if want[s[lo]] > 0:
                missing += 1
            lo += 1
    return "" if best == float("inf") else s[best_lo:best_lo + best]

# Fixed-size windows do not need any of this: keep a running sum and
# subtract the element leaving as you add the one arriving.
def rolling_mean(xs: list[float], k: int) -> list[float]:
    total = sum(xs[:k])
    out = [total / k]
    for i in range(k, len(xs)):
        total += xs[i] - xs[i - k]               # O(1) per step, not O(k)
        out.append(total / k)
    return out

// Window.java — the template, with the two things Java makes you think
// about: char vs code point, and the array-as-counter trick.

static int longestUnique(String s) {
    int[] last = new int[128];                   // ASCII: faster than a HashMap
    Arrays.fill(last, -1);
    int lo = 0, best = 0;
    for (int hi = 0; hi < s.length(); hi++) {
        char c = s.charAt(hi);
        if (last[c] >= lo) lo = last[c] + 1;     // jump; never move lo back
        last[c] = hi;
        best = Math.max(best, hi - lo + 1);
    }
    return best;
}

// Two pointers over two sorted lists: the intersection, in O(n + m)
// rather than the O(n*m) of contains() in a loop.
static List<Integer> intersect(int[] a, int[] b) {
    List<Integer> out = new ArrayList<>();
    int i = 0, j = 0;
    while (i < a.length && j < b.length) {
        if (a[i] == b[j]) { out.add(a[i]); i++; j++; }
        else if (a[i] < b[j]) i++;               // advance whichever is behind
        else j++;
    }
    return out;
}

// The read/write pointer, in place:
static int compact(int[] xs) {
    int w = 0;
    for (int r = 0; r < xs.length; r++)
        if (r == 0 || xs[r] != xs[r - 1]) xs[w++] = xs[r];
    return w;                                    // the new logical length
}

// prefix.go — build once in O(n), answer every range query in O(1).

func Prefix(xs []int) []int {
    p := make([]int, len(xs)+1)                  // note the +1: p[0] = 0 removes
    for i, v := range xs {                       // every "if i == 0" branch below
        p[i+1] = p[i] + v
    }
    return p
}

sum := p[j+1] - p[i]                             // inclusive range [i, j], O(1)

// The difference array is the same idea run backwards: to add `delta`
// to every element in [i, j], record it at the two ENDS and integrate
// once at the end. k range updates in O(k + n) instead of O(kn).
func ApplyRanges(n int, updates [][3]int) []int {
    diff := make([]int, n+1)
    for _, u := range updates {
        lo, hi, delta := u[0], u[1], u[2]
        diff[lo] += delta
        diff[hi+1] -= delta                      // the +1 slot is why diff is n+1
    }
    out := make([]int, n)
    running := 0
    for i := range out {
        running += diff[i]
        out[i] = running
    }
    return out
}

// This is how "how many meetings overlap at the busiest moment" is
// solved: +1 at each start, -1 at each end, then a running maximum of
// the integral. No interval tree required.

// When the array DOES change between queries, a prefix sum is wrong --
// every update invalidates the whole tail. That is what a Fenwick tree
// (binary indexed tree) is for: O(log n) update and O(log n) prefix
// query, in n words of memory and about fifteen lines.

# prefix.py — itertools.accumulate is the standard-library prefix sum.
from itertools import accumulate

p = [0] + list(accumulate(xs))                   # p[i] = sum of xs[:i]
total = p[j + 1] - p[i]                          # inclusive [i, j], O(1)

# accumulate takes any binary function, so the same one line gives you
# running maxima, running products, or a running state machine.
running_max = list(accumulate(xs, max))
drawdowns = [hi - v for hi, v in zip(accumulate(xs, max), xs)]

# The prefix-sum + hash-map combination, which is the answer to a
# surprising number of questions: "how many subarrays sum to k?"
# A subarray (i, j] sums to k exactly when p[j] - p[i] == k, so for
# each j we need the count of earlier prefixes equal to p[j] - k.
def count_subarrays_summing_to(xs: list[int], k: int) -> int:
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1                                  # the empty prefix
    running = total = 0
    for v in xs:
        running += v
        total += seen[running - k]               # O(1) per element
        seen[running] += 1
    return total

# O(n) and one pass. The obvious version is O(n^2), and the difference
# is entirely "remember what you have already computed".

# Two dimensions: a 2-D prefix sum answers "sum of this rectangle" in
# four lookups by inclusion-exclusion.
#   area = P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]

// Prefix.java — and the Fenwick tree, for when the array changes.

static long[] prefix(int[] xs) {
    long[] p = new long[xs.length + 1];          // long: prefix sums overflow int
    for (int i = 0; i < xs.length; i++) p[i + 1] = p[i] + xs[i];
    return p;
}

// A Fenwick tree: prefix sums that survive updates. Each slot i holds
// the sum of a block whose length is the lowest set bit of i, so both
// operations walk O(log n) slots. Fifteen lines, and it replaces a
// segment tree for anything that only needs sums.
final class Fenwick {
    private final long[] t;

    Fenwick(int n) { t = new long[n + 1]; }      // 1-indexed

    void add(int i, long delta) {                // O(log n)
        for (i++; i < t.length; i += i & -i) t[i] += delta;
    }

    long prefix(int i) {                         // sum of [0, i), O(log n)
        long s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }

    long range(int lo, int hi) { return prefix(hi) - prefix(lo); }
}

// `i & -i` isolates the lowest set bit -- the one bit trick worth
// knowing by name, and the whole reason this structure is so small.
//
// Fenwick handles sums (and anything invertible). For minimum, maximum
// or gcd over a range, you need a segment tree, which is larger but
// handles any associative operation.

// greedy.go — interval scheduling. The whole algorithm is the sort key,
// and choosing the wrong key is the classic error.

type Interval struct{ Start, End int }

// Sort by END time, not by start and not by duration. A meeting that
// finishes early leaves the most room for everything after it, and that
// sentence is the proof.
func MaxNonOverlapping(ivs []Interval) []Interval {
    slices.SortFunc(ivs, func(a, b Interval) int { return cmp.Compare(a.End, b.End) })

    out := make([]Interval, 0, len(ivs))
    lastEnd := math.MinInt
    for _, iv := range ivs {
        if iv.Start >= lastEnd {                 // no overlap with the last kept
            out = append(out, iv)
            lastEnd = iv.End
        }
    }
    return out
}

// Merging overlapping intervals: sort by START, then extend or emit.
// Different question, different key -- and that is the point.
func Merge(ivs []Interval) []Interval {
    slices.SortFunc(ivs, func(a, b Interval) int { return cmp.Compare(a.Start, b.Start) })

    out := ivs[:0]                               // reuse the backing array
    for _, iv := range ivs {
        if n := len(out); n > 0 && iv.Start <= out[n-1].End {
            out[n-1].End = max(out[n-1].End, iv.End)
        } else {
            out = append(out, iv)
        }
    }
    return out
}

// Both are O(n log n), dominated entirely by the sort. Once the input
// is ordered, the sweep is a single pass with one variable of state.

# greedy.py — Huffman coding, which is greedy plus a heap and is the
# clearest example of a rule that is provably safe.
import heapq
from collections import Counter
from itertools import count

def huffman(text: str) -> dict[str, str]:
    """Optimal prefix-free codes: frequent symbols get shorter codes."""
    freq = Counter(text)
    if len(freq) < 2:
        return {ch: "0" for ch in freq}

    seq = count()                                # tie-breaker: never compare dicts
    heap = [(n, next(seq), {ch: ""}) for ch, n in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        # The greedy step: the two least frequent symbols must be the
        # two DEEPEST leaves in some optimal tree, so merging them now
        # cannot cost anything.
        n1, _, a = heapq.heappop(heap)
        n2, _, b = heapq.heappop(heap)
        merged = {ch: "0" + code for ch, code in a.items()}
        merged |= {ch: "1" + code for ch, code in b.items()}
        heapq.heappush(heap, (n1 + n2, next(seq), merged))

    return heap[0][2]

# A counterexample to greedy coin change, small enough to keep in your
# head as a reminder that "obviously optimal" needs a proof:
#     coins = [1, 3, 4], target = 6
#     greedy -> 4 + 1 + 1   (three coins)
#     optimal -> 3 + 3      (two)

// Greedy.java — the meeting-rooms family, which is really a sweep line.

record Interval(int start, int end) {}

// "How many rooms do I need?" is not an interval-scheduling problem: it
// is the maximum overlap, and the neat solution is a heap of end times.
static int roomsNeeded(List<Interval> meetings) {
    List<Interval> sorted = new ArrayList<>(meetings);
    sorted.sort(Comparator.comparingInt(Interval::start));

    // The heap holds the end time of every meeting still running. Its
    // size is the number of rooms in use; its root is the one that
    // frees up first.
    PriorityQueue<Integer> running = new PriorityQueue<>();
    for (Interval m : sorted) {
        if (!running.isEmpty() && running.peek() <= m.start()) {
            running.poll();                      // a room came free: reuse it
        }
        running.add(m.end());
    }
    return running.size();                       // the peak, O(n log n)
}

// The same answer as a difference array, in O(n log n) but with no heap
// and a much smaller constant: +1 at every start, -1 at every end, sort
// the events, and take the running maximum. Pick whichever you find
// easier to get right at 3 a.m.; they are the same algorithm seen from
// two directions.

// backtrack.go — the template. Choose, recurse, un-choose. That last
// step is what makes it backtracking rather than brute force with
// copies, and it keeps the allocation count at zero.

func Permutations(xs []int) [][]int {
    var out [][]int
    var cur []int
    used := make([]bool, len(xs))

    var walk func()
    walk = func() {
        if len(cur) == len(xs) {
            out = append(out, slices.Clone(cur)) // CLONE: cur keeps mutating
            return
        }
        for i, v := range xs {
            if used[i] {
                continue
            }
            used[i], cur = true, append(cur, v)  // choose
            walk()                               // explore
            used[i], cur = false, cur[:len(cur)-1] // un-choose
        }
    }
    walk()
    return out
}

// N-queens: the same template, with the pruning that makes it possible.
// Three bitmasks track which column and which of the two diagonals are
// already attacked, so "is this square safe" is one AND.
func NQueens(n int) int {
    var count int
    var place func(row, cols, diag, anti int)
    place = func(row, cols, diag, anti int) {
        if row == n {
            count++
            return
        }
        // free = the squares in this row attacked by nothing
        free := ^(cols | diag | anti) & (1<<n - 1)
        for free != 0 {
            bit := free & -free                  // lowest set bit: one square
            free ^= bit
            place(row+1, cols|bit, (diag|bit)<<1, (anti|bit)>>1)
        }
    }
    place(0, 0, 0, 0)
    return count
}

// Without the masks this is 8^8 = 16 million placements for n=8; with
// them it is about 2,000. The search space did not change -- the number
// of branches worth entering did.

# backtrack.py — the template again, and the standard library shortcut
# for the cases that need no pruning at all.
from itertools import combinations, permutations, product

list(permutations([1, 2, 3]))                    # all orderings, lazily
list(combinations(range(5), 3))                  # all 3-subsets, in order
list(product("ab", repeat=3))                    # the cartesian product

# Reach for itertools first: it is C, lazy, and correct. Write the
# recursion only when you need to PRUNE, which the library cannot do.

def subsets_summing_to(xs: list[int], target: int) -> list[list[int]]:
    """All subsets with a given sum, pruning branches that cannot reach it."""
    xs = sorted(xs, reverse=True)                # big first: prune sooner
    suffix = [0] * (len(xs) + 1)                 # suffix[i] = sum of xs[i:]
    for i in range(len(xs) - 1, -1, -1):
        suffix[i] = suffix[i + 1] + xs[i]

    out: list[list[int]] = []
    cur: list[int] = []

    def walk(i: int, remaining: int) -> None:
        if remaining == 0:
            out.append(cur.copy())               # copy: cur keeps mutating
            return
        # The two prunes that turn 2^n into something finishable:
        if i == len(xs) or remaining < 0:
            return
        if suffix[i] < remaining:                # everything left is not enough
            return
        cur.append(xs[i])                        # choose
        walk(i + 1, remaining - xs[i])
        cur.pop()                                # un-choose
        walk(i + 1, remaining)                   # skip this element

    walk(0, target)
    return out

// Backtrack.java — a Sudoku solver, which is the pruning argument in
// its most familiar form.

static boolean solve(char[][] board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;
            for (char v = '1'; v <= '9'; v++) {
                if (!isValid(board, r, c, v)) continue;
                board[r][c] = v;                 // choose
                if (solve(board)) return true;   // explore
                board[r][c] = '.';               // un-choose
            }
            return false;                        // no digit fits: this branch is dead
        }
    }
    return true;                                 // no empty cell left: solved
}

static boolean isValid(char[][] b, int r, int c, char v) {
    int br = r / 3 * 3, bc = c / 3 * 3;
    for (int i = 0; i < 9; i++)
        if (b[r][i] == v || b[i][c] == v || b[br + i / 3][bc + i % 3] == v)
            return false;
    return true;
}

// That early `return false` is the whole algorithm. Without it you
// enumerate 9^81 boards; with it, a typical puzzle is solved in a few
// thousand placements.
//
// The next improvement is not a faster isValid but a better ORDER:
// fill the cell with the fewest legal candidates first (minimum
// remaining values). Choosing what to decide next is usually worth
// more than making each decision cheaper.

// bits.go — math/bits compiles to single instructions. Do not hand-roll
// popcount; the CPU has had an instruction for it since 2008.

bits.OnesCount64(x)                              // population count
bits.TrailingZeros64(x)                          // index of the lowest set bit
bits.LeadingZeros64(x)                           // 63 - floor(log2(x))
bits.Len64(x)                                    // bits needed to represent x

// A bitset as a set of small integers. Iterating its members costs one
// step per PRESENT element, not per possible one.
type Set uint64

func (s Set) Add(i int) Set      { return s | 1<<i }
func (s Set) Has(i int) bool     { return s&(1<<i) != 0 }
func (s Set) Union(o Set) Set    { return s | o }
func (s Set) Inter(o Set) Set    { return s & o }

func (s Set) Each(f func(int)) {
    for s != 0 {
        i := bits.TrailingZeros64(uint64(s))
        f(i)
        s &= s - 1                               // clear the lowest set bit
    }
}

// Bitmask DP: the travelling salesman over 20 cities. The state is
// (set of cities visited, city we are standing in), so the table is
// 2^n * n entries -- exponential, but 20 million is a table rather than
// a fantasy, and the naive enumeration is 20! which is not.
dp := make([][]int32, 1<<n)
for mask := range dp {
    dp[mask] = make([]int32, n)
}

// Iterating every SUBSET of a mask, in O(3^n) over all masks rather
// than O(4^n) -- worth knowing, and impossible to derive on the spot:
for sub := mask; sub > 0; sub = (sub - 1) & mask {
    // sub runs over every non-empty subset of mask, descending
}

# bits.py — Python ints are arbitrary precision, so a bitset is just an
# int and it never overflows. That makes some of these unusually clean.

x.bit_count()                                    # popcount, 3.10+
x.bit_length()                                   # bits needed; 0 for 0
(x & -x).bit_length() - 1                        # index of the lowest set bit

# A sieve as a single integer: set operations on millions of bits with
# one machine-word-at-a-time loop in C.
mask = 0
mask |= 1 << i                                   # add i
mask &= ~(1 << i)                                # remove i
present = mask >> i & 1                          # test i

# IntFlag makes permission masks readable, which is the difference
# between a bit trick and a maintainable one.
from enum import IntFlag, auto

class Perm(IntFlag):
    READ = auto()                                # 1
    WRITE = auto()                               # 2
    ADMIN = auto()                               # 4

granted = Perm.READ | Perm.WRITE
Perm.WRITE in granted                            # True
granted & ~Perm.WRITE                            # revoke
repr(granted)                                    # <Perm.READ|WRITE: 3>

# The XOR trick: every value appears twice except one. XOR is
# associative, commutative, and self-cancelling, so the pairs vanish.
from functools import reduce
from operator import xor
unpaired = reduce(xor, values)                   # O(n) time, O(1) space

// Bits.java — Integer and Long carry the intrinsics; BitSet handles the
// cases that do not fit in 64 bits.

Integer.bitCount(x);                             // popcount
Integer.numberOfTrailingZeros(x);                // index of lowest set bit
Integer.highestOneBit(x);                        // the bit itself, not its index
Long.bitCount(y);

// EnumSet is a bitmask wearing a Set interface: for enums with 64 or
// fewer constants it is a single long, and every operation is one
// instruction. It is faster than HashSet by an order of magnitude and
// reads as ordinary collection code.
EnumSet<Permission> granted = EnumSet.of(Permission.READ, Permission.WRITE);
granted.contains(Permission.ADMIN);              // one AND
granted.addAll(EnumSet.allOf(Permission.class));

// BitSet for large, sparse-ish sets of integers: a long[] under the
// hood, so a million flags is 128 KB rather than the ~16 MB a
// HashSet<Integer> would need.
BitSet seen = new BitSet(1_000_000);
seen.set(id);
seen.get(id);
seen.cardinality();                              // popcount over the whole array
seen.stream().forEach(i -> ...);                 // only the set bits

// The trap that survives into production: Java has no unsigned int, so
// >> is arithmetic (sign-extending) and >>> is logical. Using >> on a
// value whose top bit is set fills with ones, and a binary search
// written with (lo + hi) >> 1 breaks exactly where (lo + hi) >>> 1 does not.

Snippets in Go, Python and Java — switch in the bar, or press g / p / j.

// stdlib.go — the generic packages added in 1.21 and 1.23 replaced most
// of the hand-written loops people used to write.

slices.Sort(xs)                                  // ordered types
slices.SortFunc(xs, cmpFn)                       // -1 / 0 / +1
slices.SortStableFunc(xs, cmpFn)
i, found := slices.BinarySearch(xs, v)
slices.Contains(xs, v)                           // O(n) -- know that it is
slices.Index(xs, v)
slices.Reverse(xs)
slices.Max(xs); slices.Min(xs)
xs = slices.Compact(xs)                          // drop adjacent duplicates
xs = slices.Insert(xs, i, v)
xs = slices.Delete(xs, i, j)
ys := slices.Clone(xs)                           // shallow, but detaches the array
slices.Equal(xs, ys)

maps.Keys(m)                                     // an iterator (1.23+), not a slice
slices.Sorted(maps.Keys(m))                      // the deterministic-iteration idiom
maps.Clone(m); maps.Equal(a, b)

// Iterators (1.23) let you write algorithms that compose without
// materialising intermediate slices.
func Filter[T any](s iter.Seq[T], keep func(T) bool) iter.Seq[T] {
    return func(yield func(T) bool) {
        for v := range s {
            if keep(v) && !yield(v) {
                return                           // the consumer stopped early
            }
        }
    }
}

// container/heap and container/list are the two pre-generics holdouts:
// both use `any` and both need a type assertion on the way out. The
// heap is still worth using; the list almost never is.

# stdlib.py — the modules that replace hand-written algorithms.

# collections
from collections import Counter, defaultdict, deque, OrderedDict
Counter(words).most_common(10)                   # top-k, via a heap
Counter(a) & Counter(b)                          # multiset intersection
deque(maxlen=1000)                               # O(1) both ends, ring buffer

# heapq / bisect — the two algorithm modules
import bisect, heapq
heapq.nlargest(k, xs, key=...)                   # O(n log k)
heapq.merge(*sorted_iters)                       # lazy k-way merge
bisect.insort(sorted_list, v)                    # keep a list sorted

# itertools — the combinatorics, all lazy
from itertools import accumulate, chain, groupby, islice, pairwise, product
list(pairwise("abcd"))                           # [('a','b'),('b','c'),('c','d')]
list(accumulate(xs))                             # prefix sums
# groupby needs its input SORTED by the same key -- it groups RUNS,
# not values, and that is the single most common misuse in the module.
for key, grp in groupby(sorted(rows, key=k), key=k):
    ...

# functools — memoisation and comparators
from functools import cache, cmp_to_key, lru_cache, reduce

# graphlib — topological sorting, since 3.9
from graphlib import TopologicalSorter

# The one to know about but rarely need: array and memoryview give you
# a flat buffer and a zero-copy view of it, which is how you avoid
# copying a large bytes object into a slice.
view = memoryview(buf)[1024:2048]                # no copy at all

// Stdlib.java — the JDK's collection utilities, and which to trust.

List.of(a, b, c);                                // immutable, null-hostile, compact
Map.of(k1, v1, k2, v2);                          // up to 10 pairs; Map.ofEntries beyond
List.copyOf(mutable);                            // defensive snapshot

Collections.unmodifiableList(l);                 // a VIEW: the original can still change

Arrays.sort(a);                                  // dual-pivot quicksort (primitives)
Arrays.parallelSort(a);                          // fork/join above ~8k
Arrays.fill(a, v);
Arrays.binarySearch(a, v);                       // negative encodes the insertion point
Arrays.stream(a).sum();                          // IntStream: no boxing

// Streams: excellent for expressing the pipeline, and worth measuring
// before putting in a hot loop -- a plain for loop over an int[] is
// usually faster than the equivalent stream, sometimes by a lot.
Map<Dept, List<User>> byDept = users.stream()
        .collect(Collectors.groupingBy(User::dept));
Map<Dept, Long> counts = users.stream()
        .collect(Collectors.groupingBy(User::dept, Collectors.counting()));

// The utility that saves the most code, and the one most often missed:
map.merge(key, 1, Integer::sum);                 // count
map.computeIfAbsent(key, k -> new ArrayList<>()).add(v);   // group
map.compute(key, (k, v) -> v == null ? init : update(v));

// Across threads: ConcurrentHashMap, and its atomic compute methods.
// Never Collections.synchronizedMap, which serialises every call and
// still needs external locking for check-then-act.
concurrent.computeIfAbsent(key, k -> expensive(k));   // atomic, per key

// pitfalls.go — the three that cause real incidents, and their fixes.

// 1. The slice that pins a hundred megabytes.
func ExtractIDBad(r io.Reader) []byte {
    data, _ := io.ReadAll(r)                     // 100 MB
    return data[10:42]                           // 32 bytes; the 100 MB stays alive
}

func ExtractID(r io.Reader) []byte {
    data, _ := io.ReadAll(r)
    return slices.Clone(data[10:42])             // 32 bytes, and only 32
}

// 2. The loop variable that used to be shared. Fixed in Go 1.22 -- each
// iteration now gets its own variable -- but the same shape still bites
// when you take the address of a range value over a slice of structs.
for _, item := range items {
    out = append(out, &item)                     // 1.22+: fine. Before: all same
}

// 3. Growing a map forever. A map that peaked at 10 million keys keeps
// its buckets after every key is deleted.
if len(cache) < cap(keys)/4 {                    // live set is a quarter of peak
    fresh := make(map[string]Entry, len(cache))
    maps.Copy(fresh, cache)
    cache = fresh                                // the old buckets become garbage
}

// 4. Not a leak, but the most common performance bug: no capacity hint.
//    var out []Row               -> ~log2(n) reallocations and copies
//    out := make([]Row, 0, n)    -> one allocation

# pitfalls.py — the quadratic loops that look linear.

# 1. Membership on a list. This is O(n*m) and reads as if it were O(n).
missing = [x for x in candidates if x not in known_list]     # slow
known = set(known_list)                                      # once, O(m)
missing = [x for x in candidates if x not in known]          # O(n)

# 2. A list used as a queue.
while queue:
    item = queue.pop(0)                          # O(n) each: shifts everything
# from collections import deque; queue = deque(...); queue.popleft()

# 3. String building.
out = ""
for row in rows:
    out += render(row)                           # O(n^2) copying
out = "".join(render(row) for row in rows)       # O(n)

# 4. The mutable default: evaluated ONCE, at definition time, and then
# shared by every call that does not pass one.
def add(item, bucket=[]):                        # wrong
    bucket.append(item)
    return bucket

def add(item, bucket=None):                      # right
    if bucket is None:
        bucket = []
    bucket.append(item)
    return bucket

# 5. Mutating a list while iterating it. The iterator holds an index,
# so a removal makes it skip the next element -- silently.
for x in list(xs):                               # iterate a copy, or
    if drop(x):
        xs.remove(x)
xs = [x for x in xs if not drop(x)]              # better: one pass, no removal

// Pitfalls.java — the ones that survive code review.

// 1. A mutable key. After the set() the entry is unreachable AND
// un-removable: it hashes to a different bin than the one it is in.
Map<Point, String> map = new HashMap<>();
Point p = new Point(1, 2);
map.put(p, "a");
p.setX(9);                                       // the entry is now lost forever
map.get(p);                                      // null
map.remove(p);                                   // does nothing; the memory stays
// Fix: record Point(int x, int y) {} -- immutable, equals and hashCode free

// 2. Comparator by subtraction. Fine until the values are large.
Comparator<Item> broken = (a, b) -> a.id() - b.id();
Comparator<Item> fixed = Comparator.comparingInt(Item::id);

// 3. Removing while iterating. Fail-fast, so at least it throws.
for (String s : list) if (drop(s)) list.remove(s);   // ConcurrentModification
list.removeIf(this::drop);                           // one pass, correct

// 4. Boxing in a hot loop. Every ++ unboxes, adds, and boxes again --
// an allocation per iteration above the Integer cache of 127.
Map<String, Integer> counts = new HashMap<>();
counts.merge(key, 1, Integer::sum);              // still boxes, but once per call
// For a fixed key space, int[] indexed by an enum ordinal boxes never.

// 5. Arrays.asList is a fixed-size VIEW over the array, not a copy.
List<String> view = Arrays.asList(array);
view.add("x");                                   // UnsupportedOperationException
List<String> real = new ArrayList<>(Arrays.asList(array));

// 6. Integer.parseInt in a stream over millions of rows: the exception
// path fills in a stack trace, which is thousands of times more
// expensive than the parse. Validate before parsing on hot paths.