Part 1 · 23 topics · free

Part 1 — The Core DSA & Algorithm Cheatsheet

Built by analysing all 150 questions first, then extracting the union of every structure, pattern and Java mechanic they require — and nothing they don't. Written to be read cold.

Foundations

Read these first and carefully — everything else assumes them.

01 Complexity & Problem Triage What Big-O means, constraint → approach, how to triage a problem 12 min 02 Java Collections Toolkit What each structure is, what it costs, when to pick it; iteration & utility methods 33 min 03 Java Syntax Mechanics Char math, boxing traps, overflow, arrays, recursion 11 min 04 Ordering: Comparable, Comparator & Sorting Natural vs custom order, multi-key sorting, sorted collections of custom objects, sorting maps 18 min 05 equals, hashCode & Using Objects as Keys Why objects fail as HashMap keys, the contract, what to use instead of int[] 8 min

Patterns

One file per technique family. Read alongside the matching section.

06 Arrays & Hashing Trading space for a removed loop; key design 15 min 07 Two Pointers Using order to eliminate candidates 11 min 08 Sliding Window Incremental summaries over a moving range 14 min 09 Stack & Monotonic Stack Deferred resolution; next-greater problems 12 min 10 Binary Search Finding the boundary of a monotonic predicate 14 min 11 Linked List Dummy heads, fast/slow pointers, reversal, LRU 15 min 12 Trees & Binary Search Trees What each node needs from its children 15 min 13 Tries (Prefix Trees) Prefix structure and search pruning 8 min 14 Heaps / Priority Queues Cheap access to extremes; top-k, k-way merge, median 12 min 15 Backtracking Choose / explore / un-choose; dedup and pruning 14 min 16 Graphs Recognizing graphs; DFS vs BFS; topological sort 13 min 17 Union-Find (Disjoint Set Union) Connectivity as edges arrive 7 min 18 Advanced Graphs Dijkstra, Bellman-Ford, MST, Eulerian paths 10 min 19 Dynamic Programming Recursion plus remembering; the six recurrences 19 min 20 Greedy When a local choice is provably safe 11 min 21 Intervals Sort by start vs by end; sweep line 9 min 22 Bit Manipulation Operators, XOR properties, the eight tricks 11 min 23 Math & Geometry Matrix transforms, fast power, overflow-safe math 12 min

Derived by analyzing all 150 NeetCode questions and taking the union of their prerequisites. If a technique isn't needed by at least one of the 150, it isn't here. If a question needs it, it is.

These files assume no prior knowledge of the topic. Each one explains what the structure or technique is and why it exists before showing code, and every non-obvious algorithm is traced step by step on a concrete example.

How to read this

First pass — read files 01–05 carefully. They are the foundation: how to measure code speed, which Java structures exist, the language traps, how ordering works, and what makes an object usable as a hash key. Everything else assumes them.

Then read 06–23 in order, once, without memorizing. You are building an index of what exists, not learning it. When you later meet a problem and think "something about this feels like a window", you'll know where to look.

Then start Part 2, and come back to the relevant file whenever a question exposes a mechanic you fumbled. That third reading — with a concrete failure driving it — is when it actually sticks.

Vocabulary

Terms used throughout. Skip if they're already familiar.

n The input size — usually array length or string length

O(...) How the work grows as n grows. See 01

Amortized Averaged over a whole sequence of operations, not the single worst one

In place Modifying the input directly instead of building a copy — O(1) extra space

Auxiliary space Extra memory you use, not counting the required output

Subarray / substring A contiguous run of elements

Subsequence Elements in order but not necessarily adjacent — [1,3] is a subsequence of [1,2,3]

Monotonic Only ever increases, or only ever decreases — never both

Invariant Something guaranteed true at every step of a loop; the basis of correctness proofs

Predicate A function returning true/false

Greedy Take the locally best option and never reconsider

Memoization Caching results of a recursive function so each input is computed once

DFS Depth-first search — go as deep as possible, then back up

BFS Breadth-first search — explore in rings of increasing distance

DAG Directed acyclic graph — directed edges, no cycles

Sentinel A fake value or node that removes an edge case (dummy head, ±∞ bounds)

Lazy deletion Leaving stale entries in a heap and skipping them when they surface

Natural ordering A class's own default order, defined by Comparable.compareTo

Comparable Interface a class implements to define one built-in order

Comparator A separate object defining an order; you can have many

Total order A comparator that never returns 0 for genuinely different elements

Stable sort Equal elements keep their original relative order

The pattern decision tree

Interviews are won in the first 60 seconds of thinking. This is the sequence to run.

Step 1 — What is the shape of the input?

