cheatsheet · after you code

Big-O of everything

Use it when: The interviewer asks "what's the complexity?", or you're comparing two approaches.

What each Java container costs

`int[]` (array)

read / write a[i]: O(1)
find a value: O(n)
insert / delete in the middle: O(n) (shift by hand)

`ArrayList`

get(i), set(i, x), size(): O(1)
add(x) at the end: amortized O(1)
add(i, x), remove(i): O(n) (shifts the rest)
contains(x), indexOf(x): O(n)

Java 17 docs ↗

`LinkedList`

add / remove at either end: O(1)
get(i): O(n) (walks from the nearer end)
contains(x): O(n)

Java 17 docs ↗

`ArrayDeque`

push, pop, offer, poll, peek (either end): amortized O(1)
contains(x), remove(x): O(n)

Java 17 docs ↗

`HashMap` / `HashSet`

get, put, remove, containsKey: O(1) avg
iterate everything: O(n + capacity)

Java 17 docs ↗

`TreeMap` / `TreeSet`

get, put, remove, containsKey: O(log n)
floorKey, ceilingKey, firstKey, lastKey: O(log n)

Java 17 docs ↗

`PriorityQueue`

offer, poll: O(log n)
peek, size: O(1)
remove(x), contains(x): O(n)

Java 17 docs ↗

`String` / `StringBuilder`

charAt(i), length(): O(1)
substring(a, b): O(b − a) (copies)
sb.append(x): amortized O(length of x)
s += x inside a loop: O(n²) total: use StringBuilder

Each chapter's tables

Pick a stage, then open just the chapter you want.

01What Happens in Memory2 tables

What lives where, and for how long
	Lives in	Freed when	why
Local primitive (`int i`, `long sum`)	the method's stack frame	the method returns	The value itself sits in the frame, so popping the frame frees it in O(1).
Local reference (`int[] a`, `String s`)	the frame (only the arrow)	the method returns	The frame stores just the reference. The object it points at is separate.
Object or array (`new int[n]`, `new ListNode(5)`)	the heap	the GC finds it unreachable	An object outlives the method that made it while any reference still reaches it.
Static field (`static int[] memo`)	one copy for the whole class	practically never	Whatever a static field refers to stays alive for the whole run, across test cases.
Recursion of depth d	d frames on the stack	each call returns	Stack space is O(d) even when each call does O(1) work.

Everyday memory operations and their cost
	Time	Extra memory	why
