recognition

Spot the pattern

Most interview problems are a known pattern in disguise. Learn the signals, and the first step stops being scary.

Thinking tools

Simulation15

Do exactly what the statement describes, step by step (often with a queue or a few counters), and keep the bookkeeping clean.

spot it when

  • The statement spells out a process: rounds, turns, a line of people
  • Small limits and no obvious shortcut
  • Digit-by-digit arithmetic with a carry

practise it

Math shortcut (closed form)6

Replace a loop or a search with a formula: Gauss's sum, a combination count, or a counting argument.

spot it when

  • The numbers form a known range like 0…n
  • "How many paths/ways" on a plain grid
  • The answer depends only on counts, not on the order of events

practise it

Recursion on a smaller input5

Trust the call: solve the same problem for a smaller input, then do one step of work to finish yours.

spot it when

  • The definition is self-similar (row n is built from row n − 1)
  • A list or string that shrinks by one element or pair
  • "This piece + the answer for the rest"

practise it

Divide and conquer9

Split the input into halves, solve each half recursively, then combine — about log n levels of work.

spot it when

  • Halving the input halves the work (xⁿ, sorted ranges)
  • The answer combines a left part and a right part
  • Build a balanced structure from a sorted array

practise it

write it from memory

template: Merge sort (and counting while you merge) →
GCD & prime sieve2

Euclid's algorithm finds gcd(a, b) in O(log min(a, b)); the sieve of Eratosthenes lists every prime up to n in O(n log log n).

spot it when

  • "Greatest common divisor", or fractions and ratios to simplify
  • Count or list the primes up to n
  • Two cycles must line up again (lcm)

practise it

Digit peeling (% 10 and / 10)4

`x % 10` reads the last digit and `x / 10` drops it; rebuild with `rev * 10 + d`, and check for overflow before the multiply, not after.

spot it when

  • "Reverse the digits" or "is the number a palindrome" without a String
  • Sum, square or count the digits of a number
  • The result must fit in a 32-bit int, or else return 0

practise it

Arrays & strings

Kadane / running best5

Carry the best answer that ends at the current index (or the best value so far) and decide at each step: extend or restart.

spot it when

  • "Maximum (or minimum) subarray sum or product"
  • Best buy-then-sell, or any best pair with i < j
  • A negative running total can only hurt what follows

practise it

Prefix & suffix passes3

The answer at i combines something about everything left of i with something about everything right of i; build each side in one pass.

spot it when

  • "Product of everything except i" without division
  • Each position depends on the max to its left and to its right
  • A rule must hold towards both neighbours (candy ratings)

practise it

Matrix traversal & in-place transforms5

Walk a grid by index arithmetic — shrinking boundaries, layers, transpose then reverse — without extra memory.

spot it when

  • "Spiral order" or "layer by layer"
  • "Rotate the matrix in place"
  • Index tricks like r × cols + c or r + c for diagonals

practise it

Compare at the first difference3

Strings are ordered by their first differing character: scan column by column and stop there.

spot it when

  • "Longest common prefix"
  • Words sorted in a custom alphabet
  • Deduce letter order from adjacent sorted words

practise it

String parsing9

Walk the string with an index, pulling out tokens and multi-digit numbers, and handle separators and empty pieces on purpose.

spot it when

  • The input is a path, an expression or an encoded string
  • Numbers with several digits sit inside the text
  • Repeated separators or empty tokens

practise it

In-place markers3

Reuse the input as scratch space — flip a sign, use the first row and column, or encode two states in one cell — for O(1) extra memory.

spot it when

  • "O(1) extra space" on an array or a matrix
  • Values are in 1…n, so indices can hold flags
  • Every cell's next state depends on the current board

practise it

Next permutation (pivot, swap, reverse)1

From the right, find the first dip; swap it with the smallest bigger value after it, then reverse the falling suffix — the next arrangement in dictionary order, in place.

spot it when

  • "Next lexicographically greater arrangement"
  • "Next greater number with the same digits"
  • Step through permutations one at a time without recursion

practise it

Boyer–Moore majority vote1

Keep one candidate and a counter: a match adds a vote, a different value cancels one. A value filling more than half the array always survives.

spot it when

  • "Appears more than n / 2 times" (or n / 3 with two candidates)
  • Find the majority in O(1) extra space
  • Pairs of different values can cancel each other out

practise it

Two pointers & sliding window

Two pointers (opposite ends)12

Start at both ends and move one pointer inward per step based on a comparison: pairs, palindromes and in-place reversals in O(n).

spot it when

  • Sorted array + "pair or triplet with sum X"
  • Palindrome check or reverse in place
  • Maximise the area between two lines

practise it

write it from memory

template: Two pointers (opposite ends) →
Two pointers (read / write)5

A fast read pointer scans every element; a slow write pointer marks where the next kept element goes.

spot it when

  • "Remove or move elements in place" and return the new length
  • Keep the relative order while filtering
  • Compact duplicates in a sorted array

practise it

write it from memory

template: Two pointers (read / write) →
Three-way partition (Dutch flag)2

Keep the zones < pivot | = pivot | unknown | > pivot with three indices and shrink the unknown zone one element at a time.

spot it when

  • Only three distinct values (0, 1, 2)
  • Partition around a pivot when many values are equal
  • Sort in one pass with O(1) space

practise it

Sliding window (fixed size)6

Slide a window of exactly k: add the element entering, remove the one leaving, and update the answer in O(1).

spot it when

  • "Every subarray or substring of length k"
  • "Contains a permutation or anagram of p"
  • Indices must be at most k apart

practise it

write it from memory

template: Sliding window (fixed size) →
Sliding window (variable size)9

Grow the right edge; while the window breaks the rule, shrink the left edge. Each index enters and leaves once, so it's O(n).

spot it when

  • "Longest or shortest contiguous subarray/substring such that…"
  • "At most k" distinct values, zeros or replacements
  • All numbers are positive, so sums grow with the window

practise it

write it from memory

template: Sliding window (variable size) →
Expand around center2

Every palindrome mirrors around a centre: try all 2n − 1 centres and expand outward while the ends match.

spot it when

  • "Longest palindromic substring"
  • "Count the palindromic substrings"
  • n up to a few thousand, so O(n²) is fine

practise it

Two pointers (one per sequence)2

Give each input its own pointer and advance the one that is behind or smaller: merge, compare or match two sequences in O(n + m).

spot it when

  • Two sorted arrays or lists to merge or intersect
  • "Is s a subsequence of t?"
  • Merge in place: fill from the back so nothing is overwritten

practise it

Hashing & prefix sums

Hash lookup (seen before?)14

Store what you've seen in a HashSet or HashMap so "have I seen x — or target − x — and where?" costs O(1) on average.

spot it when

  • "Pair that sums to target" in an unsorted array
  • "Contains a duplicate" or "first repeat"
  • Map old → new objects while copying a structure

practise it

Frequency counting18

Count occurrences with an `int[26]` or `map.merge(x, 1, Integer::sum)`, then reason about the counts instead of the order.

spot it when

  • "Anagram", "permutation of", "same letters"
  • "Most or least frequent"
  • Order doesn't matter, only how many of each

practise it

Group by a canonical key5

Give equivalent items the same key (sorted letters, letter counts, a normalised shape) and bucket them in a HashMap.

spot it when

  • "Group the items that are equivalent"
  • Anagrams, rotations or shifted strings
  • Two items match when some normalised form matches

practise it

Prefix sums5

prefix[i+1] = prefix[i] + a[i]; then any range sum is one subtraction — in 1D, or in 2D with inclusion–exclusion.

spot it when

  • Many "sum of range [l, r]" queries on an array that never changes
  • Running totals
  • Sums of rectangles in a matrix

practise it

write it from memory

template: Prefix sums + HashMap →
Prefix sum + HashMap4

A subarray (j, i] sums to k exactly when prefix[i] − prefix[j] = k, so count (or index) earlier prefixes in a HashMap.

spot it when

  • "Count subarrays with sum k" when negatives are allowed
  • "Longest subarray with equal 0s and 1s"
  • "Subarray sum divisible by k"

