Glossary

A map from each vertex to the list of its neighbours.

The default graph representation. Space is O(V + E), and iterating one vertex’s neighbours costs O(degree). Prefer it unless the graph is dense or you need constant-time edge lookup.

Lesson 17

A V × V grid where each cell says whether an edge exists.

Gives O(1) edge lookup at a cost of O(V²) space, so it wastes memory on sparse graphs. Worth it when the graph is dense or when you need to test arbitrary pairs repeatedly.

Lesson 17

The average cost per operation across a whole sequence, guaranteed.

Array push is amortised O(1): one call may resize and cost O(n), but any n pushes total O(n). This is a worst-case guarantee over a sequence, unlike hash-map O(1), which is a genuine average that can degrade. Using the two words interchangeably is a small tell.

Lesson 02

A rearrangement of another string’s characters.

Detected by comparing character counts, or by comparing sorted forms. The sorted form or a 26-slot count array makes a canonical key, which is what lets you group anagrams with a hash map.

Lesson 03

Any node on the path from a given node up to the root.

A node’s parent, its parent’s parent, and so on. Relevant to BST validation, where a value must respect every ancestor’s constraint and not only its parent’s.

Lesson 14

Extra memory an algorithm uses, not counting the input or output.

What people mean by “space complexity” in practice. The recursion stack counts toward it; the returned result conventionally does not. Say which convention you are using if it could matter.

Lesson 01

Try a choice, recurse, then undo it and try the next.

The template is choose, explore, un-choose. Generates subsets, permutations, combinations and solves constraint puzzles. Every piece of state you change must be restored, and the working array must be copied into the results.

Lesson 19

A tree whose subtree heights differ by at most a small constant.

What makes tree operations O(log n). Without balancing, inserting sorted data produces a degenerate tree and everything becomes O(n). Real libraries use AVL or red-black trees; in an interview, saying “assuming the tree is balanced” covers it.

Lesson 15

The input a recursive function answers without recursing.

Without one, recursion never stops. In dynamic programming the base case is often the entire insight — best[0] = 0 in coin change is what makes the rest of the table correct, and a wrong base case produces answers that are uniformly off by one.

Lesson 11

A shortest-path algorithm that tolerates negative edge weights.

Relaxes every edge V - 1 times, giving O(V × E). Slower than Dijkstra but handles negative weights, and one extra pass detects a negative cycle. Reach for it only when weights can be negative.

Lesson 18

Breadth-first search: explore in order of distance, using a queue.

The only traversal that finds shortest paths in an unweighted graph, because it reaches every node at its minimum distance. Mark nodes visited when you enqueue them, and process one level at a time when the answer is a step count.

Lesson 17

A JavaScript number type with no width limit.

Written with an n suffix, as in 1n << 40n. Needed when bitwise work exceeds 32 bits, since the ordinary operators truncate. Roughly an order of magnitude slower than numbers, and cannot be mixed with them in an expression.

Lesson 24

A complete binary tree kept in an array, with the best value on top.

A parent is always better than its children, which makes peek O(1) and push/pop O(log n). Children of index i live at 2i+1 and 2i+2. JavaScript has no built-in heap, so this is the one structure you must be able to write from memory.

Lesson 16

Halve a sorted range repeatedly until the target is found.

O(log n). Use one form consistently: inclusive bounds with while (lo <= hi) and mid = lo + ((hi - lo) >> 1). Every branch must exclude mid, or the loop can spin forever.

Lesson 12

Binary search the range of possible answers rather than the input.

Applies when a candidate answer can be checked quickly and feasibility is monotonic — if x works then everything larger works. That makes the feasibility function a sorted array of booleans whose boundary you can find. This is the highest-value under-practised technique in the course.

Lesson 12

A tree where every left value is smaller and every right value larger.

Gives O(log n) search, insert and delete when balanced. An in-order traversal emits the values in sorted order, which answers a surprising number of questions. Validation requires threading a range down through the recursion, not just comparing with the parent.

Lesson 15

A graph whose vertices split into two groups with no edge inside a group.

Equivalent to being two-colourable, and detectable with a BFS or DFS that alternates colours. A conflict during colouring proves an odd-length cycle exists, which is what makes the graph not bipartite.

Lesson 17

An integer used as a set of up to 31 boolean flags.