Pass an array or object to a method	O(1)	O(1)	Only the reference is copied, never the elements.
`int[] b = a;`	O(1)	O(1)	A second arrow to the same array.
`a.clone()` / `Arrays.copyOf(a, n)`	O(n)	O(n)	A new array; every element is copied.
`new int[n]`	O(n)	O(n)	The JVM fills all n slots with 0 before you see the array.
`new ArrayList<>(path)` snapshot	O(k)	O(k)	k = the path's current length, paid once per saved result.
`s.equals(t)` vs `s == t`	O(n) vs O(1)	O(1)	equals compares characters (stopping at the first difference); == compares only references.
Recursion to depth d	(the calls' own work)	O(d) stack	One frame per call that is still waiting for its child to return.

open this in the chapter →

02Arrays & Strings in Java3 tables

Array operations in Java
	Time	Extra space	why
new int[n]	O(n)	O(n)	Java fills every slot with the default value before you see it.
a[i] read / write, a.length	O(1)	O(1)	Address arithmetic plus a bounds check; the length is a stored field.
Arrays.fill / equals / toString	O(n)	O(1) / O(1) / O(n)	One pass over the elements; `toString` builds a string of all of them.
Arrays.copyOf / copyOfRange / clone	O(length copied)	O(length copied)	A new array is allocated and filled — never a free view.
Arrays.sort(int[])	O(n log n)	sorts in place	Dual-Pivot Quicksort; the javadoc promises O(n log n) on all data sets.
Arrays.sort(Integer[], comparator)	O(n log n)	up to n/2 references	A stable merge sort (TimSort) on objects; the temp buffer is what the extra space pays for.
Arrays.asList(T[])	O(1)	O(1)	A fixed-size List view over the same array — nothing is copied.

String and StringBuilder operations
	Time	Notes	why
s.charAt(i), s.length()	O(1)	read only	The characters sit in an internal array with a known length.
s + t (one expression)	O(\|s\| + \|t\|)	a new String	Both strings are copied into a fresh one.
s += c, n times in a loop	O(n²)	n new Strings	Step k copies k chars: 1 + 2 + … + n = n(n + 1)/2.
sb.append(c), n times, then toString()	O(n)	O(1) amortised per append	The array grows to 2 × old + 2 when full, so growth copying stays under about 2n.
s.toCharArray(), s.substring(a, b)	O(n), O(b − a)	both copy	Both allocate new storage. `substring` stopped sharing the original's array in Java 7u6.
s.split(regex), s.trim()	O(n)	new strings	One scan, plus a new String for every piece.
s.equals(t), s.compareTo(t)	O(n)	no copy	Char by char until the first difference (or the end).
Integer.parseInt(s), String.valueOf(x)	O(digits)	parse / format	One pass over the digits.

int[] vs Integer[] vs ArrayList<Integer>
	int[]	Integer[]	ArrayList<Integer>	why
New slots start as	0	null	— (starts empty)	Primitives default to 0; references default to null.
Memory per value (typical 64-bit JVM)	4 B	4 B ref + 16 B object	4 B ref + 16 B object + spare capacity	Each boxed value is its own object (values −128..127 are cached and shared).
Can it grow?	no	no	yes — add is O(1) amortised	Arrays are fixed; ArrayList copies into a bigger array when full.
Sort with a Comparator?	no	yes	yes (list.sort)	Comparators work on objects only.
Main danger	overflow	NPE when unboxing null	NPE; remove(int) vs remove(Object)	Boxed types bring null and reference-equality problems.

open this in the chapter →

03OOP for DSA & Design Rounds2 tables

Design choices and what they cost
	Time per call	Memory	why
HashSet as an ArrayList of keys	O(n)	O(n)	contains walks every stored key, and add/remove call it.
HashSet as boolean[10⁶ + 1]	O(1)	O(U), U = 10⁶ + 1	One flag per possible key, used or not: the memory follows the key range, not the data.
HashSet with buckets + chaining	O(1) average, O(n) worst	O(n + B)	A good hash spreads n keys over B buckets, so chains stay short; if every key collides, one chain holds all n.
Linked list: singly + dummy + size	O(index)	O(n)	get, add and delete walk from the dummy to the position.
Linked list: doubly + two sentinels	O(min(index, n − index)); ends O(1)	O(n)	Walk from the nearer end; the sentinels make both ends instant.
Parking system with counters	O(1)	O(1)	Only how many slots are free matters, not which ones.

Object basics and their cost
	Time	Notes	why
`new Node(v)`	O(1)	one heap object; fields start as 0, false or null	Allocation plus the constructor's few assignments.
Read a field / call a method	O(1)	follows one reference	`node.next.val` is two reference hops.
Record `equals` / `hashCode` (k fields)	O(k)	generated from every component	Each component is compared or mixed once.
`HashMap.get` with a good `hashCode`	O(1) average	hash → bucket, then equals on a few entries	Keys are spread over many buckets.
`HashMap.get` when `hashCode` is constant	O(n)	every key in one bucket	equals must run against keys one by one (Java 8+ tree bins help only for Comparable keys).
`EnumType.values()`	O(k)	returns a fresh copy of the constants	Cache it in a static field if you call it in a loop.

open this in the chapter →

04Fast I/O, Judges & Debugging3 tables

Reading and printing n items in Java
	Time	Measured at n = 10⁶	why
Scanner.nextInt() × n	O(n)	530 ms	Regex-based token matching through a 1,024-char buffer: a big constant factor.
BufferedReader + StringTokenizer + parseInt	O(n)	140 ms	Plain character scanning through an 8,192-char buffer.
StreamTokenizer	O(n)	217 ms	Fast, but parses every number as a `double` — exact for ints, not for longs above 2⁵³.
System.out.println() × n	O(n)	2,478 ms	System.out flushes on every println: one write to the OS per line.
PrintWriter, flushed once	O(n)	87 ms	Lines collect in a buffer and leave in a few large writes.
StringBuilder, printed once	O(n)	48 ms	One string, one write.

What usually fits in a 1-second limit (rule of thumb: ~10⁸ simple steps per second)
	Largest n that usually fits	why
O(n!)	n ≤ 10	10! ≈ 3.6 × 10⁶ orders, each needing more work.
O(2ⁿ)	n ≤ 20	2²⁰ ≈ 10⁶ subsets, each needing more work.
O(n³)	n ≤ 500	500³ = 1.25 × 10⁸.
O(n²)	n ≤ 5,000	5,000² = 2.5 × 10⁷; at 10⁵ it would be 10¹⁰ — hopeless.
O(n log n) or O(n)	n ≤ 10⁶	10⁶ × 20 = 2 × 10⁷.
O(log n) or O(1)	any n	log₂ 10¹⁸ ≈ 60 steps.

Verdicts: what the judge is telling you
	Means	Usual cause in Java	why
AC — Accepted	every test passed	—	Output matched on every hidden test, within the limits.
WA — Wrong Answer	ran fine, output differs	logic bug, `int` overflow, wrong format, forgot `flush()`	The program finished normally; the checker compared and disagreed.
TLE — Time Limit Exceeded	didn't finish in time	wrong complexity, infinite loop, Scanner/println on huge I/O	The judge stops the program at the limit, so the output is never checked.
RE — Runtime Error	crashed	index out of bounds, null, bad parse, StackOverflowError	An uncaught exception or a non-zero exit code.
MLE — Memory Limit Exceeded	used too much memory	`new int[n][n]` for big n, boxed collections	Some judges report this as a runtime error instead.
CE — Compile Error	didn't compile	wrong class name for the platform, missing import	Nothing ran; read the first compiler message.

open this in the chapter →

05Java Toolkit & Collections2 tables

The Collections Framework map: what each call costs
	Add	Remove	Lookup / contains	Order	why
ArrayList	O(1) amortized at end, O(n) elsewhere	O(n) (O(1) at end)	get(i) O(1), contains O(n)	insertion	A resizable array: indexing is direct, but inserting/removing in the middle shifts elements.
LinkedList	O(1) at ends	O(1) at ends	get(i) O(n), contains O(n)	insertion	Doubly linked nodes: no shifting, but reaching index i walks the list. Rarely the best choice.
ArrayDeque	O(1) amortized at both ends	O(1) at both ends	contains O(n)	insertion	A circular array with a moving head: the go-to stack and queue.
HashSet / HashMap	O(1) average	O(1) average	O(1) average	none	Hash to a bucket; short chains on average. Big buckets become trees (Java 8+).
LinkedHashSet / LinkedHashMap	O(1) average	O(1) average	O(1) average	insertion (or access)	A HashMap plus a linked list through the entries to remember order.
TreeSet / TreeMap	O(log n)	O(log n)	O(log n), plus floor/ceiling	sorted	A red-black tree: always balanced, always sorted.
PriorityQueue	offer O(log n)	poll O(log n), remove(x) O(n)	peek O(1), contains O(n)	only the head is ordered	A binary heap in an array: the minimum is at index 0; the rest is only partially ordered.

Utilities and their costs
	Time	Notes	why
Arrays.sort(int[])	O(n log n)	dual-pivot quicksort; primitives, so stability doesn't matter	Sorting primitives in place; no boxing.
Arrays.sort(T[]) / Collections.sort / list.sort	O(n log n)	TimSort, stable; ~O(n) on nearly sorted input	Merge-based, so equal elements keep their order. Useful for multi-key sorts.
new PriorityQueue<>(collection)	O(n)	heapify, cheaper than n offers (O(n log n))	Builds the heap bottom-up.
Arrays.fill / copyOf / equals / toString	O(n)	one pass	Touch every element once.
Arrays.binarySearch / Collections.binarySearch	O(log n)	input must already be sorted	Halves the range each step (on a RandomAccess list).
String += in a loop vs StringBuilder	O(n²) vs O(n)	+= copies the whole string each time	Strings are immutable; StringBuilder appends are amortized O(1).

open this in the chapter →

06Mindset & Problem Solving2 tables

Two Sum, three ways — the brute → better → optimal ladder
	Time	Extra space	why
Check every pair	O(n²)	O(1)	n(n−1)/2 pairs: for n = 10⁴ that's ~5·10⁷ checks — passes, but at 10⁵ it would be ~5·10⁹.
Sort indices + two pointers	O(n log n)	O(n)	Sorting dominates; the extra index array keeps the original positions.
One-pass HashMap	O(n) average	O(n)	One O(1) average lookup and insert per element; the map may hold all n values.

A 45-minute coding interview, budgeted
	Minutes	You produce	why
U — Understand	0–5	Restated problem, 2 examples, clarified inputs	Most wrong answers come from solving a slightly different problem.
M + P — Match & Plan	5–12	Brute force + its Big-O, then a better idea the interviewer agrees with	Agreeing on the plan before coding means no wasted typing.
I — Implement	12–30	Clean code with good names, narrated	With a plan, coding is translation — it should be the calm part.
R — Review	30–38	A dry run on an example + 2–3 edge cases	Finding your own bug scores better than the interviewer finding it.
E — Evaluate	38–45	Final time/space, trade-offs, follow-ups, your questions	Shows you understand why the solution works and what it costs.

open this in the chapter →

07Big-O & Complexity2 tables

Common growth rates, in numbers
	n = 10³	n = 10⁶	Typical source	why
O(1)	1	1	array index, HashMap get (average)	Work doesn't depend on n at all.
O(log n)	~10	~20	binary search, balanced tree, heap push/pop	Each step halves what's left: log₂ 10⁶ ≈ 20.
O(n)	10³	10⁶	one pass, two pointers, sliding window	Constant work per element.
O(n log n)	~10⁴	~2·10⁷	sorting, n heap operations	n elements × log n work each.
O(n²)	10⁶	10¹²	all pairs, nested loops	n choices × n choices; at 10⁶ that's hours, not seconds.
O(2ⁿ)	~10³⁰¹	—	all subsets, naive recursion	Each element doubles the work: in or out.
O(n!)	~10²⁵⁶⁷	—	all permutations	n choices, then n−1, then n−2…

Input size → the complexity you can afford (~10⁸ simple steps per second)
	Max n	Allowed	Typical idea	why
Tiny	≤ 10	O(n!)	try every permutation	10! ≈ 3.6·10⁶ — fine.
Small	≤ 20	O(2ⁿ)	subsets, bitmask DP	2²⁰ ≈ 10⁶ — fine; 2⁴⁰ is not.
Medium-small	≤ 500	O(n³)	triple loops, Floyd–Warshall, interval DP	500³ = 1.25·10⁸ — borderline but usually OK.
Medium	≤ ~5,000 (10⁴ borderline)	O(n²)	all pairs, 2D DP	(10⁴)² = 10⁸ ≈ a second: borderline. ~5,000 (2.5·10⁷) is comfortable.
Large	≤ 10⁶	O(n log n)	sorting, heaps, binary search per element	10⁶ × 20 = 2·10⁷.
Huge	≤ 10⁸	O(n)	single pass, math	10⁸ steps — only constant work per element fits.
Astronomical	> 10⁸	O(log n) or O(1)	binary search on the answer, formulas	You can't even read every value.

open this in the chapter →

08Recursion2 tables

Classic recursions and their cost
	Time	Stack space	why
factorial(n)	O(n)	O(n)	One call per value n, n−1, …, 1; all of them wait on the stack at the deepest point.
Naive fib(n)	O(2ⁿ)	O(n)	Two calls per call → the tree roughly doubles per level (tightly ≈ 1.618ⁿ). Depth is only n, so space stays linear.
Memoized fib(n)	O(n)	O(n)	Each n from 0..n is computed once (2n − 1 calls); the memo array and stack are both size n.
Iterative fib(n)	O(n)	O(1)	Same n additions, but just two variables and no call stack.
Fast power pow(x, n)	O(log n)	O(log n)	n halves every call, so there are about log₂ n calls — each waiting on the stack.
Reverse a linked list recursively	O(n)	O(n)	One call per node, and every call stays on the stack until the end is reached.
Generate all strings of length m from 2 choices	O(2ᵐ · m)	O(m)	2ᵐ leaves, each copied in O(m); the stack holds one frame per character.

Read the cost straight from the recurrence
	Calls / total work	Example	why
f(n) calls f(n − 1) once, O(1) work	O(n)	factorial, reverse list	A single chain of n calls.
f(n) calls f(n / 2) once, O(1) work	O(log n)	fast power, binary search	You can halve n only log₂ n times before reaching 1.
f(n) calls f(n − 1) twice	O(2ⁿ)	Tower of Hanoi; naive fib (≤ this)	Each level doubles the number of calls: 1, 2, 4, … 2ⁿ. Naive fib calls f(n − 1) + f(n − 2), so it is bounded by this (tightly ≈ 1.618ⁿ).
f(n) calls f(n / 2) twice + O(n) work	O(n log n)	merge sort	log n levels, and every level does O(n) work in total.
Any recursion with memoization	O(states × work per state)	memo fib: n states × O(1)	Each distinct input is solved once; repeats cost O(1).

open this in the chapter →

09Math & Number Theory2 tables

The number-theory toolkit
	Time	Extra space	why
gcd by repeated subtraction	O(max(a, b))	O(1)	gcd(10¹⁸, 1) needs 10¹⁸ − 1 subtractions.
gcd by Euclid (with %)	O(log min(a, b))	O(1)	Every two steps the larger number drops below half. Lamé: at most 5 × (digits of the smaller).
Is n prime? (trial division)	O(√n)	O(1)	Divisors come in pairs d × (n / d), and one of each pair is ≤ √n.
All primes ≤ n (sieve)	O(n log log n)	O(n)	Each prime p crosses about n / p cells; Σ n / p over primes is n log log n. n = 10⁶: 2,122,048 crossings.
aᵉ mod m, one multiply at a time	O(e)	O(1)	e = 10¹⁸ would take about 31.7 years at 10⁹ multiplications per second.
aᵉ mod m, fast power	O(log e)	O(1)	One loop step per bit of e: 60 steps for e = 10¹⁸.
Inverse mod a prime p (Fermat)	O(log p)	O(1)	It is one fast power: a^(p−2) mod p.
Pascal's table up to row n	O(n²)	O(n²)	n(n + 1)/2 cells. Row 10⁵ would need 5·10⁹ cells, about 40 GB of longs.
nCr mod p with factorial tables	O(n + log p) once, O(1) per query	O(n)	n multiplications for fact[], one Fermat inverse, n more for invFact[]; each nCr is 2 multiplications.
Peel the digits of x	O(log₁₀ x)	O(1)	An int has at most 10 digits, a long at most 19.

Random Pick with Weight (n weights, total S)
	Build	Per pick	Space	why
Ticket array (index i written w[i] times)	O(S)	O(1)	O(S)	S can reach 10⁴ × 10⁵ = 10⁹ ints, about 4 GB.
Prefix sums + linear scan	O(n)	O(n)	O(n)	Walk prefix[] until it reaches the ticket.
Prefix sums + binary search	O(n)	O(log n)	O(n)	prefix[] is strictly increasing (every w[i] ≥ 1): 14 probes for n = 10⁴.

open this in the chapter →

10Arrays & Strings3 tables

Array (`int[]`) and ArrayList operations
	int[]	ArrayList	why
Read / write by index	O(1)	O(1)	The address is base + i × size: arithmetic, not a search.
Append at the end	— (fixed size)	O(1) amortized	Usually a free slot exists; the rare O(n) copy is spread over many appends.
Insert / delete at index i	O(n)	O(n)	Everything after i shifts (n − i moves to insert, n − i − 1 to delete).
Insert / delete at the front	O(n)	O(n)	Every element shifts. Need fast front operations? Use `ArrayDeque`.
Search by value (unsorted)	O(n)	O(n)	Nothing tells you where a value is — you must look at each slot.
Search by value (sorted)	O(log n)	O(log n)	Binary search halves the range each step.
Grow capacity	— (copy to a new array)	O(n) when it happens	Copy everything into a bigger array (ArrayList grows by ~1.5×).

String and StringBuilder operations
	String	StringBuilder	why
charAt(i) / length()	O(1)	O(1)	Both store characters in an internal array and keep the length.
Append one char	O(n) — new copy	O(1) amortized	Strings are immutable, so `+` copies everything. A builder writes into spare capacity.
Build a string of n chars in a loop	O(n²)	O(n)	1 + 2 + … + n characters copied vs one write per char.
substring(a, b)	O(b − a)	O(b − a)	Since Java 7u6 substring copies the characters into a new String.
equals / compareTo	O(n)	compareTo O(n) (Java 11+); equals = identity	Compares character by character (String.equals checks the length first). StringBuilder does not override equals — compare `sb.toString()` instead.
reverse / insert in the middle	O(n) via a copy	O(n)	Every character after the change point has to move.

One-pass array techniques in this chapter
	Time	Extra space	why
Kadane (max subarray, circular max)	O(n)	O(1)	One decision per element — extend or restart — kept in two or four variables.
Prefix × suffix (product except self)	O(n)	O(1) besides the output	Two passes; the left products live in the answer array, the right ones in a single variable.
Boyer–Moore majority vote	O(n)	O(1)	One pass with a candidate and a counter. Counting in a HashMap is also O(n) but needs O(n) memory.
Next permutation	O(n)	O(1)	At most three right-to-left passes over the suffix: find the pivot, find its successor, reverse.
Cyclic placement (first missing positive)	O(n)	O(1)	Every swap settles one value in its home slot for good, so there are at most n swaps in the whole run.
Three reversals (rotate by k)	O(n)	O(1)	Each element is swapped about twice.

open this in the chapter →

11Matrices & Simulation2 tables

Grid operations (m rows × n columns)
	Time	Extra space	why
Read or write `grid[r][c]`	O(1)	O(1)	Two index steps: find row r's array, then slot c in it.
Flat index `r * cols + c` and back	O(1)	O(1)	One multiply and one add; back is one divide and one remainder.
Visit every cell (rows, spiral, diagonals, zigzag)	O(m·n)	O(1)	Each cell is visited once. Only the order changes.
Check all 8 neighbours of every cell	O(m·n)	O(1)	8 constant-time checks per cell: 8·m·n steps.
Transpose m × n into a new n × m	O(m·n)	O(m·n)	The shape changes, so a new matrix is unavoidable.
Transpose a square matrix in place	O(n²)	O(1)	n(n − 1)/2 swaps above the diagonal, one temp variable.
Deep-copy a grid	O(m·n)	O(m·n)	Every row is cloned.

The same answers, less memory
	Time	Extra space	why
Set Zeroes: copy, then wipe rows and columns	O(m·n·(m + n))	O(m·n)	Each original 0 wipes m + n cells; the copy is a full second matrix.
Set Zeroes: row and column flags	O(m·n)	O(m + n)	Two passes; one boolean per row and per column.
Set Zeroes: row 0 and column 0 as markers	O(m·n)	O(1)	Same two passes; the marks live inside the matrix, plus two booleans.
Game of Life: copy the board	O(m·n)	O(m·n)	8 checks per cell, reading from a frozen copy.
Game of Life: two bits per cell	O(m·n)	O(1)	The same checks; the next state hides in bit 1 until a final shift.
Rotate: copy vs transpose + reverse	O(n²)	O(n²) vs O(1)	Both move every cell a constant number of times; only the copy needs a second matrix.
Spiral: visited grid vs four walls	O(m·n)	O(m·n) vs O(1)	Both visit each cell once; the walls replace the visited grid.
Zigzag: draw a grid / row builders / cycle jumps	O(rows·n) / O(n) / O(n)	O(rows·n) / O(n) / O(1)	The grid has rows × n cells to scan; builders hold n chars; jumps compute every position (besides the output).

open this in the chapter →

12Two Pointers1 table

Two pointers vs the alternatives
	Time	Extra space	why
Brute force: check every pair	O(n²)	O(1)	n·(n−1)/2 pairs — for n = 10⁵ that is ~5·10⁹ checks, far too slow.
Sort + binary search per element	O(n log n)	O(1)–O(n)	n searches, each log n. Good, but needs the array sorted.
Hash set / map	O(n)	O(n)	One pass, but every element is stored — memory grows with input.
Two pointers (already sorted)	O(n)	O(1)	Each step moves a pointer inward; together they move at most n times.
Sort, then two pointers	O(n log n)	O(1)–O(log n)	Sorting dominates. `Arrays.sort(int[])` uses dual-pivot quicksort with O(log n) stack.
Merge two sorted arrays (one pointer each)	O(n + m)	O(1) in place	Every comparison fills one slot for good. Copy-then-sort would cost O((n + m) log(n + m)).

open this in the chapter →

13Sliding Window2 tables

Sliding window vs the alternatives
	Time	Extra space	why
Brute force: every subarray, recompute from scratch	O(n²)–O(n³)	O(1)	n²/2 subarrays, and summing or checking each one costs up to O(n) more.
Fixed window of size k	O(n)	O(1)	Build the first window in k steps, then n − k slides of O(1) each.
Variable window (grow + shrink)	O(n)	O(1)	`right` moves n times and `left` moves at most n times in total — at most 2n steps. Amortized O(1) per step.
Window + count array `int[26]` / `int[128]`	O(n)	O(σ) = O(1)	σ is the alphabet size. The array has a fixed size no matter how long the input is.
Window + HashMap counts	O(n) average	O(distinct)	HashMap updates are O(1) on average; the map holds one entry per distinct key in the window.
Window max/min with a monotonic deque	O(n)	O(k)	Each index is pushed once and popped at most once; the deque never holds more than k indices.

Cost of one window operation
	Time	why
Add `nums[right]` to a running sum / count	O(1)	One addition or one array increment.
Remove `nums[left]`	O(1)	One subtraction or decrement — no shifting, the array is never modified.
"Is this window an anagram?" via `Arrays.equals(need, have)`	O(26) = O(1)	Compares two fixed-size arrays. Fine, but a `matches` counter makes it truly one step.
Window maximum by rescanning	O(k)	Looks at every element in the window again — this is what makes the brute force O(n·k).
Window maximum from a monotonic deque	O(1)	The answer is always `nums[deque.peekFirst()]`.

open this in the chapter →

14Hashing & Prefix Sums2 tables

Hash-based collections (Java 8+)
	Average	Worst case	why
HashMap put / get / containsKey / remove	O(1)	O(log n)	Average: one hash plus a short chain. Worst: everything collides into one bucket, which Java turns into a red-black tree (O(n) before Java 8, or if keys aren't Comparable).
HashMap put that triggers a resize	O(1) amortized	O(n) for that one call	Doubling re-hashes all n entries, but it happens only after n/2 cheap puts, so the cost spreads to O(1) each.
HashSet add / contains / remove	O(1)	O(log n)	A HashSet is a HashMap with a dummy value, so it inherits the same costs.
Iterate a HashMap / HashSet	O(n + capacity)	O(n + capacity)	The iterator visits every bucket, empty or not. This rarely matters, but it explains why huge, mostly empty maps iterate slowly.
LinkedHashMap put / get	O(1)	O(log n)	It's a HashMap plus a doubly linked list through the entries, and updating that list is O(1).
TreeMap / TreeSet put / get / floorKey / ceilingKey	O(log n)	O(log n)	A red-black tree stays balanced, so its height is always O(log n).
int[] counting array (keys in 0..m−1)	O(1)	O(1)	The key is the index, so there's no hashing and no collisions. It costs O(m) memory.

Prefix sums
	Time	Extra space	why
Build 1D prefix array	O(n)	O(n)	One addition per element, stored in an array of n + 1 slots.
Range sum query (after building)	O(1)	O(1)	It's one subtraction: prefix[r+1] − prefix[l].
Range sum without prefix sums	O(n) per query	O(1)	You re-add the range every time, so q queries cost O(n·q).
Change one nums[i], then query	O(n) per update	O(n)	Every prefix after i changes. For many updates use a Fenwick or segment tree (Range Queries chapter): O(log n) each.
Build 2D prefix (r × c)	O(r·c)	O(r·c)	Each cell is filled once from three neighbours already computed.
2D rectangle query	O(1)	O(1)	Four lookups: whole − above − left + corner.
Count subarrays with sum k (prefix + HashMap)	O(n)	O(n)	One pass. Each step does one O(1) map lookup and one O(1) update.

open this in the chapter →

15Linked Lists2 tables

Linked list vs array list
	Singly linked	Doubly linked	ArrayList	why
Get the k-th element	O(n)	O(n)	O(1)	A list has no addresses to compute — you hop k times. An array computes `base + k × size` directly.
Insert / delete at head	O(1)	O(1)	O(n)	The list rewires one or two references. The array must shift every element one slot.
Insert at tail	O(1)*	O(1)	O(1) amortized	*Only if you keep a `tail` reference. ArrayList appends in O(1) except an occasional O(n) resize.
Delete at tail	O(n)	O(1)	O(1)	Singly linked must walk to the second-to-last node to set its `next = null`. Doubly linked has `tail.prev`.
Insert / delete next to a node you hold	O(1)	O(1)	O(n)	Just rewire. Singly linked can only cheaply delete the node after the one you hold; doubly linked can delete the node itself.
Search by value	O(n)	O(n)	O(n)	No order to exploit — check elements one by one (binary search doesn't work on lists: no O(1) middle).
Extra memory per element	1 reference + object header	2 references + object header	1 slot (amortized)	Every node is a separate object. Arrays store values side by side, which is also far friendlier to the CPU cache.

The core techniques
	Time	Extra space	why
Reverse (iterative)	O(n)	O(1)	Each node's arrow is flipped once with three references.
Reverse (recursive)	O(n)	O(n)	Same work, but n stack frames — can overflow on long lists.
Reverse a section / k at a time	O(n)	O(1)	Each node is flipped once; finding each block's k-th node adds one more walk over it.
Find middle (slow / fast)	O(n)	O(1)	fast walks the list once; slow walks half.
Cycle detection (Floyd)	O(n)	O(1)	slow enters the cycle within n steps; fast then closes the gap one node per step.
Cycle detection (HashSet)	O(n)	O(n)	Stores every visited node.
Merge two sorted lists	O(n + m)	O(1)	Each step re-links one node; nothing is copied.
Palindrome check (middle + reverse + compare)	O(n)	O(1)	A few linear passes; the second half is reversed in place and restored.
Rotate by k	O(n)	O(1)	One pass counts the nodes and finds the tail; `k % n` drops whole laps, so at most one more pass reaches the cut.

open this in the chapter →

16Stacks & Monotonic Stack2 tables

Stack operations
	ArrayDeque	Raw array + size	Linked nodes	why
push(x)	O(1) amortized	O(1) amortized	O(1)	Write at the top. When an array is full it is copied into a bigger one — rare enough that the average stays O(1).
pop()	O(1)	O(1)	O(1)	Remove the top: move an index (array) or one reference (linked). Nothing shifts.
peek()	O(1)	O(1)	O(1)	Read the top without changing anything.
isEmpty() / size()	O(1)	O(1)	O(1)	Both keep a counter (or head/tail indices).
contains(x) / search	O(n)	O(n)	O(n)	Nothing is indexed by value — you'd have to walk the whole stack.
Memory for n items	O(n)	O(n)	O(n)	Same Big-O, but linked nodes pay an object header + a reference per item; arrays are compact and cache-friendly.

Monotonic stack vs brute force
	Brute force	Monotonic stack	Stack space	why
Next greater element (each index)	O(n²)	O(n)	O(n)	Brute force scans right from every index. The stack pushes each index once and pops it at most once.
Daily temperatures	O(n²)	O(n)	O(n)	Same pattern: a day leaves the stack the moment its warmer day arrives.
Largest rectangle in histogram	O(n²)	O(n)	O(n)	Brute force tries every range. The stack finds each bar's nearest shorter neighbours in one pass.
Worst case for stack size	—	—	n	A strictly decreasing input (for next greater) never pops, so all n indices wait on the stack.

open this in the chapter →

17Queues & Deques3 tables

Queue operations by implementation
	Circular array (raw)	Linked queue (raw)	ArrayDeque	ArrayList + remove(0)	why
enqueue (offer)	O(1)	O(1)	O(1) amortized	O(1) amortized	Write at `tail` / link after `tail`. ArrayDeque and ArrayList occasionally grow their array, which averages out to O(1).
dequeue (poll)	O(1)	O(1)	O(1)	O(n)	Moving `head` is one step. `ArrayList.remove(0)` shifts every remaining element left.
peek front	O(1)	O(1)	O(1)	O(1)	The front is at a known index or node.
contains / search	O(n)	O(n)	O(n)	O(n)	A queue keeps arrival order, not sorted order — you must scan.
Memory	O(capacity)	O(n) + a node per item	O(n)	O(n)	Linked nodes pay for an object header and a `next` reference per element; arrays are compact.

Building one structure from the other
	push / enqueue	pop / dequeue	Extra space	why
Queue from two stacks (lazy transfer)	O(1)	O(1) amortized, O(n) worst	O(n)	Each element is moved from `in` to `out` at most once in its life, so n operations cost O(n) in total.
Queue from two stacks (transfer on every push)	O(n)	O(1)	O(n)	Every push empties and refills the main stack.
Stack from one queue (rotate on push)	O(n)	O(1)	O(n)	After offering x, the other n−1 elements are rotated behind it.
Stack from two queues (move on pop)	O(1)	O(n)	O(n)	Pop moves all but the newest element to the helper queue.

Sliding window maximum (n elements, window k)
	Time	Extra space	why
Rescan every window	O(n·k)	O(1)	n − k + 1 windows, k elements each.
Max-heap with lazy deletion	O(n log n)	O(n)	n heap inserts; stale tops are removed later, so the heap can hold up to n entries.
Monotonic deque	O(n)	O(k)	Each index is pushed once and popped at most once; the deque never holds more than k indices.

open this in the chapter →

18Binary Search2 tables

Searching sorted data
	Time	Extra space	why
Linear scan	O(n)	O(1)	Might have to look at every element; ignores the sorted order completely.
Binary search (iterative)	O(log n)	O(1)	Each look halves the space: n → n/2 → … → 1 takes ⌊log₂ n⌋ + 1 looks at most.
Binary search (recursive)	O(log n)	O(log n)	Same looks, but each one adds a stack frame — log n frames deep.
Lower / upper bound	O(log n)	O(1)	Same halving; it just doesn't stop early on a match.
First + last occurrence (two bounds)	O(log n)	O(1)	Two binary searches = 2·log n, still O(log n) — even if the value fills the whole array.
`Arrays.binarySearch(int[], key)`	O(log n)	O(1)	The JDK's iterative binary search on a primitive array.
`Collections.binarySearch` on `ArrayList`	O(log n)	O(1)	`ArrayList` is `RandomAccess`, so `get(mid)` is O(1).
`Collections.binarySearch` on `LinkedList`	O(n)	O(1)	Only O(log n) comparisons, but walking the links to each mid costs O(n) traversal in total.
Sort once, then q searches	O(n log n + q log n)	O(log n)	Sorting dominates once; worth it as soon as you search more than a handful of times.

Binary search on the answer
	Time	Extra space	why
General: range R, check costs C	O(C · log R)	O(1)	log R guesses, each verified by one call to the check.
Koko Eating Bananas (LC 875)	O(n log M)	O(1)	M = largest pile. Each guess sums ⌈pile / speed⌉ over n piles.
Ship Packages (LC 1011)	O(n log S)	O(1)	S = total weight. Each guess simulates loading the ship in one pass.
Median of Two Sorted Arrays (LC 4)	O(log min(m, n))	O(1)	We binary search how many elements the shorter array puts in the left half.
Try every candidate instead	O(C · R)	O(1)	R can be 10⁹ — this is the brute force that binary search on the answer replaces.

open this in the chapter →

19Sorting2 tables

Every sort at a glance
	Best	Average	Worst	Extra space	Stable	In-place	why
Bubble sort (early exit)	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Best: one pass with no swaps on sorted input. Otherwise each pass fixes one value: (n−1)+(n−2)+… = n(n−1)/2 comparisons.
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	No	Yes	It always scans the whole unsorted part to find the minimum — even if the array is sorted. Its long swaps can jump an element over its equal twin.
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Work = number of inversions. Sorted input has none (n−1 comparisons); reversed input has n(n−1)/2.
Merge sort (top-down)	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No	log₂ n levels of halving; each level merges n values. The helper array costs n extra slots (plus O(log n) recursion).
Quicksort (random pivot)	O(n log n)	O(n log n)	O(n²)	O(log n) expected	No	Yes	Balanced pivots halve the range → log n levels of O(n) partitioning. Always picking the min/max gives n levels → O(n²) (and O(n) stack).
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes	Build a heap in O(n), then n extractions each sift down log n levels. Guaranteed, but cache-unfriendly so slower than quicksort in practice.
Counting sort (values 0..k)	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Yes	No	One pass to count, one over the k buckets, one to place. No comparisons, so the n log n bound doesn't apply — but k must be small.
Radix sort (LSD, d digits, base b)	O(d·(n + b))	O(d·(n + b))	O(d·(n + b))	O(n + b)	Yes	No	d stable counting passes, one per digit. For 32-bit ints in base 10, d ≤ 10 — effectively linear.
TimSort (Java objects, `List.sort`)	O(n)	O(n log n)	O(n log n)	O(n)	Yes	No	Finds already-sorted runs (insertion sort for short ones) and merges them. Sorted input is one run → O(n). Merge buffer up to n/2.
Dual-pivot quicksort (Java `int[]`)	O(n)	O(n log n)	O(n log n)	O(log n) stack; O(n) when it merges runs	No	Mostly	Two pivots split into three parts. Large, nearly sorted arrays are detected as runs and merged (sorted input → O(n)) with a temporary array. Since JDK 14 it also switches to heap sort when partitioning goes too deep, so the worst case is O(n log n).

Selection problems (don't sort everything)
	Time	Extra space	why
Sort, then index	O(n log n)	O(1)–O(n)	Simple and safe, but orders n values when you only need one position.
Min-heap of size k	O(n log k)	O(k)	Each of n values costs at most one log k push/pop. Great for streams.
Quickselect (random pivot)	O(n) avg, O(n²) worst	O(1)	Partition like quicksort but keep only one side: n + n/2 + n/4 + … ≈ 2n when pivots land near the middle. Random pivots give O(n) expected (under 3.4n comparisons).

open this in the chapter →

20String Parsing & Expression Evaluation2 tables

The problems in this chapter (n = input length)
	Brute force	Optimal time	Optimal extra space	why
String to Integer (atoi)	O(n), copies the digits	O(n)	O(1)	Each character is read once. The guard replaces a long or BigInteger, so nothing is copied.
Roman to Integer	O(n), six rewrites	O(n), n ≤ 15	O(1)	Peek one symbol ahead and add or subtract; the brute force builds six new strings first.
Integer to Roman	O(1), additive + six rewrites	O(1)	O(1)	At most 13 table rows and 15 symbols for any value 1..3999.
Reverse Words in a String	O(n²), prepending	O(n)	O(1) beyond the char[]	Prepending copies the whole answer per word; reversing touches each character about twice.
Basic Calculator II	O(n²), collapsing a list	O(n)	O(1)	ArrayList removals shift the tail; result + last never looks back.
Basic Calculator	O(n²), rewriting brackets	O(n)	O(depth)	Each rewrite rebuilds the string; the sign stack holds one pair per open bracket.
Text Justification (L lines, width W)	O(L·W²), inserting spaces	O(L·W)	O(W) per line	StringBuilder.insert shifts the line every time; computing each gap's width writes each character once.
Encode and Decode Strings (N total chars)	O(N), escaping	O(N)	O(N), the output	Both are linear, but escaping inspects every character; length prefixes jump over the payload.

Two ways to evaluate infix with precedence
	Two stacks (shunting-yard)	Recursive descent	why
Time	O(n)	O(n)	Each token is pushed and popped at most once, or read once by exactly one method.
Extra space	O(n) on the heap	O(depth) on the call stack	Very deep nesting is safe in a Deque; recursion can throw StackOverflowError.
Unary minus	push 0 when no value comes before '-'	factor := '-' factor	Both turn -x into 0 − x (or −x) without special cases elsewhere.
A new precedence level (e.g. ^)	one more case in prec()	one more method in the chain	Both are small changes; the recursive version reads like the grammar.

open this in the chapter →

21Tree Traversals2 tables

Traversals (n nodes, height h, widest level w)
	Time	Extra space	why
DFS (pre/in/post), recursive	O(n)	O(h)	Each node is entered once; the call stack only holds the current root-to-node path.
DFS with an explicit ArrayDeque stack	O(n)	O(h)	Each node is pushed and popped once; same path on the stack — but on the heap, so deep trees don't overflow.
Morris inorder (threads)	O(n)	O(1)	Temporarily points empty right links back to ancestors, then removes them; each edge is walked a constant number of times.
BFS level order with a queue	O(n)	O(w)	Each node is offered and polled once; the queue holds about one level (up to ~n/2 in a perfect tree).
Serialize / deserialize (preorder + markers)	O(n)	O(n)	n values and n + 1 null markers are written once and read once; the string itself is O(n).
Parent map + BFS from a node	O(n)	O(n)	One DFS fills the map; the BFS offers each node at most once thanks to the seen set.

Stack vs queue memory at the extremes (n ≈ 10⁶)
	DFS stack (h)	BFS queue (w)	why
Perfect tree, n = 2²⁰ − 1 = 1,048,575	20 frames	524,288 nodes	20 levels deep, but the last level alone holds 2¹⁹ nodes — half the tree waits in the queue at once.
Skewed chain, n = 10⁶	10⁶ frames → StackOverflowError	1 node	The tree is a linked list in disguise: recursion depth equals n, while each level has one node.

open this in the chapter →

22Tree Recursion2 tables

Tree recursions (n nodes, height h)
	Time	Extra space	why
Height, size, sum, balanced — one postorder pass	O(n)	O(h)	Each node is visited once with O(1) work; the stack holds one root-to-node path.
Diameter / max path sum with a global best	O(n)	O(h)	Still one pass: the bend is recorded at the node, only one arm travels up.
Same pattern, but height() recomputed at every node	O(n²) worst	O(h)	Each node's height is recomputed once per ancestor: n + (n − 1) + … on a skewed tree (O(n log n) when balanced).
Same tree / mirror (two trees in lockstep)	O(min(n, m))	O(min(h₁, h₂))	Stops at the first difference; never goes deeper than the shorter tree.
Subtree: Same Tree started at every node (subRoot has m nodes)	O(n·m) worst	O(h₁ + h₂)	Up to m comparisons at each of n starting points — long chains of equal values are the bad case.
Subtree: one id per subtree shape (HashMap)	O(n + m) expected	O(n + m)	Each node builds one short key and does one O(1)-average lookup; the map stores each distinct shape once.
Path state passed down (Path Sum, Good Nodes, Sum Root to Leaf)	O(n)	O(h)	One visit per node; the state is one int per stack frame.
Path Sum II: one shared path, k matching paths copied	O(n + k·h)	O(h) + output	O(1) add/remove per node; only the k saved paths are copied, O(h) each.
Path Sum III: start a walk at every node	O(n·h)	O(h)	Each node is walked once from every ancestor: n log n balanced, n²/2 for a chain.
Path Sum III: prefix sums + HashMap with undo	O(n) average	O(n)	One O(1)-average lookup and update per node; the map keeps at most one key per node.
Count nodes of a complete tree (perfect-subtree shortcut)	O(log² n)	O(log n)	About log n levels do real work, each with an O(log n) walk down the outer edges.
Flatten to a list in place (splice under the left subtree)	O(n)	O(1)	Each node is searched as a rightmost node at most once; no recursion, no list.
Lowest common ancestor, one recursive pass	O(n)	O(h)	Each node reports at most once.
Build from preorder (or postorder) + inorder with a HashMap	O(n)	O(n)	Each node is created once with an O(1) index lookup; the map holds n entries.
Same build with a linear search for each root	O(n²) worst	O(h)	Each of n roots may scan the whole inorder range on a skewed tree.

Why recomputing hurts — n = 10⁴ nodes
	Balanced (h ≈ 13)	Skewed chain (h = n − 1)	why
Height returned up in one pass	10⁴ visits	10⁴ visits	Shape doesn't matter: every node is visited exactly once.
Height recomputed at every node	≈ n·log₂ n ≈ 1.3·10⁵	n(n + 1)/2 ≈ 5·10⁷	Each node is re-walked once per ancestor: about 13 ancestors when balanced, up to n when skewed.
Recursion depth	≈ 14 frames	10⁴ frames — risky on a small stack	Depth = height + 1; a chain makes recursion as deep as the tree is big.

open this in the chapter →

23Binary Search Trees2 tables

BST operations (n values, height h)
	Balanced (TreeMap / AVL)	Plain BST, worst case	why
Search / contains	O(log n)	O(n)	One comparison per level; a degenerate tree has n levels.
Insert	O(log n)	O(n)	Walk down to the empty spot. A red-black tree then needs at most 2 rotations (plus recolouring) to rebalance.
Delete	O(log n)	O(n)	Find the node, maybe walk to the successor — still one path down.
Min / max	O(log n)	O(n)	Keep going left (or right) to the end of the spine.
Successor / floor / ceiling	O(log n)	O(n)	A search that remembers the best candidate seen on the way down.
Inorder traversal (all values sorted)	O(n)	O(n)	Visits each node once; stack depth O(h).
Kth smallest (no extra data)	O(log n + k)	O(n)	Walk the left spine (h steps), then k pops of an inorder.
Build from a sorted array	O(n)	—	Each value becomes a node once; picking the middle keeps it balanced.

Choosing an ordered structure
	Lookup	Insert / delete	Ordered queries (floor, range, min)	why
Sorted array + binary search	O(log n)	O(n)	O(log n)	Fast to search, but inserting shifts everything to the right.
HashMap / HashSet	O(1) average	O(1) average	O(n) — no order	Hashing scatters keys, so "next larger key" means scanning everything.
TreeMap / TreeSet (red-black)	O(log n)	O(log n)	O(log n)	Height is guaranteed ≤ 2·log₂(n + 1).
Hand-written unbalanced BST	O(h)	O(h)	O(h)	Great to learn from; h can degrade to n with sorted input.

open this in the chapter →

24Heaps & Priority Queues3 tables

Binary heap / PriorityQueue (n elements)
	Time	Why it's that fast (or slow)	why
peek (min)	O(1)	Read index 0	The heap property puts the minimum at the root.
offer / add	O(log n)	Sift up ≤ height	The new value climbs at most ⌊log₂ n⌋ levels (amortized: the array occasionally grows).
poll / remove()	O(log n)	Sift down ≤ height	The moved leaf sinks at most ⌊log₂ n⌋ levels.
Build from n values (heapify / `new PriorityQueue<>(collection)`)	O(n)	Σ heights ≤ n	n/2 leaves do no work, n/4 nodes sink ≤ 1 level, n/8 sink ≤ 2… the series sums to less than n.
n separate offers	O(n log n)	Each is O(log n)	Building one-by-one is slower than heapify (still fine in practice).
remove(Object) / contains	O(n)	Linear scan	Siblings aren't ordered, so finding an arbitrary value means checking everything.
Heap sort	O(n log n)	In place, O(1) extra	Heapify O(n) + n polls of O(log n). Worst case too — but not stable.
Iterate / toString	O(n)	Array order, NOT sorted	Only polling repeatedly gives sorted order.

Finding the k largest of n
	Time	Extra space	why
Sort everything	O(n log n)	O(log n) – O(n)	Simple, but does far more work than needed when k is small.
Size-k min-heap	O(n log k)	O(k)	Each element costs O(log k); works on streams that never end.
Heapify all, then poll k times	O(n + k log n)	O(n)	Linear build, then k cheap pops.
Quickselect (random pivot)	O(n) average, O(n²) worst	O(1) in place	Partition and keep only the side with the answer: n + n/2 + n/4 + … ≈ 2n.
Counting / buckets (bounded values)	O(n + range)	O(range)	No comparisons at all when values or frequencies are small integers.

Heap patterns at a glance
	Time	Extra space	why
Two heaps: addNum / findMedian	O(log n) / O(1)	O(n)	At most five heap operations per add; the median is read from the two tops.
K-way merge of N items from k sorted lists	O(N log k)	O(k)	Every item enters and leaves a heap that holds one cursor per list.
K smallest pair sums (Find K Pairs)	O(k log min(n₁, k))	O(min(n₁, k))	k polls on a heap of row cursors — the n₁·n₂ sum table is never built.
Sort + heap greedy (IPO)	O(n log n + k log n)	O(n)	One sort to unlock in order; each project enters and leaves the heap at most once.

open this in the chapter →

25Tries2 tables

Trie operations (L = length of the word/prefix, S = total letters stored, Σ = alphabet size)
	Time	Extra space	why
insert(word)	O(L)	O(L) worst	One step per letter; at most L new nodes when no prefix is shared.
search(word)	O(L)	O(1)	Walk at most L edges, then check one flag. The number of stored words never appears.
startsWith(prefix)	O(L)	O(1)	The same walk as search, without the final flag check.
search with k wildcards	O(Σᵏ · L) worst	O(L)	Each '.' may fan out to Σ = 26 children; letters never branch. Never more than the nodes in the trie.
countWordsStartingWith(prefix)	O(L)	O(1)	With a `pass` counter on every node, the answer is stored at the prefix node.
erase(word) (counting trie)	O(L)	O(1)	Walk once, decrement counters, cut the branch where a counter hits 0.
autocomplete(prefix)	O(L + K)	O(depth)	L to reach the prefix node, then K = nodes in its subtree (plus output); recursion depth = longest word.
Build from N words	O(S)	O(S·Σ) array / O(S) map	At most S + 1 nodes. Each array node always holds Σ = 26 references, even if empty.

Trie vs the alternatives for N words
	contains(word)	any word starts with p?	Memory	why
HashSet<String>	O(L) average	O(N·L)	O(S)	Hashing a word costs O(L), but a prefix has no hash bucket — you must scan every word.
TreeSet<String> / sorted array	O(L log N)	O(L log N)	O(S)	`ceiling(p)` finds the first word ≥ p in log N comparisons, each up to L chars.
Trie with Node[26]	O(L)	O(L)	O(S·26)	Fastest walk: array index per letter. Pays 26 slots per node, used or not.
Trie with HashMap children	O(L) average	O(L) average	O(S), bigger constant	Only existing letters are stored, but each map entry has object overhead (boxed Character, entry, table).

open this in the chapter →

26Graphs: BFS & DFS2 tables

Graph representations (V vertices, E edges)
	Adjacency list	Adjacency matrix	Edge list	why
Memory	O(V + E)	O(V²)	O(E)	A list stores only the edges that exist; a matrix reserves a slot for every possible pair.
Is there an edge u–v?	O(deg u)	O(1)	O(E)	The matrix is a direct lookup `m[u][v]`; a list must scan u's neighbours.
Visit all neighbours of u	O(deg u)	O(V)	O(E)	A matrix row has V slots even if u has only 2 neighbours.
Add an edge	O(1) amortized	O(1)	O(1) amortized	`ArrayList.add` is amortized O(1); a matrix write is a single assignment.
Full BFS / DFS	O(V + E)	O(V²)	O(V · E)	Traversal visits every vertex's neighbours once — cost depends on how fast neighbours can be listed.

Traversals and what they cost
	Time	Extra space	why
BFS (queue)	O(V + E)	O(V)	Each vertex is enqueued once; each adjacency list is scanned once. visited/dist + queue hold ≤ V items.
DFS (recursive)	O(V + E)	O(V)	Same work as BFS. The call stack can be V deep on a long path graph.
DFS (explicit stack)	O(V + E)	O(V + E)	A vertex can be pushed once per incoming edge before it's visited, so the stack can hold up to E entries.
Connected components	O(V + E)	O(V)	One outer loop over V; every inner traversal touches each vertex/edge only once in total.
Grid BFS / DFS (R × C)	O(R · C)	O(R · C)	V = R·C cells and E ≤ 4·R·C, so O(V + E) = O(R·C). Visited marks or recursion can cover the whole grid.
Cycle check / bipartite check	O(V + E)	O(V)	They are a single DFS/BFS with a colour array instead of a boolean array.
Multi-source BFS (k sources)	O(V + E)	O(V)	All k sources start in one queue and every vertex still enters it once. k separate BFS runs would cost O(k · (V + E)).
Implicit-graph BFS (N words of length L)	O(N · L² · 26)	O(N · L)	Each word is expanded once: L positions × 26 letters, and each candidate costs O(L) to build and hash.

open this in the chapter →

27Shortest Paths2 tables

Single-source shortest paths
	Time	Space	Weights	why
BFS	O(V + E)	O(V)	all equal	Each node and edge is handled once. Only correct when every edge costs the same.
0-1 BFS (deque)	O(V + E)	O(V)	0 or 1	A node is pushed at most twice; the deque never needs sorting.
Dijkstra, binary heap (lazy)	O((V + E) log V)	O(V + E)	≥ 0	Up to E pushes and polls, each O(log E) = O(log V) because E ≤ V².
Dijkstra, plain array	O(V²)	O(V)	≥ 0	V rounds, each scans all V nodes for the minimum. Wins on dense graphs (E ≈ V²).
Bellman–Ford	O(V · E)	O(V)	any (detects negative cycles)	V − 1 rounds × E relaxations. Early exit when a round changes nothing.
Bellman–Ford, k rounds	O(k · (V + E))	O(V)	any	k rounds, each relaxing all E edges and copying dist (O(V)) so a round can't chain more than one new edge.

All pairs and extras
	Time	Space	why
Floyd–Warshall	O(V³)	O(V²)	Three nested loops over V; one V × V matrix updated in place.
Dijkstra from every node	O(V · (V + E) log V)	O(V + E)	V independent Dijkstra runs. Beats Floyd on sparse graphs.
Path reconstruction	O(path length)	O(V)	Store parent[v] when relaxing; walk back from the target and reverse.
Binary search on answer + BFS (grids)	O(mn · log R)	O(mn)	log R guesses (R = value range), each a full O(mn) BFS.

open this in the chapter →

28Union-Find & Minimum Spanning Trees2 tables

Union-Find: what each trick buys you (n elements)
	find / union	Space	why
Naive quick-union (no tricks)	O(n) worst	O(n)	Unions can build a chain like 0←1←2←…; find from the bottom walks the whole chain.
Union by size or rank only	O(log n) worst	O(n)	A node only gets deeper when its tree joins one at least as big, so its tree size doubles each time — at most log₂ n times.
Path compression only	O(log n) amortized	O(n)	Long paths are flattened the first time they are walked, so expensive finds pay for cheap future ones (Tarjan & van Leeuwen).
Both tricks	O(α(n)) amortized	O(n)	Tarjan's bound: m operations cost O(m·α(n)), and α(n) ≤ 4 in practice — effectively constant.
HashMap-based DSU (any keys)	O(α(n)) amortized, average	O(n)	Same algorithm with both tricks; each parent lookup is an average O(1) hash operation instead of an array index. (The short map version shown uses path compression only: O(log n) amortized.)

Minimum spanning tree algorithms (V nodes, E edges)
	Time	Extra space	why
Kruskal (sort + DSU)	O(E log E) = O(E log V)	O(V + E)	Sorting dominates; the E DSU operations add only O(E·α(V)). log E ≤ 2 log V because E ≤ V².
Prim, lazy (PriorityQueue of edges)	O(E log E) = O(E log V)	O(E)	Each edge is offered at most once (when the first of its ends joins the tree), so ≤ E offers and polls, each O(log E).
Prim, dense (array, no heap)	O(V²)	O(V)	V rounds, each scanning all V nodes for the cheapest. Best when E ≈ V², e.g. complete graphs of points.
Prim, Fibonacci heap (theory)	O(E + V log V)	O(V)	decrease-key is O(1) amortized. Rarely worth it in practice — and Java has no Fibonacci heap.
Brute force: try every spanning tree	Exponential	—	A complete graph has V^(V−2) spanning trees (Cayley's formula). Greedy + cut property avoids all of that.

open this in the chapter →

29Topological Sort2 tables

Topological sort methods (V vertices, E edges)
	Time	Extra space	why
Kahn (queue)	O(V + E)	O(V + E)	Each vertex is enqueued/polled once, each edge decremented once. Space is the adjacency list plus in-degree array and queue.
DFS + reverse post-order	O(V + E)	O(V + E)	Each vertex turns gray then black once, each edge is looked at once. Recursion depth can reach V.
Kahn with PriorityQueue (smallest order)	O(V log V + E)	O(V + E)	V offers and V polls on a heap cost O(log V) each; edges are still O(1) each.
Naive: repeatedly scan for a free vertex	O(V · (V + E))	O(V)	Up to V rounds, and each round rescans every vertex and edge to find one with no remaining prerequisite.
Longest path in a DAG (topo order + DP)	O(V + E)	O(V + E)	One topological pass; each edge relaxes its target once. On general graphs the same problem is NP-hard.

Cycle detection in a directed graph
	Time	Extra space	why
Kahn: output count < V	O(V + E)	O(V + E)	Vertices on a cycle never reach in-degree 0, so they are never output.
DFS with three colours	O(V + E)	O(V)	Colour array + recursion stack; one back edge to a gray vertex proves a cycle.
DFS with only visited[] (two states)	wrong	—	It can't tell "on my current path" (cycle) from "finished earlier" (fine) — it reports false cycles on diamonds like 0→1, 0→2, 1→3, 2→3.

open this in the chapter →

30Advanced Graphs: Euler Paths, Bridges & SCCs2 tables

Euler paths, bridges and SCCs (V vertices, E edges)
	Time	Extra space	why
Euler degree check	O(V + E)	O(V)	One pass over the edges counts each vertex's in- and out-degree.
Hierholzer (pointer per vertex)	O(V + E)	O(V + E)	Each edge is walked once; `used[u]` skips edges already taken, so nothing is scanned twice.
Hierholzer + min-heaps (LC 332)	O(E log E)	O(E)	Each ticket is offered to and polled from a heap once; each heap operation is O(log E).
Backtracking itinerary	exponential (worst case)	O(E)	A wrong early ticket may fail only much later; undoing and retrying can explore a huge number of orders.
Fleury (naive bridge checks)	O(E · (V + E))	O(V + E)	Before each of the E steps it asks "is this edge a bridge of the unused graph?" — a full search each time.
Bridges / cut vertices (low-link DFS)	O(V + E)	O(V + E)	One DFS: each vertex is entered once, each adjacency entry looked at once. Adjacency list plus tin, low and up to V stack frames.
Remove each edge + re-check connectivity	O(E · (V + E))	O(V + E)	E separate BFS runs, each O(V + E).
Kosaraju SCC	O(V + E)	O(V + E)	Two DFS passes. The extra O(E) is the reversed copy of the graph that pass 2 walks.
Tarjan SCC	O(V + E)	O(V) beyond the graph	One DFS; each vertex is pushed on and popped off the stack once. No reversed copy — just tin, low, onStack and the stack.

Weighted relations and derived graphs
	Time	Extra space	why
Evaluate Division: DFS per query	O(Q · (V + E))	O(V + E)	Each of the Q walks may visit every variable and edge once.
Evaluate Division: all-pairs closure	O(V³ + Q)	O(V²)	Every middle variable is tried for every pair (V³); then each query is a table lookup.
Evaluate Division: weighted union-find	O((E + Q) · log V) amortized	O(V)	Path compression alone gives amortized O(log V) per find (α(V) with union by size too); map lookups are O(1) on average.
Bus Routes: BFS over stops	O(Σ Lᵢ²)	O(Σ Lᵢ²)	A route with L stops joins every pair of them: L · (L − 1) directed edges per route.
Bus Routes: BFS over buses	O(Σ Lᵢ)	O(Σ Lᵢ)	The stop → buses index reads each stop entry once; each bus is polled once and each stop's bus list is scanned once.

open this in the chapter →

31Backtracking2 tables

How big is the search tree?
	Answers	Time	Extra space (excl. output)	why
Subsets of n distinct items	2ⁿ	O(n·2ⁿ)	O(n)	Every element is in or out → 2ⁿ subsets; copying each into the result costs up to n.
Permutations of n distinct items	n!	O(n·n!)	O(n)	n choices, then n−1, … → n! leaves; each leaf copies a path of length n.
Combinations: k of n	C(n, k)	O(k·C(n, k))	O(k)	One leaf per combination, each copied in O(k); the `start` index prevents re-ordering.
Branching b, depth d (phone letters, brackets)	≤ bᵈ	O(d·bᵈ)	O(d)	A full tree with b children per node has bᵈ leaves; recursion is d frames deep.
Grid path search, word length L	—	O(m·n·3ᴸ)	O(L)	m·n start cells; after the first step each cell has at most 3 unvisited neighbours.
N-Queens with O(1) attack checks	≪ n!	O(n!)	O(n)	Row r has at most n − r free columns, so the tree is bounded by n!; pruning makes it far smaller in practice.
Sudoku with m empty cells	1	O(9ᵐ) worst case	O(m)	Up to 9 digits per empty cell. Filling the cell with the fewest options first shrinks the real tree: under 100 calls on the judge's 26-clue puzzles.

Will it run in time? (≈10⁸ simple steps per second)
	Comfortable n	Steps at that n	why
O(2ⁿ) / O(n·2ⁿ)	n ≤ ~20	2²⁰ ≈ 10⁶ (×20 ≈ 2·10⁷)	Each extra element doubles the work, so the limit arrives suddenly.
O(n!)	n ≤ ~10	10! ≈ 3.6·10⁶	12! ≈ 4.8·10⁸ is already too slow; this is why LC 46 caps n at 6.
O(4ⁿ)	n ≤ ~10	4¹⁰ ≈ 10⁶	4ⁿ = 2²ⁿ — it behaves like 2ⁿ with twice the depth.
Constraints say n ≤ 10⁵	—	—	Backtracking is the wrong tool. Look for greedy, DP, two pointers or a heap.

open this in the chapter →

32Greedy Algorithms3 tables

Jump Game three ways
	Time	Extra space	why
Try every jump (recursion)	O(2ⁿ)	O(n)	Paths multiply at every index, and the same index is solved again and again. The stack is up to n deep.
DP: can you finish from index i?	O(n²)	O(n)	Each index may scan up to n later indices. One boolean per index.
Greedy furthest reach	O(n)	O(1)	One pass and one integer: the reachable indices are always a prefix.

This chapter's greedy moves
	Time	Extra space	why
Fewest jumps as BFS levels (LC 45)	O(n)	O(1)	`end` and `farthest` replace a queue, because every level is one contiguous range.
Restart after a negative prefix (LC 134)	O(n)	O(1)	Each station adds its gain to `tank` and `total` once.
Filter, then combine (LC 1899)	O(n)	O(1)	One look per triplet and three booleans.
Stretch to the last index (LC 763)	O(n)	O(1)	Two passes; `last[26]` has a fixed size whatever n is.
Range of possibilities (LC 678)	O(n)	O(1)	Two ints, `lo` and `hi`, updated once per character.
Two passes (LC 135)	O(n)	O(n)	One `candies` array, filled left to right and then right to left.
Smallest card starts a run (LC 846)	O(n log n)	O(n)	Every card is counted and consumed once, at O(log n) per `TreeMap` call.
Shortest job first	O(n log n)	O(n)	The sort dominates; the copy keeps the caller's array untouched.

Coins: greedy vs DP (k coin values, amount A)
	Time	Extra space	why
Biggest coin first	O(k log k)	O(k)	Sort the k values, then one division per value. Fast, but only right for canonical coin systems.
DP over every amount	O(A · k)	O(A)	Each amount 1..A tries every coin once. Always right.

open this in the chapter →

33Intervals2 tables

Keep the most non-overlapping intervals: three ways
	Time	Extra space	why
Try every subset	O(2ⁿ · n)	O(n)	2ⁿ subsets, each checked in O(n) after sorting. Hopeless past n ≈ 25.
DP over intervals sorted by start	O(n²)	O(n)	For each interval, look back at every earlier one (an LIS-style DP).
Greedy: sort by end + one pass	O(n log n)	O(1)–O(n)	The sort dominates. The pass is O(n). Space is whatever the sort needs.

Interval toolkit
	Time	Extra space	why
Sort intervals (`Arrays.sort(int[][], cmp)`)	O(n log n)	O(n)	Rows are objects, so Java uses its stable merge sort (TimSort), which may need up to n/2 temporary slots.
Merge overlapping intervals	O(n log n)	O(n)	Sort by start, then one pass. The output can hold n intervals.
Insert into a sorted, disjoint list	O(n)	O(n)	Already sorted, so no sort: copy before, absorb overlaps, copy after.
Max non-overlapping (activity selection)	O(n log n)	O(1)–O(n)	Sort by end, then one comparison per interval.
Max overlap: min-heap of end times	O(n log n)	O(n)	Sort, then each meeting does at most one poll and one offer at O(log n) each.
Max overlap: sweep over sorted starts/ends	O(n log n)	O(n)	Two sorts, then one linear merge-like walk.
Max overlap: difference array over range R	O(n + R)	O(R)	Two writes per interval, then one prefix-sum sweep over R slots. Best when R is small.
Free time of k people, N intervals in total	O(N log k)	O(k)	A heap holds each person's next interval: N polls and offers on a heap of size k.
Smallest interval per query (n intervals, q queries)	O(n log n + q log q)	O(n + q)	Sort both lists; each interval enters and leaves the heap once.

open this in the chapter →

34Bit Manipulation2 tables

Cost of the core moves (int = 32 bits, long = 64)
	Time	why
`&`, `\|`, `^`, `~`, `<<`, `>>`, `>>>`	O(1)	One CPU instruction that works on all 32 (or 64) bits in parallel.
Check / set / clear / toggle bit k	O(1)	One shift to build the mask plus one operator.
`Integer.bitCount`, `numberOfTrailingZeros`, `highestOneBit`	O(1)	Fixed-width tricks on one word. `bitCount` is a HotSpot intrinsic: it may compile to one POPCNT instruction on x86-64 CPUs that have it.
Count 1-bits with `n &= n − 1`	O(k), k = number of 1-bits	Each loop erases one 1-bit. At most 32 for an int.
Loop over every bit of a value V	O(log V)	V has about log₂V bits. For an int that is at most 32 steps, so O(1) in practice.
Enumerate all subsets of n items with masks	O(n · 2ⁿ)	2ⁿ masks, and building each subset checks n bits. n ≈ 20 is the practical limit (about 2·10⁷ steps).
Enumerate every submask of every mask	O(3ⁿ)	Each item is in neither, only the mask, or both. That gives 3 choices per item.

Bit tricks vs the usual tools
	Time	Extra space	why
Find the unpaired number: HashSet	O(n)	O(n)	Stores up to n/2 values that are still waiting for a partner.
Find the unpaired number: XOR fold	O(n)	O(1)	One int accumulator. Pairs cancel to 0.
Set of small ints (≤ 64): `long` mask	O(1) per op	8 bytes	Add, remove, contains, union and intersect are each one operator.
Set of ints 0…n−1: `boolean[n]`	O(1) per op	~n bytes	The JVM typically uses one byte per boolean.
Set of ints 0…n−1: `BitSet`	O(1) per op	~n/8 bytes	One bit per number, packed into a `long[]`. `cardinality()` is O(n/64).

open this in the chapter →

35Dynamic Programming2 tables

The DP ladder (Fibonacci / Climbing Stairs)
	Time	Extra space	why
Plain recursion	O(2ⁿ) (≈ 1.618ⁿ)	O(n)	Each call spawns two more; the tree has ~φⁿ nodes. Space is the recursion depth.
Memoization (top-down)	O(n)	O(n)	Each of the n+1 states is computed once; later calls are O(1) lookups. Memo + stack are O(n).
Tabulation (bottom-up)	O(n)	O(n)	One loop over n cells, O(1) work each. The table has n+1 slots, no stack.
Space-optimised	O(n)	O(1)	Each cell reads only the previous two, so two variables replace the table.

Classic DP shapes
	Time	Table space	Optimised space	why
1D linear (stairs, robber, decode ways)	O(n)	O(n)	O(1)	n states × O(1) transition; only the last 1–2 cells are read.
Coin change / Combination Sum IV (amount A, k values)	O(A·k)	O(A)	O(A)	A states, each tries k values. The 1D table is already minimal.
Grid m × n (unique paths, min path, maximal square)	O(m·n)	O(m·n)	O(n)	One O(1) step per cell; a row only reads itself and the row above.
Triangle (n rows)	O(n²)	O(n²)	O(n)	n(n+1)/2 cells, O(1) each; bottom-up needs only the row below.
0/1 knapsack (n items, capacity W)	O(n·W)	O(n·W)	O(W)	n·W cells, O(1) each. Pseudo-polynomial: it grows with the value W, not its digit count.
LIS	O(n²) or O(n log n)	O(n)	O(n)	n states × O(n) look-back; patience replaces the look-back with a binary search.
Two strings (LCS, edit distance)	O(m·n)	O(m·n)	O(min(m, n))	One cell per pair of prefixes; each reads 3 neighbours from this row and the previous one.
Interval DP (burst balloons)	O(n³)	O(n²)	O(n²)	n² intervals × O(n) choices of split point. Every interval may be read later, so no row trick.

open this in the chapter →

36DP Patterns2 tables

State-machine DP over n days
	Time	Extra space	why
Brute force: try every action	O(2ⁿ)	O(n)	Act or wait on every day, nothing remembered; the space is the recursion depth.
Cooldown (3 states) / fee (2 states)	O(n)	O(1)	n days × a constant number of states; each day reads only yesterday's numbers.
At most 2 trades (4 states)	O(n)	O(1)	buy1, sell1, buy2, sell2: four max() lines per day.
At most k trades (2k states)	O(n·k)	O(k)	Every day walks t = 1..k with two updates each. If k ≥ n/2, adding every rise is O(n).

The other families
	Time	Table space	Optimised space	why
Regex matching (text m, pattern n)	O(m·n)	O(m·n)	O(n)	(m + 1)(n + 1) cells, O(1) each; a row reads itself and the row above, so two rows would do.
Interleaving String	O(m·n)	O(m·n)	O(n)	One cell per (i, j) prefix pair; each reads up and left, so one row is enough.
Distinct Subsequences	O(m·n)	O(m·n)	O(n)	Each cell reads up and up-left: one row, filled right to left like 0/1 knapsack.
Palindromic Substrings	O(n²)	O(n²)	O(1)	2n − 1 centres × up to n/2 steps; the pal[i][j] table needs n² booleans, expanding needs none.
Target Sum (P = (total + target) / 2)	O(n·P)	O(n·P)	O(P)	n numbers × P sums; pseudo-polynomial, fine because the total is at most 1,000.
Max Profit in Job Scheduling	O(n log n)	O(n)	O(n)	The sort, then one O(log n) binary search per job.
Predict the Winner (game on a range)	O(n²)	O(n²)	O(n)	n(n + 1)/2 ranges × 2 choices; one row is enough if i runs downward.

open this in the chapter →

37Design Data Structures2 tables

Which piece answers which question fast (n stored items)
	find by key	add / remove	pick at random	nearest ≤ x	why
HashMap / HashSet	O(1) avg	O(1) avg	O(n)	O(n)	Hashing jumps straight to one bucket, but a hash table keeps no order and no index — random picks and floor lookups must walk it.
ArrayList (any order)	O(n)	add O(1) amortized · remove O(n), or O(1) by swapping with the last	O(1)	O(n)	Index access is one address calculation; finding a value is a scan. remove(i) shifts the tail unless you fill the hole with the last element.
Sorted ArrayList + binary search	O(log n)	O(n) to keep it sorted · O(1) amortized if keys only grow	O(1)	O(log n)	Binary search halves the range each step; inserting in the middle shifts the tail — unless every new key is the largest, as with timestamps.
TreeMap	O(log n)	O(log n)	O(n)	O(log n)	A red-black tree stays balanced, so every lookup, insert and floor/ceiling query walks one root-to-leaf path.
ArrayDeque as a stack	O(n)	O(1) at the top	—	O(n)	Only the top is reachable in O(1); anything else is a walk.

This chapter's designs: the slow method vs the designed one
	First idea	Designed	why
RandomizedSet.remove	O(n) — find, then shift (ArrayList only)	O(1) average	The map gives the index; the last element fills the hole, so nothing shifts.
RandomizedSet.getRandom	O(n) — walk a HashSet	O(1)	`values.get(random.nextInt(size))` is one index access.
FreqStack.pop	O(n) scan · O(log n) heap	O(1) average	The answer is always the top of group maxFreq, and maxFreq moves by one.
TimeMap.get (v versions of the key)	O(v) — scan back	O(log v)	The history is sorted by time, so the floor is a binary search.
FileSystem.ls (P stored paths, d names in the path, k listed)	O(P · L) — scan every path string	O(d · log c + k)	The tree walks d levels, each one TreeMap lookup among c siblings, then copies k sorted names.
DetectSquares.count (n points added)	O(n²) — scan pairs	O(c), c ≤ 1,001	Only points in the query's column can be a corner, and y ≤ 1000 limits that column to 1,001 different values.

open this in the chapter →

38Segment Trees, Fenwick & String Matching2 tables

Range-sum structures (n = array length)
	Build	Point update	Range sum	Space	why
Plain array, loop per query	O(n)	O(1)	O(n)	O(n)	Updates are a single write, but every query walks the whole range.
Prefix-sum array	O(n)	O(n)	O(1)	O(n)	One subtraction per query, but changing nums[i] shifts every prefix after i.
Sqrt decomposition	O(n)	O(1)	O(√n)	O(n)	√n chunks of √n values: a query sums ≤ √n chunks plus ≤ 2√n loose values.
Fenwick tree (BIT)	O(n log n) or O(n)	O(log n)	O(log n)	O(n)	Each loop adds or strips one bit of i, so it runs at most ⌊log₂ n⌋+1 times. A smarter build pushes each node to its parent once → O(n).
Segment tree	O(n)	O(log n)	O(log n)	O(n) (4n array)	2n−1 nodes built once. A query visits at most 4 nodes per level across ~log₂ n levels.
Segment tree + lazy propagation	O(n)	O(log n) per range add	O(log n)	O(n)	A range add stops at O(log n) fully covered nodes and parks the rest in lazy[] until someone looks deeper.

String matching (text length n, pattern length m)
	Preprocess	Search	Extra space	why
Naive (try every start)	—	O(n·m) worst	O(1)	Text "aaaa…a" with pattern "aa…ab" re-compares almost all m characters at each of n starts.
KMP	O(m)	O(n)	O(m)	The text pointer only moves forward; each fallback undoes an earlier step, so total work ≤ 2n.
Z-algorithm on pattern#text	—	O(n + m)	O(n + m)	The right edge r of the Z-box only moves right; every comparison either moves r or ends a position.
Rabin–Karp	O(m)	O(n + m) expected, O(n·m) worst	O(1)	O(1) per slide; characters are only compared on hash equality, which is rare unless you're unlucky (or the input is adversarial).
`String.indexOf` (JDK)	—	O(n·m) worst	O(1)	The JDK uses a straightforward (heavily optimised) scan, not KMP — great in practice, quadratic in theory.

open this in the chapter →

What each Java container costs

int[] (array)

ArrayList

LinkedList

ArrayDeque

HashMap / HashSet

TreeMap / TreeSet

PriorityQueue

String / StringBuilder

Each chapter's tables

`int[]` (array)

`ArrayList`

`LinkedList`

`ArrayDeque`

`HashMap` / `HashSet`

`TreeMap` / `TreeSet`

`PriorityQueue`

`String` / `StringBuilder`