practise it

write it from memory

template: Prefix sums + HashMap →

Linked lists

In-place linked-list rewiring17

Reverse, splice and reconnect nodes by changing `next` pointers in place; a dummy head removes the special case for the first node.

spot it when

  • "Reverse" all or part of a list
  • "Merge, reorder or swap nodes" without making new ones
  • The head itself might change

practise it

write it from memory

template: Reverse a linked list →
Fast & slow pointers9

Move two pointers at different speeds (or with a fixed gap): they meet inside a cycle, and the slow one stops at the middle.

spot it when

  • "Detect a cycle" or "where does the cycle start"
  • "Middle of the list" in one pass
  • "N-th node from the end" in one pass

practise it

write it from memory

template: Fast & slow pointers →

Stacks & queues

Stack for matching & nesting10

Push context when you open a level; pop and combine when you close it — brackets, nested encodings, postfix expressions, paths.

spot it when

  • Brackets must match or nest
  • "Evaluate" an expression or decode k[…]
  • ".." means go back one level

practise it

Monotonic stack4

Keep the stack in increasing or decreasing order; whatever pops an element is its next greater (or smaller), and each index is pushed and popped once.

spot it when

  • "Next greater element" or "days until a warmer day"
  • Largest rectangle in a histogram
  • For each item, the nearest item to one side that beats it

practise it

write it from memory

template: Monotonic stack →
Monotonic deque2

A deque of indices in sorted value order: drop expired indices at the front and dominated ones at the back; the front is the window's best.

spot it when

  • "Max or min of every window of size k"
  • Shortest subarray with sum ≥ k when negatives exist
  • A DP step that needs the best of the last k states

practise it

write it from memory

template: Monotonic deque →
Stack & queue design7

Build containers from simpler parts: a queue from two stacks (amortized O(1)), a ring buffer with head + size, a stack that carries its running minimum.

spot it when

  • "Implement a queue/stack using…"
  • "Design a circular queue" with a fixed capacity
  • "Retrieve the minimum in O(1)"

practise it

Sorting

Merge sort & merging sorted runs6

Merge two sorted sequences by always taking the smaller head; merge sort applies that recursively, and counting during the merge solves inversion problems.

spot it when

  • "Merge two sorted lists or arrays"
  • Sort a linked list in O(n log n)
  • "Count pairs i < j where nums[i] > k·nums[j]"

practise it

write it from memory

template: Merge sort (and counting while you merge) →
Quickselect3

Partition around a random pivot and keep only the side that contains index k: O(n) on average to find the k-th element.

spot it when

  • "K-th largest or smallest" with all the data available
  • "K closest" when the order inside the answer doesn't matter
  • Find the median without sorting

practise it

write it from memory

template: Quickselect (k-th smallest or largest) →
Counting / bucket sort6

When keys are small integers or bounded counts, index an array by value (or by frequency) instead of comparing: O(n + range).

spot it when

  • Values lie in a small range (0…2, letters, 0…n)
  • "Top k by frequency" — a count is at most n
  • Group values into buckets of width t

practise it

Sort with a custom comparator3

Define the order you need (by frequency then value, by concatenation) and let the sort do the rest — with `Integer.compare`, not subtraction.

spot it when

  • "Arrange the numbers to form the largest number"
  • Sort by frequency, ties broken by value
  • The right order isn't the natural one

practise it

Trees

Tree DFS (bottom-up)11

Postorder: each child reports a value up (height, gain, found?), the parent combines them, and a global variable can track the best path.

spot it when

  • Height, depth, diameter or balance
  • A path that may bend through any node
  • Lowest common ancestor, or comparing two trees

practise it

write it from memory

template: Tree DFS that carries info (bottom-up and top-down) →
Tree DFS (top-down)7

Preorder: pass state down to the children (an allowed range, the depth, the path so far) and decide at each node.

spot it when

  • Each node must respect bounds set by its ancestors
  • Root-to-leaf path conditions
  • Visit by depth with DFS (right child first)

practise it

write it from memory

template: Tree DFS that carries info (bottom-up and top-down) →
Tree BFS (level order)9

A queue plus a size snapshot processes the tree one level at a time.

spot it when

  • "Level by level", "each depth", "right side view"
  • Minimum depth or the nearest leaf
  • Serialize row by row

practise it

write it from memory

template: Level-order traversal (tree BFS) →
Build a tree from traversals4

Pick the root (first preorder value, middle of a sorted range), split the rest into left and right parts, and recurse.

spot it when

  • "Construct the tree from preorder and inorder"
  • "Convert a sorted array to a balanced BST"
  • "Serialize and deserialize" a tree

practise it

BST property9

Left < node < right: walk one branch per step (O(h)), and an inorder traversal visits the values in sorted order.

spot it when

  • Search, insert or delete in a BST
  • "K-th smallest" or "validate" a BST
  • Iterate a BST in sorted order

practise it

write it from memory

template: BST search, insert, delete and validate →
Ordered map / set (floor & ceiling)4

TreeMap and TreeSet keep keys sorted, so floor, ceiling, first and last are O(log n) — perfect for "nearest value" questions.

spot it when

  • "Closest value ≤ or ≥ x" while inserting
  • Bookings or intervals that must not overlap
  • Repeatedly take the smallest remaining key

practise it

Iterative tree DFS (explicit stack)3

Do the call stack's job yourself with an ArrayDeque: dive left pushing nodes, pop one, visit it, go right — same order as recursion, but no StackOverflowError.

spot it when

  • "Can you do it without recursion?"
  • The tree may be 10⁵ levels deep (a skewed chain)
  • Pause and resume a traversal (an iterator, next smallest)

practise it

write it from memory

template: Tree traversals (pre, in, post — recursive and iterative) →

Heaps

Top-k with a size-k heap6

Keep a heap of size k (a min-heap for the k largest): its root is the k-th best, and each update costs O(log k).

spot it when

  • "K largest, smallest, closest or most frequent"
  • "K-th largest in a stream"
  • k is much smaller than n

practise it

write it from memory

template: Top k with a size-k heap →
Two heaps (median)1

A max-heap holds the lower half and a min-heap the upper half; keep their sizes balanced and the median sits on top.

spot it when

  • "Median of a data stream"
  • A running median as numbers arrive
  • Balance a lower half against an upper half

practise it

write it from memory

template: Two heaps (running median) →
K-way merge5

Put the head of each sorted list in a min-heap; pop the smallest and push its successor: O(N log k).

spot it when

  • "Merge k sorted lists or arrays"
  • The newest n items across many sorted feeds
  • Smallest range covering k lists

practise it

Greedy with a heap6

Keep the candidates in a heap and always act on the current best (largest count, heaviest stone, earliest end time).

spot it when

  • "Repeatedly take the two largest"
  • Schedule tasks with a cooldown, or spread equal letters apart
  • How many rooms or servers are busy at once

practise it

Tries

Trie (prefix tree)10

Store words character by character in a tree so prefix questions cost O(word length), not O(number of words); a binary trie does the same with bits.

spot it when

  • "Starts with", autocomplete or other prefix queries
  • Search many words at once (a word-search grid)
  • Wildcard '.' matching, or the maximum XOR of a pair

practise it

write it from memory

template: Trie (prefix tree) →

Graphs

Graph DFS / BFS traversal10

Visit everything reachable with DFS or BFS and a visited set; restart from each unvisited node to count connected components.

spot it when

  • "Connected", "groups", "provinces", "reachable"
  • Clone or copy a graph
  • An adjacency matrix or list is given

practise it

write it from memory

template: Graph DFS (recursive & iterative) →
Grid flood fill4

Treat cells as nodes and their 4 neighbours as edges; one DFS or BFS from a cell marks its whole region.

spot it when

  • "Number of islands" or regions in a grid
  • "Fill the area connected to (r, c)"
  • Mark cells as visited by changing them in place

practise it

write it from memory

template: Grid BFS (flood fill & shortest steps) →
BFS shortest path (unweighted)9