Bit i being set means member i is present. Test with mask & (1 << i), add with |, remove with & ~. Iterating mask from 0 to 2ⁿ - 1 enumerates every subset, which is practical to about n = 20.

Lesson 24

Dynamic programming built as a table from the smallest subproblem upward.

Also called tabulation. Avoids recursion entirely, so there is no stack limit, and it makes space optimisation obvious — once you see that a row only needs the row above, the table collapses to one or two variables.

Lesson 20

See BFS.

Explores a graph level by level using a queue, visiting nodes in order of distance from the start.

Lesson 17

One slot of a hash table, holding the keys that hash to it.

Collisions land in the same bucket and are resolved by chaining or probing. Also the name of a technique in its own right: bucketing values by a bounded key, as in counting sort or bucketing by frequency to find the top k in O(n).

Lesson 04

The stack of function calls currently in progress.

Each call pushes a frame holding its parameters and local variables. Recursion depth is therefore memory, which is why a tree traversal is O(h) space, and why very deep recursion throws RangeError: Maximum call stack size exceeded.

Lesson 11

A normalised representation that makes equivalent things identical.

The whole art of hash-map grouping. Anagrams share a sorted-letters form; points on a line share a slope; island shapes share a set of coordinates relative to their first cell. Choosing the canonical key is the insight in these problems.

Lesson 04

A function that tells a sort which of two values comes first.

Returns negative, zero or positive. JavaScript’s default converts to strings, so [1, 2, 10].sort() gives [1, 10, 2] — always pass (a, b) => a - b for numbers. Sometimes the comparator is the whole solution, as in arranging numbers to form the largest value.

Lesson 13

Every level full except possibly the last, which fills left to right.

The shape a binary heap maintains, and the reason a heap can live in a flat array with no pointers: the structure is implied by the indices.

Lesson 16

A maximal group of vertices reachable from one another.

Counted by running a search from each unvisited vertex, or with union-find. Union-find is the better choice when edges arrive one at a time; BFS is better when you also need distances.

Lesson 17

O(1): the cost does not grow with the input.

Array indexing, hash lookups, arithmetic. “Constant” does not mean fast — a hash lookup has a real constant factor and can lose to a short linear scan — only that the cost stops growing.

Lesson 01

Sort by counting occurrences of each value, not by comparing.

O(n + k) for values in a bounded range k, which beats the O(n log n) comparison bound because it never compares two elements. Only usable when the range of values is small and known.

Lesson 13

A path that returns to where it started.

In an undirected graph, union-find detects one when an edge joins two already-connected vertices. In a directed graph you need three colours, or a topological sort that fails to emit every vertex — a two-state visited check wrongly reports a diamond as a cycle.

Lesson 17

Directed acyclic graph: directed edges, no cycles.

The structure that makes a topological sort possible. Dependency graphs, build orders and course prerequisites are DAGs, and detecting that a graph is not one is usually the real question.

Lesson 18

A tree that has become a single chain.

Every node has one child, so height equals node count and every operation degrades to O(n). Inserting already-sorted data into an unbalanced BST produces exactly this, which is the argument for self-balancing trees.

Lesson 15

A double-ended queue: O(1) push and pop at both ends.

Needed for the sliding-window-maximum pattern, where a monotonic deque keeps the current best in O(1) while the window moves. In JavaScript an array with shift is not a deque, because shift is O(n).

Lesson 10

Depth-first search: follow one path as far as it goes, then back up.

Answers reachability, components, cycles, and anything where a node’s result is assembled from its children. It does not find shortest paths — choosing DFS for a shortest-path question is a substantive error, not a stylistic one.

Lesson 17

Add at a range’s start, subtract past its end, then take a running sum.

The prefix-sum identity run backwards. Turns many range updates into O(1) each, with one final pass to materialise the real values. Ideal when coordinates are small bounded integers, because it removes the need to sort.

Lesson 07

Cheapest paths from one source, with non-negative weights.

Repeatedly settle the nearest unsettled vertex and relax its edges. O(E log V) with a binary heap. Negative weights break it, because a settled vertex could later be improved — use Bellman–Ford instead.

Lesson 18

A graph whose edges have a direction.

An edge from a to b does not imply one from b to a. Getting the direction right is the most common error in prerequisite problems: “to take a you need b” means the edge runs b → a.