Input shape	First patterns to consider
Unsorted array; asked about existence, counts, or pairs	Hash map or hash set (06)
Sorted array — or you're allowed to sort	Two pointers (07), binary search (10)
Contiguous subarray or substring	Sliding window (08), prefix sums (06), Kadane (20)
Subsequence (non-contiguous)	Dynamic programming (19)
Nested or matched structure (brackets, expressions)	Stack (09)
"Next greater / smaller element", spans, histograms	Monotonic stack (09)
Linked list	Dummy head + fast/slow pointers (11)
Tree	DFS recursion, or BFS if the answer is level-shaped (12)
Prefixes or a dictionary of words	Trie (13)
Grid	DFS/BFS treating it as an implicit graph (16)
Explicit nodes and edges	Graph traversal (16), union-find (17), Dijkstra (18)
List of `[start, end]` pairs	Sort + sweep (21)
A single integer, or "without using `+`/`-`"	Bit manipulation (22)

Step 2 — What is the question asking for?

Asked for	Pattern
"Does X exist?" / "count of X"	Hash set / hash map
"Top / Kth largest or smallest"	Heap of size k, quickselect, or bucket sort (14, 06)
"Minimum / maximum value" over a set of choices	DP (19) or greedy (20) — see Step 3
"Number of ways"	DP (19)
"All possible ..." (enumerate every solution)	Backtracking (15)
"Shortest path", unweighted	BFS (16)
"Shortest path", weighted non-negative	Dijkstra (18)
"Shortest path" with a cap on edges used	Bellman-Ford (18)
"Minimum cost to connect everything"	MST — Prim or Kruskal (18)
"Valid ordering given dependencies"	Topological sort (16)
"Are these connected / how many groups"	Union-find or DFS flood fill (17, 16)
"Smallest value satisfying a condition"	Binary search on the answer (10)
"Longest/shortest window satisfying a condition"	Sliding window (08)

Step 3 — Greedy or DP?

Both optimize. Choose with this test:

Does a locally optimal choice provably stay optimal globally?

Yes → greedy. You must be able to state the exchange argument out loud: "swapping in the greedy choice never makes the answer worse." Examples: interval scheduling by earliest end time, jump-game reachability.
No, or you can't prove it → DP. If a choice's value depends on choices you haven't made yet, you need state.
Unsure in an interview? Say so, attempt a counterexample for greedy, and fall back to DP. Being wrong about greedy is far more costly than being verbose about DP — a DP solution one tier slower still passes; a wrong greedy doesn't.

Keep this counterexample loaded: Coin Change with coins = [1, 3, 4], amount = 6. Greedy takes 4+1+1 (3 coins); optimal is 3+3 (2 coins). It settles the question in one sentence.

Step 4 — Sanity-check against the constraints

Read n's bound before committing. Full table in 01; the short version:

`n` up to	Budget
10–12	`O(n!)`, `O(2ⁿ · n)` — backtracking is expected
~20	`O(2ⁿ)` — bitmask
~500	`O(n³)`
~5,000	`O(n²)`
~10⁵	`O(n log n)` — sorting, a heap, or binary search is in the answer
~10⁶+	`O(n)` or `O(log n)` — single pass, hashing, math

If your candidate approach is one tier too slow, the constraint is telling you which tier to reach for. And a small bound is not a small problem — it's permission to go exponential.

The ten mechanics that appear most across the 150

Ranked by how many of the 150 need them. If revision time is short, do these first.

1HashMap as a "seen before" index — value→index, char→count, node→clone. (06)
2Tree DFS that returns one value while updating a field — diameter, max path sum, balanced. (12)
3Two pointers on a sorted array, including the sort-then-scan setup for k-sum. (07)
4The variable-size sliding window loop — expand right, shrink left while invalid. (08)
5BFS with a level-size loop — level order, shortest path, multi-source spread. (12, 16)
6PriorityQueue with a custom comparator over int[] pairs. (14)
7The backtracking choose/explore/un-choose skeleton, plus the i > start dedup. (15)
8Bottom-up DP over a 1-D or 2-D table, then rolling-array space reduction. (19)
9Monotonic stack for next-greater and span problems. (09)
10Union-find with path compression for connectivity questions. (17)

Five arguments to have memorized

Interviewers ask for these by name. Each is one or two sentences, and each appears repeatedly.

Why the monotonic stack is `O(n)`

each index is pushed once and popped at most once, so total inner-loop work across the whole run is bounded by n. (09)

Why two pointers can discard a whole range

on sorted input, if the current pair's sum is too small, that left element can't pair with anything still in range, since the right element is the largest remaining. (07)

Why BFS finds shortest paths and DFS doesn't

BFS reaches nodes in non-decreasing distance order, so the first arrival is via a shortest path. DFS may arrive by a long detour first and then mark the node visited. (16)

Why Dijkstra needs non-negative weights

it finalizes the cheapest frontier node and never revisits it. A negative edge could later improve a finalized node, breaking that invariant. (18)

Why backward iteration makes knapsack 0/1

reading dp[t - num] before it's updated in this pass means it reflects the state before this item existed, so the item contributes at most once. (19)