BFS visits nodes in order of distance, so the first time it reaches the target is the fewest steps.

spot it when

  • "Minimum number of steps, moves or transformations"
  • Every move costs the same
  • The states are implicit (words, board positions)

practise it

write it from memory

template: BFS shortest path (unweighted graph) →
Multi-source BFS5

Seed the queue with every source at distance 0 and expand them together, layer by layer.

spot it when

  • "Minutes until every cell is affected" from several starts
  • Distance from each cell to the nearest X
  • Peel layers from all leaves or all edges at once

practise it

write it from memory

template: Multi-source BFS →
Bipartite check (two-colouring)1

Colour each node opposite to its neighbour with BFS or DFS; a clash means an odd cycle, so the graph isn't bipartite.

spot it when

  • "Split into two groups with no edge inside a group"
  • "Is the graph bipartite?"
  • Odd cycles must be detected

practise it

Topological sort & cycle detection8

Order a DAG so every edge points forward: Kahn's algorithm peels nodes with in-degree 0 (or use DFS colours); if some never peel, there's a cycle.

spot it when

  • Prerequisites, dependencies or a build order
  • "Is it possible to finish everything?" (is there a cycle?)
  • Derive an order from pairwise rules

practise it

write it from memory

template: Topological sort (Kahn & DFS) →
DP on a DAG3

Process nodes in topological order (or DFS + memo) so each node's best value is final before anything reads it.

spot it when

  • "Longest path" or "earliest finish time" with dependencies
  • "Number of ways" along shortest paths
  • Strictly increasing moves on a grid, so no cycle is possible

practise it

Dijkstra8

With non-negative weights, a min-heap always settles the closest unsettled node next: O((V + E) log V).

spot it when

  • "Shortest or cheapest path" with non-negative weights
  • Minimise the maximum step on a path (minimax)
  • Maximise a product of probabilities ≤ 1

practise it

write it from memory

template: Dijkstra (shortest path, weights ≥ 0) →
Bellman–Ford1

Relax every edge V − 1 times (or k + 1 times for a limit on edges), reading from a copy of the previous round.

spot it when

  • "At most k stops" or edges
  • Negative edge weights
  • Detect a negative cycle

practise it

write it from memory

template: Bellman–Ford →
Floyd–Warshall1

All-pairs shortest paths in O(V³): for each middle node k, try i → k → j for every pair.

spot it when

  • Distances between every pair of nodes
  • V up to a few hundred
  • "Within a threshold distance" for every node

practise it

write it from memory

template: Floyd–Warshall (all pairs) →
0-1 BFS2

When edges cost 0 or 1, a deque replaces the heap: push 0-cost moves to the front and 1-cost moves to the back.

spot it when

  • Moves are free or cost exactly 1
  • "Minimum number of changes or removals" on a grid
  • Dijkstra works, but O(V + E) is possible

practise it

Bridges & articulation points (Tarjan)1

One DFS with discovery times and low-links finds every edge or node whose removal disconnects the graph.

spot it when

  • "Critical connections" in a network
  • Single points of failure
  • Removing one edge or node splits the graph

practise it

Euler path (Hierholzer)1

To use every edge exactly once, check the degrees, then walk until stuck and add each vertex when it runs out of edges; reverse that list.

spot it when

  • "Use every ticket, domino or pair exactly once"
  • Rebuild one sequence from overlapping pieces
  • In-degree and out-degree differ by at most 1

practise it

Union-Find

Union-Find (DSU)13

A parent array with path compression and union by size merges groups and answers "same group?" in near O(1).

spot it when

  • Connections arrive one at a time (online)
  • "Same group?", "how many groups?", "which edge is redundant?"
  • Equivalence rules like a == b

practise it

write it from memory

template: Union-Find (DSU) →
Minimum spanning tree (Kruskal / Prim)2

Connect every node at the least total weight: sort edges and union them (Kruskal), or grow from one node with a heap (Prim).

spot it when

  • "Connect all points or cities at minimum cost"
  • Edges that every (or some) MST must use
  • A dense graph given as coordinates

practise it

write it from memory

template: Prim's minimum spanning tree →

Backtracking

Backtracking: subsets2

Every element is in or out: record the path at every node of the recursion tree. With duplicates, sort and skip equal siblings.

spot it when

  • "All subsets" or "the power set"
  • n ≤ 20, so 2ⁿ is allowed
  • Duplicates in the input, but each answer must be unique

practise it

write it from memory

template: Backtracking: subsets →
Backtracking: permutations1

Fill the positions one at a time from the unused elements (a `used[]` array or swapping), undoing each choice.

spot it when

  • "All orderings" or "arrangements"
  • n ≤ 8–10, so n! is allowed
  • Each element is used exactly once

practise it

write it from memory

template: Backtracking: permutations →
Backtracking: combinations & partitions5

Choose the next item (or the next cut point) from index `start` onward so each set is built once; prune as soon as the target is passed.

spot it when

  • "All combinations that sum to target"
  • "All ways to cut a string into valid pieces"
  • One choice per position (phone keypad letters)

practise it

write it from memory

template: Backtracking: combinations with pruning →
Backtracking with constraint pruning4

Place one piece at a time and only recurse while the partial state can still become valid; O(1) checks keep the tree small.

spot it when

  • Place items so none conflict (queens, sudoku)
  • Generate only valid strings (balanced parentheses)
  • Constraints you can check after each step

practise it

write it from memory

template: Backtracking: combinations with pruning →

Greedy & intervals

Greedy choice8

Commit to the locally best move and never undo it — after convincing yourself (an exchange argument) that it can't hurt.

spot it when

  • One pass where a failure lets you restart past it (gas station)
  • Always use the smallest available item first
  • A rule must hold from both sides (two greedy passes)

practise it

Greedy furthest reach3