Lesson 17

See union-find.

A structure tracking a partition of elements into non-overlapping groups, supporting fast merge and same-group queries.

Lesson 18

Split the problem, solve the parts, combine the results.

Merge sort and quicksort are the canonical examples, and binary search is the degenerate case where one half is discarded rather than solved. The recurrence T(n) = 2T(n/2) + O(n) gives O(n log n).

Lesson 13

A throwaway node placed before a list’s real head.

Removes every special case where the first node might change, because even the head then has a predecessor. Build onto the dummy and return dummy.next. Using one is the difference between clean linked-list code and a thicket of null checks.

Lesson 08

A one-pass three-way partition.

Maintains three regions with lo, mid and hi pointers. Sorts an array of three distinct values in one pass, and is the partition scheme that makes quicksort robust against many duplicate keys. On swapping a value in from hi, do not advance mid — the new value is unexamined.

Lesson 13

An array that grows as needed by reallocating.

What a JavaScript array is. Appending is amortised O(1) because capacity typically doubles, so the occasional O(n) copy is spread across many cheap appends.

Lesson 02

Cache the answers to overlapping subproblems instead of recomputing them.

Requires overlapping subproblems and optimal substructure. Write the honest recursion first, cache it, then convert to a table and shrink the table. Doing it in that order means you always have something working, which matters more under time pressure than a memorised table.

Lesson 20

The fewest single-character edits turning one string into another.

Also called Levenshtein distance. A two-dimensional table over the two string prefixes, O(mn). A match is free and moves diagonally; otherwise take the cheapest of insert, delete and substitute.

Lesson 20

Proof that swapping in the greedy choice never makes a solution worse.

The standard way to justify a greedy algorithm. Take any optimal solution, replace one of its choices with the greedy one, and show it is still valid and no worse. Being able to say this in a sentence is what makes a greedy answer credible.

Lesson 21

O(2ⁿ): cost doubles with each added element.

Practical only to about n = 25. It is the correct answer when the output itself is exponential, as with listing every subset. When the question asks for a count or a best value rather than a list, subproblems repeat and dynamic programming collapses it to polynomial.

Lesson 01

Two pointers moving at different speeds through the same sequence.

Finds the middle of a list in one pass, and detects a cycle: the fast pointer gains exactly one position per step, so in a loop it cannot skip past the slow one. Also called the tortoise and hare, or Floyd’s algorithm.

Lesson 08

First in, first out. The queue discipline.

The order BFS needs, because it processes nodes in the order they were discovered, which is the order of increasing distance.

Lesson 10

Consume a connected region of a grid with a search from one cell.

The engine behind island counting and region colouring. Marking cells as you visit them — often by overwriting them — is the cheapest visited-set available. Mark before recursing, or the same cell is entered repeatedly.

Lesson 23

Shortest paths between every pair of vertices.

O(V³) with three nested loops, the outermost over the intermediate vertex. Simple to write and fine for a few hundred vertices. Handles negative edges, though not negative cycles.

Lesson 18

Take the locally best option and never reconsider.

Astonishingly short when valid, and confidently wrong when not, with no error to warn you. Justify it with an exchange argument or a bound before writing it. Coins [1,3,4] for 6 is the counterexample worth keeping ready: greedy says three coins, the answer is two.

Lesson 21

Two different keys hashing to the same bucket.

Unavoidable, since there are more possible keys than buckets. Resolved by chaining or probing. Enough collisions degrade lookups from O(1) to O(n), which is why hash-map performance is an average rather than a guarantee.

Lesson 04

A structure giving near-constant lookup by key.

Trades memory for speed, and turns a repeated O(n) search into O(1). Three shapes cover most uses: a set for membership, a counter for frequency, and a map from canonical key to group. In JavaScript, prefer Map over a plain object when keys may be numbers or collide with inherited names.

Lesson 04

Turn an arbitrary array into a valid heap.

Sifting down from the last parent to the root is O(n), not O(n log n), because most nodes are near the bottom and sift only a short distance. A useful fact when you are asked to build a heap from existing data.

Lesson 16

The number of edges on the longest path from a node down to a leaf.

Determines the recursion depth of a tree traversal, hence O(h) space. O(log n) when balanced, O(n) when degenerate. Distinguish it from depth, which is measured from the root downward.

