csGraph

A function that calls itself on a smaller subproblem. The call stack manages the rest.

O(1) random access, O(n) insertion — the trade-off every other structure is a response to.

O(1) insertion at a pointer, O(n) access — the inverse trade-off of an array.

A linked list with a prev pointer — O(1) deletion from anywhere you hold a reference.

LIFO discipline — the structure your language runtime uses to execute every function call.

FIFO discipline — the structure behind every waiting system from print jobs to HTTP requests.

Double-ended queue — O(1) push/pop at both ends. The basis for sliding window maximum.

A stack that enforces sorted order — next-greater-element in O(n) instead of O(n²).

Key-to-slot mapping via a hash function — O(1) average lookup at the cost of O(n) worst case.

A hash table without values — O(1) membership testing. The structure behind cycle detection.

A node with at most two children — the recursive structure underlying half of computer science.

A binary tree with the invariant left < root < right. Binary search, but navigable.

A BST that self-balances on insert via rotations — guarantees O(log n) where naive BST gives O(n).

A binary tree where parent ≥ all descendants. O(1) peek-max, O(log n) insert and extract.

Queue ordered by priority, not arrival time — the ADT. Heap is the canonical implementation.

A tree where the path from root spells a prefix. Prefix lookups in O(key length), not O(n log n).

A tree over an array for range queries — sum, min, max over [l, r] in O(log n).

A compact structure for prefix sums — same O(log n) as segment tree, half the code and memory.

Nodes with arbitrary connections — the most general structure, reducible to almost any problem.

A graph where edges have direction — dependencies, state machines, version control DAGs.

A graph where edges have cost — every shortest-path and MST problem lives here.

Tracks connected components — O(α) amortized per operation, essentially O(1) in practice.

Evicts the least recently used item — a hash table + doubly linked list. O(1) get and put.

DFS on a binary tree — preorder, inorder, postorder are one algorithm with a visit point change.

Explore as deep as possible before backtracking — a stack (or recursion) is the only bookkeeping.

Explore all neighbors before going deeper — finds shortest paths in unweighted graphs.

Halve the search space each step — O(log n), the trade-off you get for keeping data sorted.

Two indices walking toward each other (or together) — reduces O(n²) pair problems to O(n).

A subarray of fixed or variable size that slides forward — O(n) solutions to O(n²) problems.

Split the problem, solve each half recursively, combine — the pattern behind merge sort and FFT.

Recursion with caching — break into overlapping subproblems, trade space for exponential time.

Top-down DP — write the recursion naturally, add a cache. Compute on demand, store results.

Bottom-up DP — compute subproblems in order, store in a table. No recursion, better cache use.

Make the locally optimal choice at each step — works when greedy is provably globally optimal.

Try a choice, recurse, undo if it fails — DFS on the space of partial solutions.

Operate directly on binary representation — XOR, shifts, masks. O(1) tricks replacing O(n) loops.

Split, sort recursively, merge — O(n log n) guaranteed. The only sort that handles linked lists.

Partition around a pivot, sort recursively — O(n log n) average, fastest in practice.

Build a heap, extract-max n times — O(n log n) guaranteed, O(1) space. Uses the heap invariant.

Greedy shortest path from one source — O((V+E) log V) with a min-heap. Fails on negative edges.

Linear order of a DAG so every edge points forward — DFS + reverse exit time.

The cheapest set of edges connecting all nodes — Kruskal's uses union-find, Prim's uses a heap.

Detect whether a graph has cycles — DFS with three-color marking (directed) or union-find (undirected).

Traversing the document tree — the same DFS you learned in DSA, wearing a browser hat.

React's reconciler as a singly-linked list of work units — tree traversal made interruptible.