Track the furthest index you can reach (or the current segment's end) and act when you arrive at it.

spot it when

  • "Can you reach the end?" or "minimum number of jumps"
  • Cut a string so each letter lives in exactly one part
  • Extend a segment while something inside it reaches further

practise it

Interval merging (sort by start)6

Sort by start; each interval either stretches the last merged one or starts a new one.

spot it when

  • "Merge overlapping intervals"
  • Insert an interval into a sorted list
  • The union of covered ranges

practise it

Interval scheduling (sort by end)2

Sort by end and keep the interval that finishes first: it leaves the most room for the rest.

spot it when

  • "Fewest intervals to remove so none overlap"
  • "Fewest arrows or points that hit every interval"
  • Most meetings that fit without overlap

practise it

Sweep line & difference array3

Turn intervals into +1 / −1 events (or a difference array), process them in order, and track the running total.

spot it when

  • "Maximum overlap" or rooms needed at the same time
  • Capacity checks along a route
  • Many range increments, then one read

practise it

Dynamic programming

1D DP10

dp[i] depends on a few earlier states (take or skip, a last step of 1 or 2, a word ending here); roll it down to O(1) variables.

spot it when

  • "Number of ways to reach step n"
  • "Maximum sum with no two adjacent"
  • Can the prefix be split or decoded validly?

practise it

write it from memory

template: 1D DP →
0/1 knapsack2

Each item is used at most once: dp[s] = can we make sum s; loop the sums downward so an item is never reused.

spot it when

  • "Partition into two subsets with equal sums"
  • Pick a subset that hits a target sum
  • Each item: take it or leave it, once

practise it

write it from memory

template: Knapsack (0/1 and unbounded) →
Unbounded knapsack3

Items can repeat: loop the sums upward. Coins in the outer loop count combinations; amounts in the outer loop count orderings.

spot it when

  • "Fewest coins" or "number of ways to make the amount"
  • An unlimited supply of each item
  • The order of choices doesn't matter

practise it

write it from memory

template: Knapsack (0/1 and unbounded) →
Longest increasing subsequence1

dp[i] = the longest run ending at i (O(n²)), or patience sorting: keep the smallest tail for each length and binary search it (O(n log n)).

spot it when

  • "Longest strictly increasing subsequence"
  • Chains or nesting (envelopes, pairs)
  • Keep as many items as possible in sorted order

practise it

write it from memory

template: Longest increasing subsequence →
2D DP on two strings (LCS / edit distance)5

dp[i][j] answers the question for the prefixes a[0..i) and b[0..j); each cell reads its left, top and diagonal neighbours.

spot it when

  • "Longest common subsequence"
  • "Minimum edits to turn a into b"
  • Two sequences compared character by character

practise it

write it from memory

template: Two-string DP (LCS, edit distance) →
Grid DP5

Moving only right or down, each cell's answer comes from the cell above and the cell to the left; one row of memory is enough.

spot it when

  • "Number of unique paths" in a grid
  • "Minimum path sum" moving right or down
  • Obstacles block some cells

practise it

write it from memory

template: Grid DP →
Interval DP5

dp[l][r] is built from smaller intervals inside it: fill by increasing length, or think about the last action inside the range.

spot it when

  • Palindromic substrings or palindrome partitions
  • "Burst, merge or remove — and the neighbours change"
  • The answer for [l, r] splits at some k inside

practise it

write it from memory

template: Interval DP →
State-machine DP4

Track a few named states per step (holding, sold, cooling down) and write the transitions between them.

spot it when

  • Buy and sell a stock with a cooldown or a fee
  • "At most k transactions"
  • At each step you're in one of a few modes

practise it

Bit manipulation

XOR cancellation3

x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels the pairs and leaves the odd one out.

spot it when

  • "Every element appears twice except one"
  • One number is missing from 0…n
  • A duplicate or missing value with O(1) extra space

practise it

write it from memory

template: Bit tricks →
Bit tricks (shift, mask, lowest set bit)11

Work one bit at a time with shifts and masks; n & (n − 1) clears the lowest set bit and n & −n isolates it.

spot it when

  • Count or reverse the bits of a number
  • "Power of two" or "add without +"
  • "Every element appears three times except one"

practise it

write it from memory

template: Bit tricks →
Bitmask as a set4

An int's bits form a set of up to 32 flags: enumerate subsets as 0…2ⁿ − 1, or mark seen digits in O(1).

spot it when

  • n ≤ 20 and you need every subset
  • A small fixed alphabet (digits 1–9) to mark as seen
  • Store a set of flags in one number

practise it

write it from memory

template: Bit tricks →

Range queries & string algorithms

Fenwick tree (BIT)2

Prefix sums that survive updates: both update(i, delta) and prefixSum(i) take O(log n) using i & −i jumps.

spot it when

  • Range sums with point updates
  • "Count smaller elements after self" (with coordinate compression)
  • Running rank or count queries as values arrive

practise it

write it from memory

template: Fenwick tree (BIT) →
Segment tree1

A tree over array ranges answers any associative range query (sum, min, max) and handles updates in O(log n).

spot it when

  • Range min, max or sum with updates
  • Range updates (lazy propagation)
  • The operation can't be undone by subtraction (min, max)

practise it

write it from memory

template: Segment tree →
KMP / prefix function4

pi[i] is the longest proper prefix of s[0..i] that is also a suffix; the match never moves backwards, so search is O(n + m).

spot it when

  • "Find the pattern in the text" in linear time
  • The longest prefix that is also a suffix
  • Is the string one block repeated?

practise it

write it from memory

template: KMP (prefix function) →
Rolling hash (Rabin–Karp)3

Hash every length-L substring in O(1) each by sliding: remove the leading character, add the trailing one, modulo a large prime.

spot it when

  • Compare many same-length substrings quickly
  • "Longest duplicate (repeated) substring"
  • Pairs well with binary search on the length

practise it

Design

HashMap + doubly linked list1

The map finds a node in O(1); the list keeps recency order, so moving or evicting a node is O(1) too.

spot it when

  • "LRU cache" with O(1) get and put
  • Evict the least recently used item
  • You need fast lookup and fast reordering together

practise it

HashMap + array (O(1) random access)1

An array holds the values and a map holds each value's index; delete by swapping with the last element.

spot it when

  • "Insert, delete and getRandom in O(1)"
  • Pick uniformly at random from a changing set
  • Remove from the middle of an array in O(1)

practise it

Class design: state + operations4

Keep only the state the operations need, in private fields set by the constructor; each method checks its input, updates that state and returns the result.

spot it when

  • "Implement the X class" with a constructor and a few methods
  • Each call changes a small counter, flag or list and returns a status
  • Invalid calls must return false or -1 instead of throwing

practise it

Hash table from scratch (chaining)1

An array of buckets: hash the key to an index with floorMod, keep a short linked chain per bucket, and compare keys only inside that one chain.

spot it when

  • "Design a HashSet / HashMap" without the built-in hash libraries
  • Keys come from a huge range but only a few are ever stored
  • You must explain how hashCode and equals work together

practise it

chapter signals: what you see → what you think

Constraints like nums[i] ≤ 10⁹ and you add or multiply values→ long sums and (long) a * bJava MemoryBinary search on indices or on an answer range near 2³¹→ lo + (hi - lo) / 2, never (lo + hi) / 2Java Memory"Modify in place" and the method returns void→ Change the array's contents through the reference you were givenJava MemoryA helper needs to give back two numbers→ Return an int[] or a record; int parameters are copiesJava MemoryCollecting paths or subsets while backtracking→ Save new ArrayList<>(path), not pathJava MemoryRecursion depth can reach 10⁴–10⁵ (long list, skewed tree, path graph)→ Stack overflow risk: loop or explicit ArrayDequeJava MemoryComparing strings, Integers or arrays→ equals / Arrays.equals, never ==Java Memory"Only lowercase English letters"→ int[26] with c - 'a' — no HashMap neededJava Arrays & StringsValues in a small range, like 1 ≤ nums[i] ≤ 100→ A counting array indexed by the value: new int[101]Java Arrays & StringsReturn a string you build piece by piece→ StringBuilder, then one toString()Java Arrays & Strings"Words separated by one or more spaces"→ trim() + split("\\s+"), or scan with an indexJava Arrays & Stringsm × n grid, matrix, int[][]→ grid.length rows, grid[r].length columns; r outer, c innerJava Arrays & StringsReturn type List<Integer> / List<Boolean>→ new ArrayList<>(n) when n is known; values get boxedJava Arrays & StringsOutput size known up front (2n, n + 1, m·n)→ Allocate new int[size] once and fill it by index arithmeticJava Arrays & Strings"Design" or "Implement the X class" with a list of methods→ Private fields for state, a constructor, one small checked method per operationJava OOPYou need a Node, TrieNode or Entry inside your class→ private static class NodeJava OOPA pair or grid cell must be a HashMap key or go in a HashSet→ A record, or equals + hashCode written togetherJava OOPFour directions, three states, a fixed set of types→ An enum (or one constant int[][] table)Java OOP"Without using any built-in hash table / LinkedList library"→ Build it from an array plus your own Node classJava OOPThe method takes ListNode head or TreeNode root→ LeetCode's classes: read val, next, left, right directly; null is emptyJava OOP"Input: the first line has n, the next line has n integers"→ Stdin mode: FastReader template in, StringBuilder or PrintWriter outI/O & Debugging"Read until the end of input" / no count given→ readLine() loop until it returns nullI/O & Debuggingn up to 10⁵–10⁶ in the constraints→ Need O(n log n) or better — and fast I/O in stdin modeI/O & DebuggingTLE, but your algorithm is O(n)→ Suspect Scanner or println-per-line before the algorithmI/O & DebuggingSamples pass, WA on hidden tests→ Edge cases and overflow: write them as your own testsI/O & DebuggingRE on a hidden test→ Index bounds, null, parse of a bad token, recursion depthI/O & DebuggingYour output looks right but the verdict is WA→ Format: missing newline between answers, extra text, forgot flushI/O & Debugging"Most recent", matching brackets, undo, monotonic stack→ ArrayDeque as a stackJava ToolkitLevel-by-level, BFS, "process in arrival order"→ ArrayDeque as a queueJava ToolkitFrequencies, "how many times", grouping by a key→ HashMap (merge / computeIfAbsent) or int[26]Java Toolkit"Closest value ≤ x", sorted keys while inserting, calendar/booking→ TreeMap / TreeSet floor & ceilingJava Toolkit"k largest", "k closest", "next smallest event", merging k lists→ PriorityQueueJava ToolkitOnly lowercase letters→ int[26] indexed by c − 'a'Java ToolkitAnswers "modulo 10⁹+7" or values up to 10⁹ being multiplied→ long arithmetic, reduce after each stepJava Toolkit"Find two/k items that add up to / match something"→ HashMap of what you've seen (or sort + two pointers)MindsetInput is sorted→ Binary search or two pointersMindsetContiguous subarray / substring with a condition→ Sliding window or prefix sumsMindset"Top k", "k-th largest", "closest k"→ Heap (PriorityQueue)Mindset"All combinations / permutations / subsets", n ≤ 20→ Backtracking (exponential is allowed)Mindset"Number of ways", "min/max cost", choices that repeat→ Dynamic programmingMindsetGrid, network, dependencies, "connected"→ Graph BFS/DFS, union-find, topological sortMindsetn up to 10⁵ or 10⁶→ You need O(n log n) or O(n) — nested loops will time outMindsetA loop variable that halves or doubles (i /= 2, i *= 2, lo..hi shrinking by half)→ O(log n)Big-OA loop nested inside another loop over the same input→ O(n²) — unless the inner pointer never resets (then it's O(n) total)Big-OTwo pointers or a sliding window where each pointer only moves forward→ O(n) amortized: each index is visited a constant number of timesBig-OSorting before the main loop→ At least O(n log n)Big-ORecursion with two calls on n − 1→ O(2ⁿ) — look for repeated subproblems (DP) to fix itBig-ORecursion that halves the input and does O(n) work per level→ O(n log n) (merge sort shape)Big-OConstraints with n ≤ 20 or n ≤ 10→ Exponential or factorial search is intendedBig-OThe answer for n is defined using the answer for n − 1, n / 2, or a sub-part→ Write the recurrence first, then the base caseRecursionNested or tree-shaped input (trees, folders, expressions, nested lists)→ Recursion on each child, combine the resultsRecursion"Generate all", "list every", "all combinations / permutations / subsets"→ Recursion with choices → backtrackingRecursionSame arguments show up again and again in the recursion tree→ Add a memo → dynamic programmingRecursionWork from the end of a linked list back to the front→ Recurse to the end, act while unwindingRecursionHuge exponent / repeated multiplication (xⁿ, matrix powers)→ Divide and conquer: halve n each callRecursion"The answer may be large, return it modulo 10⁹+7"→ Reduce after every + and ×, use long for products, divide with Fermat's inverseMath & NumbersFractions, slopes or ratios that must compare exactly→ Reduce (dy, dx) by their gcd with one sign rule — never use doubles as keysMath & NumbersCount primes, or smallest prime factors for many numbers→ Sieve once up to the limitMath & Numbersxⁿ with n up to 10⁹ or 10¹⁸→ Fast power: square and multiply, O(log n)Math & Numbers"How many ways to choose / arrange"→ nCr: Pascal's rule, or factorials with inverse factorials mod pMath & NumbersReverse, palindrome or digit sums of a number, "without converting to a string"→ Peel digits with % 10 and / 10; guard overflow before rev * 10Math & Numbers"Pick with probability proportional to weight"→ Prefix sums + binary search for the first prefix ≥ ticketMath & NumbersTrailing zeros of n!→ Count the factors of 5: n/5 + n/25 + n/125 + …Math & Numbers"Contiguous subarray" with the max/min sum→ Kadane: extend or restart at each indexArrays & StringsSame, but the array is circular→ max(Kadane max, total − Kadane min), unless everything is negativeArrays & Strings"Best pair (i < j)" where the later element is compared with something earlier→ Keep a running min/max of the prefix (stock pattern)Arrays & Strings"Without division" or "product/sum of everything except i"→ Prefix and suffix accumulationsArrays & StringsAnagrams, permutations of letters, "same characters"→ Frequency array int[26] (or sorted string as a key)Arrays & Strings"Appears more than n / 2 times"→ Boyer–Moore vote: one candidate, one counterArrays & Strings"Next greater arrangement" or "next permutation"→ Pivot from the right, swap with the next bigger value, reverse the suffixArrays & StringsValues in 1..n (or "smallest missing positive") with O(1) space→ Index v − 1 is the home of value v: swap values home, or flip signsArrays & Strings"Rotate" or "shift" an array by k in O(1) space→ Three reversalsArrays & StringsBuilding a result string in a loop→ StringBuilder, never +=Arrays & Strings"Spiral order", "layer by layer", "ring"→ Four shrinking walls, with guards for a single leftover row or columnMatrices"Rotate the image 90°" in place, n × n→ Transpose, then reverse every rowMatrices"If a cell is 0, set its whole row and column to 0"→ Mark first, write later; row 0 and column 0 as markersMatrices"All cells update at the same time", "next generation", "next state"→ Read old, write new: a copy, or two bits per cellMatrices"Write it in a zigzag", "rails", "up and down the rows"→ One builder per row with a direction that flips, or a cycle of 2·rows − 2Matrices"Neighbours", "adjacent", "8 directions"→ A DIRS array with one bounds checkMatrices"The k-th cell", "treat the matrix as one sorted list"→ Flat index: i = r·cols + c, back with i / cols and i % colsMatrices"Diagonal", "anti-diagonal"→ r − c is fixed on ↘, r + c is fixed on ↙MatricesThe array is sorted and you need a pair / triplet with some sum→ Opposite-ends pointersTwo Pointers"In place", "O(1) extra space", "remove", "move", "partition"→ read/write (same-direction) pointersTwo PointersPalindrome, reverse, symmetric comparisons→ Opposite-ends pointers comparing mirrored charactersTwo PointersMaximize/minimize something that depends on a width between two positions→ Start widest, move the limiting side (container pattern)Two PointersThree categories to separate (0/1/2, negative/zero/positive)→ Three pointers — Dutch national flagTwo Pointersk-Sum (3Sum, 4Sum)→ Sort, fix k−2 elements with loops, two pointers for the last twoTwo PointersTwo sorted arrays or strings to merge, compare or match in order→ One pointer per sequence; merging in place → fill from the backTwo PointersSquares or absolute values of a sorted array with negatives→ The biggest values sit at the two ends — build the answer from the backTwo Pointers"Contiguous subarray" or "substring" + longest / shortest / maximum / minimum→ Variable sliding windowSliding Window"Of size k", "every k consecutive", "average of each window"→ Fixed sliding windowSliding Window"At most k" distinct / zeros / replacements→ Variable window; shrink while the count exceeds kSliding Window"Contains all characters of", "anagram", "permutation of" inside a longer string→ Window + count array (fixed size for permutations, variable for covering)Sliding WindowEqual values "at most k indices apart"→ Fixed window of the last k values in a HashSetSliding Window"Concatenation of all words" (every word the same length)→ Window over words instead of letters — one run per starting offsetSliding Window"Maximum / minimum of every window"→ Monotonic deque of indicesSliding WindowSubarray sum equals k with negative numbers→ Not a window — use prefix sums + HashMap (chapter on hashing & prefix sums)Sliding Window"Find a pair / complement" in an unsorted array, return indices→ HashMap value → index, look up target − x before storing xHashing"Duplicate", "seen before", "unique", "first repeating"→ HashSet (add returns false on repeats)Hashing"Frequency", "most common", "anagram", "top k"→ Counting map or int[26]; then bucket sort or a heapHashing"Can you build X from the letters of Y?"→ Count Y's letters, then spend them on X (int[26])Hashing"Longest palindrome you can build" from given letters→ Use every pair; one leftover letter can sit in the middleHashing"Pattern", "isomorphic": each symbol must stand for exactly one thing→ Two maps (or two arrays), one per directionHashing"Sum of a range" asked many times on a fixed array→ Prefix sums: build once, answer in O(1)Hashing"Number of subarrays with sum = k" and values can be negative→ Prefix sum + HashMap of counts (sliding window breaks with negatives)Hashing"Longest subarray with equal 0s and 1s" / "balanced"→ Map 0 → −1, then the longest subarray with sum 0. Store the first index of each prefixHashing"Divisible by k", "multiple of k"→ Prefix sums mod k: equal remainders bracket a divisible subarrayHashingO(n) required and sorting is too slow→ Hash set or map: trade O(n) memory for timeHashing"Middle of the list", "split in half", "palindrome list"→ slow / fast pointers (fast moves 2)Linked Lists"Cycle", "loop", "where does the loop start"→ Floyd's tortoise and hare (then reset one pointer to head)Linked Lists"n-th from the end" in one pass→ Two pointers with a fixed gap of nLinked ListsThe head might change (delete head, merge, partition)→ Dummy head node — return dummy.nextLinked Lists"Reverse" all or part of a list, "reorder", "k-group"→ prev / curr / next rewiringLinked ListsTwo sorted lists → one sorted list→ Merge with dummy + tail (merge-sort step)Linked ListsSplit by a rule but keep the order (odd/even positions, < x vs ≥ x)→ Two dummy-headed chains, then join — and end the second with nullLinked Lists"Rotate the list by k" with a huge k→ Count n, use k % n, close into a ring, cut onceLinked Listsn + 1 values in 1..n, find the repeat, O(1) space, don't modify→ Treat i → nums[i] as a linked list; Floyd finds the cycle's entryLinked Lists"O(1) get and put", "most recently used"→ HashMap + doubly linked list (LRU)Linked ListsDeep copy with extra pointers→ HashMap old → new, or interleave copies to get O(1) spaceLinked ListsBrackets, tags or anything that opens and closes and can nest→ Push openers; a closer must match the topStacks"Next greater / smaller", "how many days until warmer", "nearest taller to the left"→ Monotonic stack of indicesStacksLargest rectangle, maximal area under bars, "span" of a value→ Increasing monotonic stack; measure when a bar is poppedStacksPostfix / prefix expression, calculator, "evaluate"→ Operand stack (plus an operator stack for infix)StacksNested encoding like 3[a2[c]], or a path with ..→ Stack of saved contexts — push on open, pop and combine on closeStacks"Undo", "go back", "most recent first"→ A plain stack of statesStacksThings meet or cancel out: colliding asteroids, a backspace # erasing the last letter→ Stack of survivors — the newcomer fights the most recent one firstStacks"Longest valid / balanced substring"→ Stack of indices with a base index at the bottom; measure i − topStacksRecursion might be too deep, or you're asked to do it iteratively→ Explicit stack replaces the call stackStacks"Process in the order they arrive", "first come first served", task scheduling→ Plain FIFO queue (ArrayDeque)QueuesShortest path / fewest steps in an unweighted graph or grid, level-by-level→ BFS with a queueQueues"Within the last X seconds / last k items", stream of timestamps→ Queue as a time window: offer new, poll expired from the frontQueuesMax or min of every window of size k→ Monotonic deque of indicesQueuesShortest/longest subarray with a sum condition and negative numbers→ Prefix sums + monotonic deque (LC 862)Queues"Design a circular queue / ring buffer / fixed-size buffer"→ Array + head + size, indices wrap with %QueuesRotation games: "move the top card to the bottom", "pass the ball k times", Josephus→ Simulate with a queue: poll then offerQueuesNeed both ends (add/remove front and back)→ Deque (ArrayDeque)QueuesInput is sorted (or each row of a matrix is) and you need O(log n)→ Classic binary search or lower/upper boundBinary Search"First", "last", "insert position", "how many equal to x"→ Lower bound / upper bound (lo < hi template)Binary Search"Minimum capacity / speed / time / largest minimum such that …"→ Binary search on the answer with a greedy feasibility checkBinary SearchSorted array that was rotated→ Compare mid with an end to find which half is sortedBinary Search"Find any peak" or local min/max in O(log n)→ Follow the slope at midBinary SearchConstraints like n ≤ 10⁵ with values up to 10⁹, and an O(n) check is easy→ O(n log V) — binary search over the value rangeBinary SearchTwo sorted arrays, k-th smallest / median→ Binary search on a partition of the shorter arrayBinary SearchAn expensive yes/no check that flips once ("is this version bad?", "does this build pass?")→ Find the first true with the lo < hi template — fewest callsBinary Search"k closest values to x" in a sorted array→ The answer is a window: binary search its start in [0, n − k]Binary SearchIntervals, meetings, schedules — anything with start/end→ Sort by start (or end), then sweep onceSorting"Find duplicates / closest pair / group equal things"→ Sort so equal or near values become neighboursSortingPair or triplet sums without needing original indices→ Sort + two pointersSorting"k-th largest / smallest", "top k"→ Quickselect (O(n) avg) or a size-k heap (O(n log k))SortingValues come from a small known range (0–100, three colours, lowercase letters)→ Counting sort / buckets in O(n + k)Sorting"Arrange to form the largest/smallest…", custom ordering rule→ Custom comparator — prove the rule is transitiveSortingCount pairs i < j with some order condition (inversions, reverse pairs)→ Merge sort and count during the mergeSortingSort a linked list in O(n log n)→ Merge sort (slow/fast split + merge)Sorting"Implement atoi", "parse this number", "is this a valid number"→ A small state machine: spaces → sign → digits (→ '.' → exponent), with an overflow guardParsing"Evaluate the expression" with + − * / and maybe brackets→ Two stacks (shunting-yard), result + last when there are no brackets, or recursive descentParsingOnly + and − with brackets and a unary minus→ Running total + a stack of (result, sign) pairsParsingRoman numerals, "amount in words", seconds → h:m:s→ Greedy value table, biggest firstParsing"Reverse the words" or "rotate" text in place→ Reverse everything, then reverse each piece backParsing"Exactly maxWidth characters per line", word wrap→ Greedy line filling, then spaces / gaps and spaces % gapsParsing"Encode a list of strings into one string", "serialize"→ Length-prefix framing (len#s), never a bare delimiterParsingSomething like k[...] or (...) that nests→ A stack of saved contexts, or recursion with a shared index (Stacks chapter)Parsing"Level", "row", "zigzag", "right side view", "average of each level"→ BFS with size = queue.size() per roundTraversals"Can you do it without recursion?"→ Explicit ArrayDeque stack — inorder: dive left, pop, visit, go rightTraversalsValues of a BST in sorted order, k-th smallest→ Inorder traversalTraversals"Copy", "serialize", "encode" a tree→ Preorder (or BFS) with a marker for every nullTraversals"Width", positions, gaps that count→ Number nodes like a heap array (2p, 2p + 1); re-base per levelTraversals"Distance k from a node", "time to spread through the tree"→ Parent map → undirected graph → BFS from the nodeTraversals"Point each node to its right neighbour"→ Level order; for O(1) space walk the level you already linkedTraversals"Inorder with O(1) extra space"→ Morris traversal (temporary threads, then restore)Traversals"Maximum/minimum depth", "height", "is balanced"→ Postorder: return the height up; use −1 or a record for "invalid"Tree Recursion"Diameter", "longest path", "any path" (doesn't have to pass the root)→ Return the best one-sided arm; record the two-sided bend in a global bestTree Recursion"Path sum" from root to leaf, "depth of every node", "max so far on the path"→ Pass the running value down as a parameter; decide at a leaf (both children null), not at nullTree Recursion"Return all the paths"→ Backtracking: one shared list — add, recurse, remove — and save copiesTree Recursion"Number of paths" that may start and end anywhere, going down→ Prefix sums on the current path + HashMap seeded with {0: 1}; undo when leaving a nodeTree Recursion"Complete tree", "count the nodes in less than O(n)"→ Compare the leftmost and rightmost depths; equal → perfect → 2^h − 1Tree Recursion"Flatten" a tree into a list "in place"→ Preorder rewiring: hang the right subtree under the left subtree's rightmost nodeTree Recursion"Ancestor", "where do p and q meet"→ Recursive LCA: return what you found; the split point is the answerTree Recursion"Same", "mirror", "symmetric", "subtree of" another tree→ Walk both trees in lockstep with one recursionTree Recursion"Construct / rebuild" from traversals→ Preorder from the front (or postorder from the back) gives the roots; inorder (via a HashMap) gives the left/right splitTree RecursionDeep tree (n up to 10⁵) and Java recursion→ Mention StackOverflow risk; offer an iterative versionTree RecursionThe input is a BST and you need sorted order→ Inorder traversal (iterative with a stack if you need to stop early)BST"Validate" / "is this a BST"→ Pass (low, high) down, or check inorder is strictly increasingBSTFind / insert / delete / closest value in a BST→ Walk one path using comparisons: O(h), O(1) space iterativelyBST"Next larger" / "successor" / "previous smaller" of a node→ Walk from the root remembering the best candidate (or TreeMap.higherKey)BSTLCA in a BST→ Walk down while both values are on the same side; first split = LCABST"Closest value", "next larger", "previous smaller" in a changing set→ TreeSet / TreeMap floor & ceilingBSTIntervals that must not overlap, bookings, merging on insert→ TreeMap keyed by start; check floorEntry and ceilingEntryBSTSliding window + "values within t of each other"→ TreeSet window with ceiling(x − t), or buckets of width t + 1BSTSorted array / list → tree→ Middle element as root, recurse on both halvesBST"k largest", "k smallest", "k closest", "top k frequent"→ Size-k heap in the opposite direction (or quickselect / buckets)Heaps"kth largest in a stream", values keep arriving→ Size-k min-heap; the root is the answerHeaps"median" of a changing collection→ Two heaps, sizes balanced within oneHeapsMerge k sorted things→ Min-heap of (value, source, index) cursorsHeaps"k smallest pairs / sums" from two sorted arrays→ Each row of the sum table is sorted → k-way merge over rowsHeaps"smallest range" with one element from each of k lists→ Heap of one pointer per list + track the max; always advance the minHeapsAlways process the most urgent / cheapest / biggest next (greedy)→ Priority queue keyed by urgency (task scheduling, Dijkstra, stones)HeapsChoices unlock as a resource grows ("at most k projects", capital, fuel)→ Sort by the unlock threshold + max-heap of what's unlockedHeaps"rearrange so no two equal items are adjacent"→ Max-heap by count, hold back the last used item one turnHeapsSchedule meetings / rooms by earliest end time→ Min-heap of end times (see the Intervals chapter)Heaps"prefix", "starts with", "autocomplete", "suggestions", "typeahead"→ Trie — walk to the prefix nodeTriesSearch many words at once in a grid or a string→ Put all words in a trie, run one DFS that follows the trieTriesWildcards like . matching any letter→ Trie + DFS that branches only at the wildcardTriesReplace words by their shortest root / dictionary prefix→ Trie: stop at the first end-of-word node on the walkTriesMaximize XOR of pairs, or XOR queries against a set→ Binary trie, highest bit first, greedily take the opposite bitTries"Built one character at a time", "every prefix is also a word"→ Trie DFS that only enters end-of-word nodesTriesCount words with a given prefix, with inserts and deletes→ Counting trie (pass / end counters)TriesTwo strings joined must form a palindrome, or match end-to-start→ Trie (or HashMap) of the words reversedTries"Minimum number of steps / moves / transformations" with all moves costing the same→ BFS from the start; level = answerGraphs"Count islands / provinces / groups / connected regions"→ Loop over every cell/vertex; each unvisited one starts a DFS/BFS → count++ (or union-find)GraphsA 2D grid of 0/1, '#'/'.', land/water→ Grid as a graph: 4-directional neighbours with a DIRS arrayGraphs"Spreads every minute", "all at the same time", "distance to the nearest X"→ Multi-source BFS: put every source in the queue firstGraphs"Split into two groups", "no two neighbours share a colour"→ Bipartite check with 2-colouringGraphsRegion that is "surrounded", "can reach the border", "flows to the ocean"→ Reverse it: start from the border/ocean and mark what's reachableGraphs"Deep copy" a graph with cycles→ HashMap original → clone + DFS/BFSGraphsDependencies / prerequisites — "is it possible?"→ Directed cycle detection (colours) or topological sort (its own chapter)Graphs"Fewest moves" in a puzzle: change one letter / gene, roll a die, move a knight→ BFS on an implicit graph — states are vertices, legal moves are edgesGraphs"Largest / size of" a connected region→ Flood fill that returns a count (1 + the neighbours' counts), keep the maxGraphs"Minimum cost / time / distance" with weighted edges→ Dijkstra (if no negative weights)Shortest Paths"At most k stops / k edges"→ Bellman–Ford with k + 1 rounds, or BFS by levelsShortest PathsNegative weights, or "detect an arbitrage / negative cycle"→ Bellman–Ford (or Floyd–Warshall's diagonal)Shortest Paths"Every pair", "for each city count reachable cities", n ≤ 100→ Floyd–WarshallShortest PathsCosts are 0 or 1 ("free if you follow the arrow", "remove an obstacle")→ 0-1 BFS with a dequeShortest PathsGrid where a path's cost is its largest step / highest cell→ Minimax Dijkstra, or binary search the answer + BFS, or union-findShortest PathsMaximise a product of probabilities ≤ 1→ Dijkstra with a max-heap (multiplying by ≤ 1 never helps, like adding ≥ 0)Shortest Paths"Number of shortest paths"→ Dijkstra + a ways[] array updated on tiesShortest Paths"Groups", "connected", "same component", "friends of friends", "merge accounts"→ Union-Find (or DFS) over the connection relationUnion-Find & MSTEdges/connections are given as a list and arrive over time→ Union-Find: union each edge, track count or detect the redundant oneUnion-Find & MST"Which edge creates a cycle?" or "is this a valid tree?" in an undirected graph→ The first union whose ends share a root; a tree also needs exactly n − 1 edgesUnion-Find & MSTEqualities and inequalities (a == b, b != c), or "is this assignment consistent?"→ Union all equalities, then check every inequality spans two setsUnion-Find & MST"Connect all … with minimum total cost"→ Minimum spanning tree — Kruskal (edge list) or Prim (dense)Union-Find & MST"Minimum time/threshold until two points become connected" while something rises→ Process cells/edges in sorted order with a DSU; stop when they join (or binary search + BFS)Union-Find & MST"How many extra edges/operations to connect everything?"→ Count components c; the answer is c − 1 (if enough edges exist)Union-Find & MST"prerequisites", "depends on", "must happen before", "build order"→ Directed graph + topological sortTopo Sort"Is it possible to finish / schedule everything?"→ Cycle detection: Kahn count or DFS gray back edgeTopo SortDerive an ordering from sorted examples (alien dictionary)→ Compare adjacent items, first difference = an edge, then topo sortTopo Sort"Minimum time when tasks run in parallel"→ Longest path in a DAG (Kahn + DP)Topo Sort"Smallest / lexicographically first valid order"→ Kahn with a PriorityQueueTopo SortStrictly increasing moves on a grid (longest increasing path)→ Implicit DAG: memoised DFS or peel by in-degreeTopo Sort"Find the centre / root that minimises height" of a tree→ Peel leaves layer by layer (Kahn on degree 1)Topo Sort"Use every ticket / edge / domino exactly once"→ Euler path: degree check + Hierholzer (add when stuck, reverse)Advanced Graphs"Critical connection", "single point of failure", "removing one link disconnects"→ Bridges with a tin/low DFS (articulation points if it's a node)Advanced GraphsDirected graph: "groups that can all reach each other", "collapse the cycles"→ SCCs (Kosaraju or Tarjan), then work on the condensation DAGAdvanced Graphs"a / b = k", conversion factors, "x is k times y"→ Weighted graph: multiply along a path (or weighted union-find)Advanced Graphs"Fewest buses / flights / transfers" — the cost counts groups, not single steps→ BFS where the groups are the verticesAdvanced GraphsRebuild one sequence from overlapping pieces (pairs that chain, de Bruijn)→ Euler path over the overlapsAdvanced Graphs"Return all …" (subsets, permutations, combinations, partitions, valid strings)→ Backtracking — the output itself is exponential, so nothing faster existsBacktrackingSmall constraints: n ≤ 10, 15, 20, a 9×9 board, words ≤ 15 letters→ An exponential search is allowed; plan choose / explore / un-chooseBacktracking"Place" items under constraints (queens, Sudoku digits, colours)→ Backtracking with O(1) constraint tables for pruningBacktrackingFind a path through a grid that spells / sums to something, cells used once→ DFS + mark cell + restore (grid backtracking)BacktrackingInput contains duplicates and output must be unique→ Sort, then skip equal neighbours at the same depthBacktracking"Count the number of ways" or "minimum / maximum" with large n→ Probably DP, not backtracking — overlapping subproblems give it awayBacktracking"Can you reach the end?" / "fewest jumps"→ Furthest reach; BFS levels without a queueGreedyCircular route with a running balance→ Gas Station: restart after any prefix that goes negativeGreedyConstraints from both neighbours (left and right)→ Two passes, one per direction (Candy)Greedy"Split into as many parts as possible" with a last-occurrence rule→ Partition Labels: stretch the end to the last indexGreedyA wildcard like * that can be several things→ Track the range of possible states (lo, hi)Greedy"Combine with max (or min) any number of times"→ Throw away anything that overshoots; the rest is harmlessGreedy"Split into groups of consecutive values"→ The smallest value must start a group (TreeMap)Greedy"Order jobs to minimise total or average waiting"→ Shortest first, proved by an exchange argumentGreedyCoins or weights with arbitrary values, "minimum number"→ Be suspicious of greedy. Try a counter-example, then use DPGreedy"Merge", "insert", "union of ranges"→ Sort by start, extend the last groupIntervals"Maximum number of non-overlapping …", "minimum removals so nothing overlaps"→ Sort by end, keep what fits (activity selection)Intervals"Minimum rooms / platforms / cars", "max concurrent", "capacity at any time"→ Min-heap of end times, sweep line, or difference arrayIntervals"Minimum arrows / points to cover all intervals"→ Sort by end, place the point at the earliest endIntervals"When is everyone free?"→ Merge all busy intervals; the gaps are the answerIntervals"For each query point, the best interval containing it"→ Sort the queries too (offline), sweep with a heapIntervalsSorted unique numbers to describe as ranges→ Stretch each run while the next number is one moreIntervals"Every element appears twice except one"→ XOR everything: pairs cancelBits"…appears three times except one"→ Count each bit position mod 3 (or the ones/twos state machine)BitsNumbers are exactly 0…n with one missing / one duplicated, O(1) space→ XOR values with indices (or the Gauss sum)Bits"Without using + / - / *"→ XOR = add without carry, (a & b) << 1 = the carries; shifts multiply by 2Bits"Power of two", "number of 1 bits", "binary representation"→ n & (n − 1), Integer.bitCountBitsn ≤ ~20 and "all subsets" / "try every combination"→ Loop mask from 0 to 2ⁿ − 1BitsState is a small set (visited nodes ≤ 16, letters a–z)→ Store the set in an int mask, often as a DP dimension (bitmask DP)Bits"Count the number of ways…"→ Counting DP: dp[state] = sum of ways of the smaller states it comes fromDynamic Programming"Minimum / maximum cost, length, profit…" with choices at each step→ Optimisation DP: dp[state] = best over choices (min/max)Dynamic Programming"Is it possible to…" (reach, split, partition, form)→ Feasibility DP with booleans: dp[state] = OR over choicesDynamic ProgrammingYour recursion has parameters that repeat (draw the tree — same arguments appear twice)→ Overlapping subproblems → memoizeDynamic ProgrammingChoose items with a weight/budget limit; each item once→ 0/1 knapsack (capacity loop downward in 1D)Dynamic ProgrammingUnlimited supply of each item (coins, ribbon pieces)→ Unbounded knapsack (capacity loop upward)Dynamic Programming"How many sequences add up to target" and the order matters→ Unbounded knapsack with the target loop OUTSIDE (Combination Sum IV)Dynamic ProgrammingTwo strings: compare, align, convert, common subsequence→ 2D DP on prefixes dp[i][j]Dynamic ProgrammingGrid, move only right/down (or down a triangle)→ Grid DP: dp[r][c] from above and left; triangles go bottom-upDynamic ProgrammingLargest square of 1s in a binary grid→ dp[r][c] = 1 + min(up, left, up-left): the square ending at this cornerDynamic ProgrammingSubsequence (not subarray!) that increases / is the longest→ LIS: O(n²) DP or O(n log n) patienceDynamic ProgrammingMerge / burst / split a range and the order matters→ Interval DP: dp[i][j], short intervals first, try every split point kDynamic Programmingn ≤ ~20 and you need subsets→ Probably backtracking or bitmask DP, not a plain tableDynamic ProgrammingBuy and sell with a cooldown, a fee, or at most k trades→ State-machine DP: one variable per mode, one max() per arrowDP Patterns"At most k" of anything (trades, deletions, operations)→ Add the count to the state: dp[…][t] for t = 0..kDP PatternsA pattern with '.' and '' must match the whole* string→ Two-string boolean DP; '*' = zero copies (j − 2) or one more (i − 1)DP PatternsCan s3 be formed by merging s1 and s2, keeping each one's order?→ dp[i][j] over two prefixes: the next letter came from s1 or from s2DP PatternsHow many times does t appear as a subsequence of s?→ Counting two-string DP: skip s[i] or use it; one row, j downwardDP PatternsCount (or find) palindromic substrings→ Expand around all 2n − 1 centresDP PatternsPut + or − before each number to hit a target; split into two groups by a difference→ Subset count with P = (total + target) / 2DP PatternsJobs or intervals with a profit, no overlaps, maximise the total→ Sort by end + DP + binary search for the last compatible jobDP PatternsAll intervals are worth the same→ Greedy by earliest end (Intervals chapter) — no DP neededDP PatternsTwo players take turns, "both play optimally"→ Game DP: one 'lead' per state, opponent's best comes back with a minus signDP Patterns"insert, delete and getRandom, all in O(1)"→ HashMap value → index + ArrayList; delete by swapping with the last elementDesign DS"pop the most frequent; on a tie, the most recent"→ count map + map from count to a stack, plus maxFreqDesign DS"value at timestamp t", "latest version ≤ t", "snapshot"→ Per-key history sorted by time + floor search (binary search or TreeMap.floorEntry)Design DS"mkdir", "ls", paths like /a/b/c, nested names→ Trie of names: each node maps a name to a child; TreeMap children for sorted outputDesign DS"count the squares/rectangles formed with stored points", "duplicates count separately"→ Count identical points; loop over the few points that can be a partner (same column or row)Design DS"O(1) get and put with eviction of the least recently used"→ HashMap + doubly linked list (LRU Cache, linked-lists chapter)Design DS"Design X" / "implement the class" with several methods and per-call targets→ The routine: API → cost per method → one structure per question → invariant → script testDesign DSMany range-sum queries, no updates→ Prefix sums (Hashing & Prefix Sums chapter) — don't overbuildRange Queries & StringsRange queries mixed with point updates, n and q up to ~10⁵→ Fenwick tree (sums) or segment tree (min/max/anything)Range Queries & Strings"Add v to every element in [l, r]" plus range queries→ Lazy segment tree (or difference array if there are no queries in between)Range Queries & Strings"How many elements to the left/right are smaller/greater?", inversions, reverse pairs→ Coordinate compression + Fenwick, or merge-sort countingRange Queries & StringsFind a pattern in a string, or "longest prefix that is also a suffix"→ KMP prefix functionRange Queries & StringsPeriodic / repeated strings, shortest palindrome by adding a prefix→ Prefix function on a cleverly glued string (s + '#' + reverse(s))Range Queries & Strings"Longest duplicate substring", many substring equality checks→ Binary search on length + Rabin–Karp hashingRange Queries & Strings