Lesson 14

Left subtree, then the node, then the right subtree.

On a binary search tree this emits values in sorted order, which is the answer to a whole family of questions: the kth smallest, validating a BST, and converting a BST to a sorted list.

Lesson 14

Modifying the input rather than allocating a copy.

Usually means O(1) auxiliary space. Achieved with a write pointer that compacts kept elements, or by swapping. Note that JavaScript’s sort mutates in place but is not O(1) space internally.

Lesson 02

A start and end pair, usually representing a range of time.

Two intervals overlap when a.start < b.end && b.start < a.end. Whether merely touching counts decides < versus <=, and the problem statement always picks one convention — confirm which before writing anything.

Lesson 22

A condition your code keeps true at every step.

The way to reason about a loop without tracing it. Binary search’s invariant is that the target, if present, lies within [lo, hi]. Sliding window’s is that the window is valid after the shrink loop. Stating the invariant is usually faster than debugging.

Lesson 12

Maximum subarray sum in one pass.

At each element, either extend the running subarray or start fresh, whichever is larger. It is dynamic programming with the table collapsed to a single variable. Initialise from the first element, not zero, or an all-negative array wrongly answers 0.

Lesson 21

Topological sort by repeatedly taking vertices with no prerequisites.

Count in-degrees, queue everything at zero, and decrement dependents as you emit. O(V + E). Emitting fewer vertices than exist proves a cycle, which is how one algorithm answers both “what order” and “is it possible”.

Lesson 18

Count set bits by repeatedly clearing the lowest one.

n &= n - 1 erases the lowest set bit, so the loop runs once per set bit rather than once per bit position. The same identity gives a one-line power-of-two test, since a power of two has exactly one set bit.

Lesson 24

Choose items under a capacity limit to maximise value.

The archetypal two-dimensional dynamic programming shape: items along one axis, remaining capacity along the other. In the 0/1 variant each item is used at most once, which means iterating capacity downward; the unbounded variant allows reuse and iterates upward.

Lesson 20

Build a minimum spanning tree by adding the cheapest safe edge.

Sort every edge by weight and add it unless it would form a cycle, which union-find tests in near-constant time. O(E log E). Prim’s algorithm grows a single tree instead and is preferable on dense graphs.

Lesson 18

Last in, first out. The stack discipline.

The order matching nested structures: brackets, function calls, undo history. When the most recent unresolved thing is the one you need next, you want a stack.

Lesson 09

O(n): cost grows in proportion to the input.

One pass. The target for most array and string problems, and usually reached by replacing a nested loop with two pointers, a sliding window, or a hash map.

Lesson 01

O(n log n): the comparison-sorting bound.

What sorting costs, and therefore what any sort-then-sweep solution costs. Comfortable up to several million elements. If your solution is O(n log n) because of a sort, ask whether the sort is actually needed — sometimes a hash map or a heap avoids it.

Lesson 01

A chain of nodes, each holding a value and a reference to the next.

O(1) insertion and removal given the node, but O(n) access by position, since you must walk. Four moves solve nearly every question: reverse, find with two speeds, merge, and detect a cycle.

Lesson 08

The ratio of stored entries to available buckets.

When it grows too high, collisions become common and lookups degrade, so the table resizes and rehashes everything. That resize is why hash-map O(1) is amortised as well as average.

Lesson 04

The longest sequence of characters appearing in both strings in order.

A two-sequence dynamic programming table, O(mn). Matching characters extend the diagonal; otherwise take the better of dropping one character from either string. Distinct from longest common substring, which must be contiguous.

Lesson 20

The longest strictly increasing sequence within an array, not necessarily adjacent.

The O(n²) version compares each element with all earlier ones. The O(n log n) version keeps an array of the smallest possible tail for each achievable length and binary searches it — note that this array’s length is the answer, but its contents are not necessarily a valid subsequence.

Lesson 20

The deepest node having both given nodes as descendants.

On a general tree, recurse into both subtrees and return the node where the two searches meet. On a binary search tree it is far simpler: walk down until the two values fall on opposite sides, which is O(h) with no recursion.

Lesson 14

Cache a function’s results so repeated calls are free.

