Every programmer — beginner or senior — has been stuck staring at a blank editor, knowing what the answer should be but not knowing how to get there. This file fixes that. Not by giving you code to copy, but by teaching you how to see every problem: the pattern, the constraint, the trick. Problem → Think → Visualize → Code. Every time.
The difference between a programmer who gets stuck and one who doesn't isn't intelligence — it's process. Every problem, no matter how hard, yields to the same five questions asked in the same order.
Problem: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. Constraints: n ≤ 10⁴.
1. Given: Array of size n, distinct elements ranging [0, n].
2. Produce: A single integer missing from the sequence.
3. Simplest Case: `arr = [0, 1]` (n=2, should have 0,1,2). Missing is 2. `arr = [3, 0, 1]` (n=3). Missing is 2.
4. Math Relationship: The array *should* contain every number from 0 to n. If I sum the ideal range [0..n] and subtract the sum of the actual array, the difference mathematically must be the missing number.
5. Algorithm: Math formula for sum `n*(n+1)/2`, minus loop sum. O(n) time, O(1) space.
Solve by hand on paper first. Always. Pick 3–4 small examples. Trace what you do with your hands and eyes. Your code is just translating that manual process into instructions. If you can't solve it manually, you can't code it. If you can, coding it is mechanical.
| Constraint on n | What it means for your algorithm | Typical Pattern |
|---|---|---|
n ≤ 10 | Brute force everything | Try all permutations, all subsets |
n ≤ 20 | Bitmask or meet-in-middle | 2ⁿ is around 10⁶ — barely ok |
n ≤ 10² | O(n²) or O(n³) fine | Nested loops, all pairs |
n ≤ 10³ | O(n²) ok, O(n³) risky | Bubble/insertion sort, simple DP |
n ≤ 10⁵ | O(n log n) required | Sort, binary search, segment tree |
n ≤ 10⁶ | O(n) only | Single pass, hash map, sieve |
n ≤ 10¹⁸ | O(log n) or O(1) | Math formula, binary search on answer |
Write the O(n²) or O(2ⁿ) brute force first. Always. It gives you correct answers to verify against, it helps you understand the structure of the problem, and sometimes — especially in interviews — it's all you need. Optimize after you have correctness.
Look for: math formula, combinatorics, prefix sums, DP. Ask: can I compute it without enumerating all cases?
Look for: binary search on answer, greedy, DP. Ask: is there a monotone property? If I fix one thing, can I minimize the other?
Look for: DFS/BFS for reachability, two pointers, hash set membership. Often easier than finding the actual answer.
Look for: greedy construction, sort then assign, modular building. Start with what's forced, then fill in the rest.
Look for: DP with state, greedy with proof, binary search on the answer. The key: define the state precisely first.
Look for: model as graph, reduce to known problem. Ask: is this secretly a shortest path? A matching? A flow problem?
Given a number n, determine if it is prime. A prime has exactly two divisors: 1 and itself.
1. Given: An integer n. 2. Produce: True if prime, False otherwise.
3. Simplest Case: n=2 (True), n=4 (False: 2x2), n=9 (False: 3x3).
4. Math Relationship: A number n is prime if no integer from 2 to √n divides it evenly. Why √n? Because if n = a × b and a ≤ b, then a must be ≤ √n. If no factor exists up to √n, none exist beyond it either.
5. Algorithm: Iterate i from 2 to √n. If n % i == 0, return false. Skip evens early to optimize.
Mark all multiples of each prime as composite, starting from 2. What remains unmarked is prime. Time: O(n log log n). For n = 10⁶, this runs in milliseconds. See File 06 Ch17 for the full linear sieve.
A number is Armstrong (narcissistic) if the sum of its digits each raised to the power of the number of digits equals the number itself. Example: 153 = 1³ + 5³ + 3³.
1. Given: An integer n. 2. Produce: True if Armstrong, False otherwise.
3. Simplest Case: n=153. Digits are 1,5,3. 1³ + 5³ + 3³ = 1 + 125 + 27 = 153. True.
4. Math Relationship: The answer requires distinct mathematical operations: counting total digits, extracting individual digits sequentially, and summing their digit-wise powers.
5. Algorithm: Convert to string to count digits. Use a `while(n > 0)` loop with `% 10` (extract) and `/ 10` (remove) to compute sum. Compare sum to original.
A number is perfect if the sum of all its proper divisors (divisors excluding itself) equals the number. Example: 28 = 1 + 2 + 4 + 7 + 14.
Find all divisors of n from 1 to √n. For each divisor d, both d and n/d are divisors (add both, but don't double-count when d == n/d). Sum them all. Compare with n.
A number is strong if the sum of factorials of its digits equals the number itself. Example: 145 = 1! + 4! + 5! = 1 + 24 + 120.
Draw the pattern. Label each row with i (1 to n). For each row i, ask: How many spaces? How many stars/numbers? What changes? The answer is always a formula in i and n. Once you have those three formulas, the code writes itself with two nested loops.
For any pattern, look at row i (1-indexed, n rows total):
Q1: Leading spaces? — Often n-i or i-1 or 0.
Q2: Characters printed? — Often i, 2i-1, n-i+1, or something in between.
Q3: What is each character? — Star, digit (i or j), cumulative count?
You can solve rotation with three reverses. This is a technique worth memorizing because it works in O(n) time and O(1) space — no extra array needed.
Rotate left by k: Reverse [0..k-1], reverse [k..n-1], reverse entire array.
Rotate right by k: Reverse entire array, reverse [0..k-1], reverse [k..n-1].
Given array, find the maximum sum contiguous subarray (Kadane's algorithm). This is the most famous array problem and the logic behind it teaches you half of all array problems.
At each position, you have exactly two choices: extend the existing subarray (add current element to running sum), or start fresh at the current element.
Start fresh when? When the running sum becomes negative — because a negative prefix only drags you down. Any subarray starting after the negative part will be better.
Track the maximum sum seen at any point. That's your answer.
Rotate 90° clockwise: First transpose (swap a[i][j] with a[j][i]), then reverse each row. This is a two-step O(n²) in-place operation. No extra matrix needed.
Transpose rule: element at (i,j) goes to (j,i). Only swap upper triangle to avoid double-swapping.
Determine if a string reads the same forwards and backwards. Ignore case and non-alphanumeric characters for the "clean" version.
Create reversed copy. Compare with original. Simple, clear.
Left pointer at start, right at end. Move inward. Compare characters. Stop when mismatch or pointers cross.
Skip non-alphanumeric. Lowercase before comparing. Works for "A man, a plan, a canal: Panama".
Two strings are anagrams if one is a rearrangement of the other. "listen" and "silent" are anagrams. The fundamental tool here is the frequency map.
Any time a string problem involves counting characters, comparing character sets, or finding missing/extra characters, a frequency map (array[26] for lowercase letters, or unordered_map for general) is your first instinct. Build it in O(n), query it in O(1).
1. The Base Case (The Anchor): This is the simplest un-splittable unit. When n=0 or the array is empty, what's the answer? Stop here. DO NOT overthink it.
2. The Recursive State (The Leap of Faith): Assume your function already works flawlessly for n-1. Do not trace it down! Just take the imaginary result of f(n-1) and figure out the math to turn it into f(n). You trust the smaller version works, and just write one extra step.
Q1: Base case — When do I stop? (n=0, n=1, empty, single element)
Q2: Recursive case — How does the answer for n depend on the answer for n-1 (or smaller)?
Q3: Combine — What do I do with the recursive result to get the full answer?
At each recursive call, you branch based on choices. For "generate all subsets", at each element you branch: include it OR exclude it. For "generate all permutations", you branch by which element you place next. The recursion tree has choices^depth leaves — understand this to predict time complexity.
Binary search isn't just "is X in this array?". It's a technique for any monotone decision problem: if answer works for value x, it also works for all values ≤ x (or ≥ x). Whenever you see "find the minimum/maximum value such that some condition holds" — binary search on the answer. This reduces O(n²) or worse to O(n log n).
Find the minimum capacity of a ship that can ship all packages within D days, where packages[i] is the weight of package i and must be shipped in order.
Key Insight: If capacity C works (all packages shipped in D days), then any capacity > C also works. This monotone property means we can binary search on C.
Search space: Minimum possible C = max(packages) (must fit heaviest package). Maximum possible C = sum(packages) (ship everything in one day).
Check function: Given capacity C, greedily fill each day until adding next package would exceed C. Count days needed. If days ≤ D → C works.
| Situation | Best Sort | Reason |
|---|---|---|
| General purpose | std::sort (introsort) | O(n log n) guaranteed, fastest in practice |
| Need stable sort | std::stable_sort | Preserves relative order of equal elements |
| Nearly sorted array | Insertion sort | O(n) best case on nearly sorted input |
| Integer values in range [0,k] | Counting sort | O(n+k) — linear! |
| Sort by custom rule | sort with comparator | sort(v.begin(),v.end(),[](a,b){ return a.x < b.x; }) |
| Partial sort (need top k) | nth_element / partial_sort | O(n) average for nth_element |
GCD(a, b) = GCD(b, a mod b). The key insight: the GCD of a and b is the same as the GCD of b and the remainder when a is divided by b. Why? Because any common divisor of a and b also divides a - k*b (for any integer k), which includes a mod b. Each step shrinks the numbers, converging to GCD in O(log min(a,b)) steps.
| Series | Formula | Example |
|---|---|---|
| Sum 1 to n | n*(n+1)/2 | 1+2+…+100 = 5050 |
| Sum of squares | n*(n+1)*(2n+1)/6 | 1²+2²+…+n² |
| Sum of cubes | [n*(n+1)/2]² | (1+2+…+n)² |
| Geometric series (r≠1) | a*(rⁿ-1)/(r-1) | 1+2+4+8+…+2^(n-1) = 2ⁿ-1 |
| Count divisors of n | Loop to √n, add pairs | 12 → {1,2,3,4,6,12} → 6 divisors |
| Sum of divisors | Loop to √n, sum d and n/d | 12 → 1+2+3+4+6+12 = 28 |
| Number of digits in n | floor(log10(n))+1 | digits(1000) = 4 |
| Triangular numbers | n*(n+1)/2 | 1,3,6,10,15,21... |
| Catalan numbers | C(2n,n)/(n+1) | 1,1,2,5,14,42... (balanced parens) |
Signal 1: Contiguous Segments. "Find the longest/shortest subarray or substring." A sliding window natively represents a contiguous segment.
Signal 2: Monotonicity. Adding an element strictly increases the condition (e.g., sum of positive numbers). Removing an element strictly decreases it. This guarantees we don't have to test every window.
Signal 3: O(n²) is too slow. You see constraints like N = 10⁵ and a brute-force nested loop is timing out.
Given array of positive integers and a target sum S, find if there exists a contiguous subarray with sum equal to S.
Observation: All elements are positive. This means: expanding the window (moving right) always increases the sum. Shrinking the window (moving left forward) always decreases the sum.
Therefore: If sum < S → expand (move right pointer). If sum > S → shrink (move left pointer). If sum == S → found it. Each pointer moves at most n steps → O(n) total.
Bit manipulation is your go-to when: the problem involves sets (subsets, membership), powers of 2, toggling states (on/off), the constraints are very tight (O(1) space needed), or you spot that XOR cancels pairs. The key is learning to see problems as operations on binary representations.
| Bit Operation | What it does | When to use |
|---|---|---|
n & 1 | Check if odd (last bit) | Parity check, odd/even |
n & (n-1) | Turn off rightmost set bit | Check power of 2, count bits |
n | (1<<i) | Set bit i | Turn on position i |
n & ~(1<<i) | Clear bit i | Turn off position i |
n ^ (1<<i) | Toggle bit i | Flip position i |
a ^ a = 0 | XOR self = zero | Find unpaired element |
a ^ 0 = a | XOR with 0 = identity | XOR trick for missing numbers |
n << k | Multiply by 2^k | Fast multiply/divide by powers of 2 |
A greedy algorithm is correct when making the locally optimal choice at each step never prevents a globally optimal solution. The classic proof technique: "exchange argument" — if you swap a greedy choice with any other choice, the result doesn't improve. If you can prove this, greedy is correct AND fast.
You have n intervals [start, end]. Find the minimum number of intervals to remove to make all remaining intervals non-overlapping.
Why end time? At each step, among all intervals that start after our last kept interval ends, we should keep the one that ends earliest. This leaves the maximum room for future intervals. Keeping the one that ends latest would "waste" more future space.
Algorithm: Sort by end time. Keep a "last end" pointer. Greedily include each interval if it starts at or after last end. Count excluded intervals.
Step 1: Solve with recursion first. Don't think about DP yet. Just write the recursive solution that expresses the answer in terms of smaller subproblems.
Step 2: Add memoization. Notice which recursive calls repeat. Cache their results. This is "top-down DP" and it's usually enough.
Step 3: Convert to bottom-up (tabulation). Fill the table from smaller to larger subproblems. Usually gives better constant factors and avoids stack overflow.
Step 4: Optimize space. If you only ever look at the previous row/state, you can compress the 2D table to 1D.
Longest Common Subsequence (LCS) of two strings. This is the classic 2D DP problem.
Any grid problem where you move between cells (up/down/left/right) is a graph. Cells are nodes, valid moves are edges. BFS finds shortest path. DFS finds connected regions (islands).
"Task A must complete before B" → directed edge A→B. Finding valid order = topological sort. Detecting impossible (circular dependency) = cycle detection.
BFS/DFS doesn't need a literal graph. States (board positions, configurations) are nodes, transitions are edges. Shortest path = fewest transitions to reach goal state.
| You Read / Notice | Think About | Start With | Concrete Example |
|---|---|---|---|
| "Find if exists / is possible" | Boolean logic, BFS/DFS, two pointers | Can you reduce to yes/no sub-question? | "Is there a path from A to B?" |
| "Minimum / maximum value" | Binary search on answer, greedy, DP | Is there a monotone property? | "Minimum days to ship all cargo." |
| "Count ways / number of X" | DP, combinatorics, inclusion-exclusion | Can I define dp[i] = count up to i? | "Ways to climb N stairs." |
| "All / every / enumerate" | Backtracking, bitmask | Decision tree: what choices exist at each step? | "Generate all valid parentheses." |
| "Contiguous subarray" | Sliding window, prefix sum, Kadane's | Try prefix sum first: sum[r]-sum[l] | "Max sum subarray of size K." |
| "Pair / triplet summing to X" | Sort + two pointers, hash map | Fix one element, find rest with two pointer | "3Sum problem." |
| "Sorted array / binary search" | Binary search variants | Lower bound? Upper bound? On answer? | "Find first occurrence of X." |
| "Grid / 2D movement" | BFS (shortest), DFS (reachability/area) | BFS if shortest path, DFS if just connectivity | "Number of Islands." |
| "Dependencies / ordering" | Topological sort, DAG DP | Build adjacency list, run Kahn's algorithm | "Course Schedule (prerequisites)." |
| "Overlapping subproblems" | Memoization → DP table | Define the state first: what uniquely identifies a subproblem? | "Longest Common Subsequence." |
| "Remove/add elements dynamically" | Heap, segment tree, BIT | Heap if only need max/min. SegTree for range ops. | "Running median of a data stream." |
| "Digits of a number" | Modular arithmetic, digit DP | Extract digits: while(n) { d=n%10; n/=10; } | "Sum of digits until single digit." |
| "Strings, character frequency" | Frequency array[26], sliding window | Build freq map in O(n), query O(1) | "Longest substring without repeats." |
| "Intervals / schedules" | Sort by start or end, greedy, sweep line | Sort by end for max non-overlapping. Sort by start for merge. | "Merge Overlapping Intervals." |
| "XOR, bit toggling, subset" | Bit manipulation | Draw small examples in binary. XOR for pairing/cancellation. | "Find the single non-repeating number." |
Get digits: while(n) { d=n%10; n/=10; }
Reverse digits: while(n) { rev=rev*10+n%10; n/=10; }
Digit count: to_string(n).length()
Prefix sum for range queries.
Sort + binary search for pair finding.
Two pointers on sorted arrays.
Hash map for O(1) membership check.
Frequency array for anagram/permutation.
Two pointers for palindrome.
Concatenate + Z-function for pattern matching.
Sort chars for canonical anagram key.
dp[i] = answer for first i elements.
dp[i][j] = answer for range [i,j].
dp[i][j] = answer using i items with j capacity.
dp[mask] = answer for subset mask.
n=0 → return 0 or empty.
n=1 → return the element itself.
l > r → return 0 (empty range).
visited → return (avoid infinite loop).
Problem has optimal substructure AND greedy choice property.
Often: sort first, then process linearly.
Exchange argument proves correctness.
No "undo" is needed.