Top-down dynamic programming. Keeps the shape of your recursion and usually turns exponential into polynomial with three added lines. Almost always the right first step, and often the right last one too.

Lesson 20

A stack whose values stay sorted, where popping computes the answer.

Answers “next greater”, “previous smaller”, spans and histogram rectangles. Each index is pushed and popped at most once, so it is O(n) despite the inner while — an amortised argument worth being able to state, since the code looks quadratic. Store indices, not values.

Lesson 09

BFS seeded with every starting point before the loop begins.

Makes all sources expand in lockstep, so “how long until everything is reached” and “distance to the nearest source” are one linear search rather than one per source. Recognising a problem as multi-source is usually the entire insight.

Lesson 23

An optimal solution is built from optimal solutions to subproblems.

One of the two conditions dynamic programming needs, alongside overlapping subproblems. When it fails, caching subproblem answers does not help, because the best local answer is not part of the best global one.

Lesson 20

The same subproblem is reached along several different routes.

The tell that dynamic programming applies. Naive Fibonacci recomputes fib(5) many times; caching it collapses exponential work to linear. If subproblems never repeat, caching buys nothing and you want divide and conquer instead.

Lesson 20

Flattening a union-find chain during a lookup.

While walking up to the root, repoint each node at its grandparent, so later lookups are shorter. Combined with union by size it makes each operation effectively constant — formally the inverse Ackermann function, which is below five for any realistic input.

Lesson 18

An arrangement of elements where order matters.

There are n! of them. Generated by backtracking that starts its loop from index 0 each time and tracks which elements are used — and both pieces of that state must be undone, not just the array.

Lesson 19

The value quicksort partitions around; also the rotation point of a rotated array.

In quicksort, a poor pivot choice gives O(n²); randomising or taking a median makes that vanishingly unlikely. In a rotated sorted array, the pivot is where the order breaks, and binary search finds it by comparing the middle against the right end.

Lesson 13

Both subtrees first, then the node.

The order you need whenever a node’s answer depends on results coming up from below: height, diameter, balance, maximum path sum. The recurring shape is to return one value to the parent while updating an answer held outside the recursion.

Lesson 14

A running total, so any range sum becomes one subtraction.

Build in O(n), then answer any range in O(1). Make the array one longer with prefix[0] = 0 to remove edge cases. Paired with a hash map of prefix counts it also counts subarrays hitting a target sum — which works with negative numbers, where a sliding window cannot.

Lesson 07

A collection that always hands you the best item next.

Normally implemented as a binary heap. JavaScript ships none, so you write it. Pairs with sorting in a great many greedy algorithms: the sort fixes the order of decisions, the heap answers what is currently best.

Lesson 16

Abandoning a search branch that cannot lead to an answer.

What makes exponential search usable. Two prunes almost always apply: sort the candidates and break once one exceeds what remains, and check feasibility before recursing rather than at the top of the call.

Lesson 19

First in, first out. Add at the back, remove from the front.

The structure BFS runs on. In JavaScript, do not implement one with shift() — that is O(n) and silently makes your BFS quadratic. Use a head index that only moves forward, or swap two arrays per level.

Lesson 10

Find the kth smallest element without fully sorting.

Quicksort that recurses into only the side containing the target, giving O(n) average and O(n²) worst case. Worth naming when asked for the kth largest, even if you then write the simpler heap solution.

Lesson 13

An equation defining a value in terms of smaller cases.

The heart of a dynamic programming solution. Getting the recurrence and the base cases right is the whole problem; whether you then implement it top-down or bottom-up is an implementation detail.

Lesson 20

A function that calls itself on a smaller input.

Needs a base case and progress toward it. Costs O(depth) stack space, which is real memory and part of your space complexity. Natural for trees and graphs; convert to an explicit stack when the depth could be large.

Lesson 11

Improving a recorded distance when a cheaper route is found.

The core step of Dijkstra and Bellman–Ford: if going through u reaches v more cheaply than the best known, record the better value. Both algorithms are just different disciplines for choosing which edge to relax next.

Lesson 18

A fake value added to remove a special case.

A dummy list head so the first node has a predecessor; a zero-height bar appended to a histogram so the monotonic stack flushes without a second loop; ±Infinity as unreachable bounds. Almost always simpler than the branch it replaces.

Lesson 09

Restoring the heap property by moving a value toward the leaves.

Used after popping, when the last element is moved to the root. Repeatedly swap with the better of its two children until neither is better. O(log n).

Lesson 16

Restoring the heap property by moving a value toward the root.

Used after pushing, when the new value sits at the end of the array. Repeatedly swap with the parent while it is better. O(log n).

Lesson 16

A range whose two edges only ever move forward.

For contiguous subarray and substring questions. Because neither edge moves backwards, total work is at most 2n. Record the answer after shrinking for a longest-valid question, and before shrinking for a shortest-valid one. Needs a monotonic condition, which negative numbers can break.

Lesson 06

How memory use grows with the input.

Count the recursion stack, count every copy you allocate, and conventionally exclude the output. A 26-letter count array is O(1), not O(n). This is the half candidates forget, and interviewers ask precisely because of that.

Lesson 01

A sort that preserves the original order of equal elements.

Matters when sorting by one key after another, since the earlier ordering survives within ties. Merge sort is stable, quicksort is not, and JavaScript’s sort has been required to be stable since ES2019.

Lesson 13

Last in, first out. Add and remove at the same end.

Cheap in JavaScript, since push and pop are both amortised O(1). Use it whenever the most recent unresolved item is the one you need next: bracket matching, expression evaluation, and iterative traversal.

Lesson 09

Recursion deeper than the call stack allows.

Throws RangeError: Maximum call stack size exceeded, typically after roughly ten thousand frames. A recursive flood fill over a very large grid hits it. The fix is an explicit stack or a BFS, and mentioning the risk is worth a sentence in an interview.

Lesson 11

Elements kept in order but not necessarily adjacent.

Distinct from a subarray or substring, which must be contiguous. Misreading one for the other changes the problem entirely — contiguity is the signal for a sliding window, while a subsequence usually means dynamic programming.

Lesson 20

Turn intervals into +1/-1 events and scan them in time order.

Answers “how many are happening at once” without merging anything. The tie-break is the whole difficulty: process an end before a start at the same instant if a resource frees up immediately.

Lesson 22

See bottom-up.

Filling a dynamic programming table iteratively from the base cases upward, with no recursion.

Lesson 20

Dynamic programming as recursion plus a cache.

Also called memoisation. Preserves the natural recursive structure and only computes the subproblems actually needed, which can be far fewer than a full table. Its limit is recursion depth.

Lesson 20

An ordering of a DAG where every edge points forward.

Answers dependency, prerequisite and build-order questions in O(V + E), and detects cycles for free. Only exists for an acyclic graph, so “is this possible” and “in what order” are the same algorithm with different return values.

Lesson 18

A tree keyed by character, where a path spells a word.

Lookup, insert and prefix search all cost O(length), independent of how many words are stored. The right structure for autocomplete and prefix queries; worth learning once the core patterns are automatic, and not before.

Lesson 15

Two indices replacing a nested loop.

Three flavours: opposite ends closing inward on sorted data, a read and a write pointer compacting in place, and two different speeds for cycle detection. The question to keep asking is what tells you which pointer to move.

Lesson 05

How signed integers are represented in binary.

Negate by flipping every bit and adding one, so ~5 + 1 === -5. It is why (-5).toString(2) is misleading and you should print with (n >>> 0).toString(2) to see the real 32 bits.

Lesson 24

Attaching the smaller union-find tree beneath the larger.

Keeps trees shallow, so find stays fast. Combined with path compression it gives effectively constant-time operations. Union by rank is an equivalent variant tracking depth instead of element count.

Lesson 18

Tracks which elements are in the same group, with fast merging.

Each element points at a parent; following the chain reaches a representative identifying the group. With path compression and union by size, operations are effectively O(1). Choose it over BFS when edges arrive incrementally; choose BFS when you also need distances.

Lesson 18

A node of a graph.

Written V in complexity bounds, with E for edges. Graph traversals are O(V + E) because each vertex is visited once and each edge examined once.

Lesson 17

Bitwise exclusive or: 1 where exactly one input bit is set.

Three properties do all the work: x ^ x === 0, x ^ 0 === x, and order does not matter. That makes “find the element appearing once” an O(1)-space single pass. XOR is really “count each bit position modulo 2”, which generalises to modulo k for elements repeating k times.

Lesson 24