THE RECURSION TREE
YOUR CALL
Twelve problems, and five facts underneath them. The operations budget that decides every complexity target, what your containers actually cost, and the two obligations every recursion owes you. Later decks re-derive these; this one settles them.
This is not a list of problems. It is 5 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDNothing. This is the first deck — every other one assumes what is here.
12 PROBLEMS · 11 LINK TO A JUDGE · THE REST ARE CONCEPTS THE DRILLS COVER
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Step 1 is not a topic so much as the set of things every later topic assumes. The statement tells you which one you need — and reading the constraint first is the habit that survives longest.
The input size alone usually fixes the complexity you are allowed.
Read the target off the ladder, then pickone second ≈ 10⁸ opsThe number is a sequence you peel with % 10 and / 10.
One while loop, two operatorsO(log₁₀ n)Divisors pair up around the square root, so half the range is free.
Loop to √n, take both of each pairO(√n)Replacing the larger by the remainder shrinks it fast.
Euclid: gcd(a,b) = gcd(b, a % b)O(log min(a,b))Name the base case and the thing that shrinks, before the body.
Base case + a strictly smaller stepO(depth) stackBounded keys want an array; arbitrary keys want a map.
Count once, then read the countsO(n) timeThis ladder is the reason the deck exists. Every other deck's CONSTRAINTS slide reads off the same figure — roughly 10⁸ operations a second — and this is where it is derived rather than assumed.
READ THE BOUND FIRST ⇒ THE COMPLEXITY FAMILY IS USUALLY DECIDED
Five facts, twelve problems, no lectures — this step has no harvested series, so each unit opens with its own drills. Unit 01 is the one the whole series leans on; the rest are the arithmetic and recursion habits everything else is written on top of.
Roughly how many simple operations can you expect a judge to run in one second?
About 10⁸, and that single number decides most of your design choices. It is a rule of thumb, not a guarantee — constant factors, cache behaviour and the language all move it — but it is accurate enough to rule things out before you write anything. At n = 10⁵ a quadratic solution is 10¹⁰ operations, a hundred times over budget; there is no point being clever about the constant factor. Every CONSTRAINTS slide in every deck of this series reads off this one figure, which is why it is the first thing here.
Which of these does an std::vector or Java ArrayList not give you in O(1)?
Inserting at the front is O(n) — every later element shifts up one. Indexing is a single address computation, size is stored, and appending is amortised O(1) because the buffer grows geometrically. Front insertion is the one that costs, and it is why a problem full of front-inserts wants a deque or a linked list instead. Knowing which operation on which container secretly walks the whole thing is half of choosing a data structure — Linked List (step 06) turns this into its opening question.
Given n ≤ 10⁷, which complexity is already too slow?
O(n²) on 10⁷ is 10¹⁴ — six orders of magnitude past the budget. O(n) is 10⁷ and O(n log n) about 2.3×10⁸, which is on the edge but usually survives. The gap between linear and quadratic is not a detail at this size; it is the difference between a solution and a timeout, and it is decided before you write a line.
A bound of n ≤ 20 is unusually small. What does that usually signal?
A tiny bound is permission to be exponential. At n = 20, 2ⁿ is about a million and n! is far too big, so the intended answer usually enumerates subsets — bitmask DP, or plain recursion over take/skip. Reading a small bound as 'brute force is allowed' is as useful as reading a large one as 'it is not'. Recursion (step 07) and Bit Manipulation (step 08) live here.
One second is roughly 10⁸ simple operations, and that single fact turns the input bound into a decision. n ≤ 5000 means n² is 25 million and fine while n³ is 1.25 trillion and hopeless — so the bound has already told you the shape of the intended solution before you have thought about the problem. Read it first, every time.
A bound stated before any algorithm is described — n ≤ 10⁵, n ≤ 20, 1 ≤ a,b ≤ 10⁹. It is not decoration: it is the problem telling you which family of solutions it will accept.
Assume roughly 10⁸ simple operations per second. Multiply out what each candidate complexity costs at the stated n and discard anything over budget. What survives is usually a single family, and you have narrowed the search before thinking about the problem at all.
// Not code to submit - the arithmetic you do in your head first. // One second buys roughly 1e8 simple operations. // // n <= 12 O(n!) 4.8e8 every permutation // n <= 25 O(2^n) 3.4e7 every subset // n <= 500 O(n^3) 1.25e8 triple loop, just about // n <= 5000 O(n^2) 2.5e7 double loop, comfortable // n <= 1e5 O(n log n) 1.7e6 sort or heap, free // n <= 1e7 O(n) 1e7 one pass // // At n = 1e5 a double loop is 1e10 - a hundred times over budget. // No constant-factor cleverness closes a gap that size.
// Not code to submit - the arithmetic you do in your head first. // One second buys roughly 1e8 simple operations. // // n <= 12 O(n!) 4.8e8 every permutation // n <= 25 O(2^n) 3.4e7 every subset // n <= 500 O(n^3) 1.25e8 triple loop, just about // n <= 5000 O(n^2) 2.5e7 double loop, comfortable // n <= 1e5 O(n log n) 1.7e6 sort or heap, free // n <= 1e7 O(n) 1e7 one pass // // At n = 1e5 a double loop is 1e10 - a hundred times over budget. // No constant-factor cleverness closes a gap that size.
# Not code to submit - the arithmetic you do in your head first. # One second buys roughly 1e8 simple operations. # # n <= 12 O(n!) 4.8e8 every permutation # n <= 25 O(2^n) 3.4e7 every subset # n <= 500 O(n^3) 1.25e8 triple loop, just about # n <= 5000 O(n^2) 2.5e7 double loop, comfortable # n <= 1e5 O(n log n) 1.7e6 sort or heap, free # n <= 1e7 O(n) 1e7 one pass # # Python is 10-50x slower than C++ on the same loop, so shift every # row down: a 1e7 pure-Python loop is already seconds, not one.
Reading the constraints after writing the solution. The bound is the cheapest information in the statement and the only piece available before you understand the problem. Skipping it means discovering at submission time that a correct algorithm was never fast enough — and correct-but-too-slow is the most expensive way to be right. The other half of the trap is treating 10⁸ as exact: it is an order of magnitude, so a 2× margin means nothing and a 100× margin is decisive.
Which pair of operations peels a number apart digit by digit?
n % 10 gives the last digit; n / 10 removes it. That pair, in a while (n > 0) loop, is the entire toolkit for counting digits, reversing a number, summing digits, checking Armstrong and testing palindromes. The loop runs once per digit, so everything here is O(log₁₀ n) — about 10 iterations for a 32-bit int, which is effectively constant.
Reversing 1534236469 as a 32-bit int overflows. What should the function return?
0 — LeetCode 7 defines it that way. The reversal of 1534236469 is 9646324351, past 2³¹−1. Signed overflow in C++ is undefined behaviour, so you cannot detect it after the fact: check before each multiply, or accumulate in a 64-bit type and compare. This is the same guard atoi needs in Strings (step 05) and the same reason Arrays 2 carries a long long in 4Sum.
n % 10 reads the last digit and n / 10 removes it, and those two lines are the entire technique — no string conversion anywhere. The loop runs once per digit, about log₁₀(n) times, which is why digit problems stay cheap even on huge numbers. The chain on the left is a loop, drawn as what a loop is: a recursion that never branches.
“How many digits” — or anything that walks a number rather than a container. The number is the sequence; you just need the two operators that read and drop its last digit.
n % 10 is the last digit and n / 10 removes it, so a while (n > 0) loop visits every digit exactly once. Counting them is one increment per turn. The loop runs ⌊log₁₀ n⌋ + 1 times — about 10 for a 32-bit int.
// n % 10 reads the last digit, n / 10 drops it. int countDigits(int n) { if (n == 0) return 1; // the loop would return 0 int count = 0; while (n > 0) { count++; n /= 10; } return count; }
// n % 10 reads the last digit, n / 10 drops it. public int countDigits(int n) { if (n == 0) return 1; // the loop would return 0 int count = 0; while (n > 0) { count++; n /= 10; } return count; }
# n % 10 reads the last digit, n // 10 drops it. def count_digits(n): if n == 0: return 1 # the loop would return 0 count = 0 while n > 0: count += 1 n //= 10 return count
Forgetting n == 0. Zero has one digit, but while (n > 0) never runs and you return 0. Negative input needs a decision too — take the absolute value, or state that the domain is non-negative. The log₁₀ shortcut is tempting but floating-point rounding makes it wrong on exact powers of ten, which is precisely where a test will look.
“Reverse the digits” of a signed 32-bit integer, with an explicit rule for what to do when the result does not fit. The overflow clause is the actual problem.
Peel digits off the right of n and push them onto the right of rev: rev = rev * 10 + n % 10. The only difficulty is that rev can exceed the range mid-way, and in C++ signed overflow is undefined — so you must test before the multiply, not after.
// Check BEFORE the multiply: signed overflow is undefined behaviour, // so you cannot detect it by looking at the result afterwards. int reverse(int n) { int rev = 0; while (n != 0) { int digit = n % 10; if (rev > INT_MAX / 10) return 0; if (rev < INT_MIN / 10) return 0; rev = rev * 10 + digit; n /= 10; } return rev; }
// Java's int wraps rather than being undefined, but the contract still // says return 0 - so test before the multiply either way. public int reverse(int n) { int rev = 0; while (n != 0) { int digit = n % 10; if (rev > Integer.MAX_VALUE / 10) return 0; if (rev < Integer.MIN_VALUE / 10) return 0; rev = rev * 10 + digit; n /= 10; } return rev; }
# Python ints do not overflow, so the bound must be applied by hand. def reverse(n): sign = -1 if n < 0 else 1 n, rev = abs(n), 0 while n: rev = rev * 10 + n % 10 n //= 10 rev *= sign return 0 if rev < -2**31 or rev > 2**31 - 1 else rev
Detecting the overflow after it has happened. In C++ that is undefined behaviour — the compiler may assume it cannot occur and delete your check. Test against INT_MAX / 10 before multiplying, or accumulate in a 64-bit type. Note also that n % 10 in C++ keeps the sign of n, so negatives reverse correctly without special handling; in Python -7 % 10 is 3, which quietly breaks the same code.
“Is this number a palindrome” — read the same forwards and backwards. Negative numbers are conventionally not palindromes, because of the leading minus.
Reverse the number and compare, or better: reverse only half of it. Peel digits off the back into rev until rev ≥ n; at that point they have met in the middle and you compare. Half the work, and no overflow is possible because rev never exceeds n.
// Reverse only HALF: they meet in the middle, so no overflow is possible. bool isPalindrome(int n) { if (n < 0) return false; // the minus sign breaks symmetry int rev = 0; while (n > rev) { // stop once they cross rev = rev * 10 + n % 10; n /= 10; } return n == rev || n == rev / 10; // even length, or odd (shared middle) }
// Reverse only HALF: they meet in the middle, so no overflow is possible. public boolean isPalindrome(int n) { if (n < 0) return false; // the minus sign breaks symmetry int rev = 0; while (n > rev) { // stop once they cross rev = rev * 10 + n % 10; n /= 10; } return n == rev || n == rev / 10; // even length, or odd (shared middle) }
# Reverse only half: they meet in the middle. def is_palindrome(n): if n < 0: return False # the minus sign breaks symmetry rev = 0 while n > rev: # stop once they cross rev = rev * 10 + n % 10 n //= 10 return n == rev or n == rev // 10 # even length, or odd
The odd-length case. When the digit count is odd the loop leaves the middle digit in rev, so n == rev fails and you need n == rev / 10 as well. Testing only the even case passes 1221 and fails 121 — a bug that survives casual testing. Trailing zeros are the other trap: any number ending in 0 (other than 0 itself) cannot be a palindrome, and the half-reversal handles that for free.
“Armstrong number” — the sum of each digit raised to the power of the digit count equals the number. 153 = 1³ + 5³ + 3³.
Two passes over the digits. The first counts how many there are, because the exponent depends on it. The second raises each digit to that power and accumulates. Compare the total to the original — which you must have saved, since the loop destroys n.
// The exponent is the DIGIT COUNT, so count first, then accumulate. bool isArmstrong(int n) { int k = 0, t = n; while (t > 0) { k++; t /= 10; } // pass 1: how many digits int sum = 0; t = n; while (t > 0) { // pass 2: each digit ^ k int d = t % 10, p = 1; for (int i = 0; i < k; i++) p *= d; sum += p; t /= 10; } return sum == n; // n itself was never modified }
// The exponent is the DIGIT COUNT, so count first, then accumulate. public boolean isArmstrong(int n) { int k = 0, t = n; while (t > 0) { k++; t /= 10; } // pass 1: how many digits int sum = 0; t = n; while (t > 0) { // pass 2: each digit ^ k int d = t % 10, p = 1; for (int i = 0; i < k; i++) p *= d; sum += p; t /= 10; } return sum == n; // n itself was never modified }
# The exponent is the digit count, so count first, then accumulate. def is_armstrong(n): k = len(str(n)) # pass 1: how many digits total, t = 0, n while t > 0: # pass 2: each digit ** k total += (t % 10) ** k t //= 10 return total == n # n itself was never modified
Destroying n before you can compare against it. The digit loop consumes the number, so copy it first — forgetting to is the most common failure here, and it returns false for every input including genuine Armstrong numbers. The second trap is hard-coding the exponent as 3: that is only correct for three-digit numbers, and it silently passes 153 while failing 9474.
Why does a divisor search only need to run to √n?
Every divisor d below √n has a partner n/d above it. So walking to √n and recording both members of each pair finds all of them — O(√n) instead of O(n). Take care with perfect squares, where d and n/d are the same number and must not be counted twice. The same pairing is why primality only needs to test to √n: a composite must have a factor at or below it.
Euclid on gcd(48, 18). What is the sequence of pairs?
Replace the larger with the remainder: gcd(a,b) = gcd(b, a % b). 48 % 18 = 12, then 18 % 12 = 6, then 12 % 6 = 0 — and when the remainder hits 0 the other number is the answer, 6. It converges in O(log min(a,b)) steps, far faster than testing every candidate downward. Once you have the GCD, lcm(a,b) = a / gcd × b — divide before multiplying, or you overflow for no reason.
Divisors come in pairs: if i divides n then so does n/i, and the smaller of every pair is at most √n. So a scan that stops at the root has still seen all of them — each iteration reads two. That is O(√n) instead of O(n) without losing a single divisor, and the only care needed is not counting √n twice.
“Print all divisors” / “all factors”. The naive loop to n is O(n); the pairing observation makes it O(√n), which is the point of the unit.
Divisors come in pairs: if d divides n then so does n/d, and one of the two is always ≤ √n. So loop i from 1 to √n and, on each hit, record both i and n/i. A perfect square has i == n/i at the root and must not be recorded twice.
// Divisors pair as (i, n/i), and one of each pair is <= sqrt(n). vector<int> divisors(int n) { vector<int> out; for (int i = 1; (long long)i * i <= n; i++) { // i*i, not sqrt() if (n % i != 0) continue; out.push_back(i); if (i != n / i) out.push_back(n / i); // a square would repeat } sort(out.begin(), out.end()); return out; }
// Divisors pair as (i, n/i), and one of each pair is <= sqrt(n). public List<Integer> divisors(int n) { List<Integer> out = new ArrayList<>(); for (int i = 1; (long) i * i <= n; i++) { // i*i, not Math.sqrt() if (n % i != 0) continue; out.add(i); if (i != n / i) out.add(n / i); // a square would repeat } Collections.sort(out); return out; }
# Divisors pair as (i, n // i), and one of each pair is <= sqrt(n). def divisors(n): out = [] i = 1 while i * i <= n: # i*i, not math.sqrt if n % i == 0: out.append(i) if i != n // i: # a square would repeat out.append(n // i) i += 1 return sorted(out)
Double-counting the root of a perfect square. For n = 36, i = 6 gives n/i = 6 — record it once. The other trap is the loop bound: i <= sqrt(n) using a floating-point sqrt can round down and miss the root entirely on exact squares. i*i <= n in integer arithmetic is exact, and needs a widening cast so the square itself does not overflow.
“Is it prime”. The same square-root pairing as divisors, used to stop early: a composite number must have a factor at or below its square root.
If n has any divisor other than 1 and itself, the smaller member of that pair is ≤ √n. So testing i from 2 to √n is sufficient — no hit means prime. Handle n < 2 first: 0 and 1 are not prime, and neither are negatives.
// A composite must have a factor <= sqrt(n), so stop there. bool isPrime(int n) { if (n < 2) return false; // 0, 1 and negatives are not prime for (int i = 2; (long long)i * i <= n; i++) if (n % i == 0) return false; // found a factor return true; }
// A composite must have a factor <= sqrt(n), so stop there. public boolean isPrime(int n) { if (n < 2) return false; // 0, 1 and negatives are not prime for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false; // found a factor return true; }
# A composite must have a factor <= sqrt(n), so stop there. def is_prime(n): if n < 2: return False # 0, 1 and negatives are not prime i = 2 while i * i <= n: if n % i == 0: return False # found a factor i += 1 return True
Forgetting that 1 is not prime. A loop from 2 to √1 never runs, so the naive version returns true for 1 — and for 0, and for negatives. Guard n < 2 first. If you need primality for many numbers rather than one, stop reaching for this: a sieve marks every prime below n in O(n log log n), which Bit Manipulation (step 08) covers.
“GCD” / “HCF” / “reduce this fraction” / “LCM”. Anything about shared structure between two numbers ends at Euclid's algorithm.
Any common divisor of a and b also divides a % b, so the pair (a, b) can be replaced by (b, a % b) without changing the answer. The second number shrinks fast — logarithmically — and when it reaches 0 the other is the GCD.
// gcd(a,b) = gcd(b, a % b); the remainder shrinks logarithmically. int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; // b hit 0, so a is the answer } long long lcm(int a, int b) { return (long long)a / gcd(a, b) * b; // DIVIDE first, then multiply }
// gcd(a,b) = gcd(b, a % b); the remainder shrinks logarithmically. public int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; // b hit 0, so a is the answer } public long lcm(int a, int b) { return (long) a / gcd(a, b) * b; // DIVIDE first, then multiply }
# gcd(a, b) = gcd(b, a % b); the remainder shrinks logarithmically. def gcd(a, b): while b: a, b = b, a % b return a # b hit 0, so a is the answer def lcm(a, b): return a // gcd(a, b) * b # divide first (habit; Python won't overflow)
Computing a * b / gcd for the LCM. The product overflows long before the quotient would — two numbers near 10⁹ multiply to 10¹⁸. Divide first: a / gcd * b is exact because the GCD divides a. The other trap is the base case direction: gcd(a, 0) is a, not 0, and writing the loop condition as while (a != 0) returns the wrong variable.
What two things must every recursive function have to terminate correctly?
A base case that returns without recursing, and a step that provably moves toward it. The base case is where the recursion stops; the step is what guarantees it is reached — a smaller n, a larger index, a shorter remaining target. Write both down before the body. Recursion (step 07) and every tree and graph traversal after it are this pattern with a different shrinking quantity.
Naive recursive Fibonacci on n = 40 is slow. Where does the time go?
The call tree is exponential because subproblems repeat. fib(38) is computed twice, fib(37) three times, and so on — roughly 1.6ⁿ calls in total. Depth 40 is nothing; the branching is the problem. Caching each answer once collapses it to O(n), which is the entire idea of Dynamic Programming (step 16). This one function is the bridge between recursion and DP, which is why it sits here.
This is the whole of recursion on one screen. fact(5) cannot multiply anything until it knows fact(4), which waits on fact(3) … so the descent only stacks frames — five of them — and computes nothing. At n = 0 the base case returns 1 without recursing, and only then does the work start: each frame multiplies by its own n on the way back up. Watch the CALL STACK grow to full depth before a single number appears. The two things every recursion owes you are both here — a base case that returns without recursing, and a step (n → n−1) that strictly shrinks toward it. Drop either and you get infinite descent, not a wrong answer.
Same two obligations, one difference: each call spawns two children instead of one. That is the entire change, and it turns the factorial ladder into a tree that recomputes. Follow the times called counter: fib(3) is built from scratch twice, fib(2) three times, fib(1) five times — none of them remembering the last one. The shape is why naive Fibonacci is O(2ⁿ) while factorial is O(n), despite the two functions looking almost identical. It is also the cheapest possible motivation for memoisation: cache each n and every duplicate subtree collapses to one lookup.
“Do it recursively” on something with an obvious smaller version of itself. Factorial is the smallest honest example: n! = n × (n−1)!.
The recurrence is the code. fact(n) returns n * fact(n-1), and fact(0) returns 1 without recursing. That is both obligations satisfied: a base case, and a step that reduces n by one every call, so the base case is always reached.
// Base case that returns without recursing, and a step that shrinks. long long fact(int n) { if (n <= 1) return 1; // BASE: stops the recursion return (long long)n * fact(n - 1); // STEP: n-1 always approaches it } // 21! overflows a signed 64-bit integer, so the domain is n <= 20.
// Base case that returns without recursing, and a step that shrinks. public long fact(int n) { if (n <= 1) return 1; // BASE: stops the recursion return (long) n * fact(n - 1); // STEP: n-1 always approaches it } // 21! overflows a signed 64-bit long, so the domain is n <= 20.
# Base case that returns without recursing, and a step that shrinks. def fact(n): if n <= 1: return 1 # BASE: stops the recursion return n * fact(n - 1) # STEP: n-1 always approaches it # Python ints are unbounded, but the default recursion limit is ~1000.
A base case the step can step over. Writing if (n == 1) instead of n <= 1 means fact(0) recurses to fact(-1) and onward until the stack dies. Whenever the base case is an equality, ask what happens if the argument starts below it. The second trap is overflow: the recursion is correct long past the point the return type can hold the answer.
“Reverse it recursively” / “in place, without a second array”. The shrinking quantity is the gap between two indices, not a count.
Swap the outermost pair, then solve the same problem on the inside: reverse(l+1, r-1). The base case is l >= r — zero or one element left, which is already reversed. Each call closes the gap by two, so it terminates in n/2 levels.
// The shrinking quantity is the GAP between l and r, not a count. void reverse(vector<int>& a, int l, int r) { if (l >= r) return; // BASE: 0 or 1 element is reversed swap(a[l], a[r]); reverse(a, l + 1, r - 1); // STEP: the gap closes by two }
// The shrinking quantity is the GAP between l and r, not a count. void reverse(int[] a, int l, int r) { if (l >= r) return; // BASE: 0 or 1 element is reversed int t = a[l]; a[l] = a[r]; a[r] = t; reverse(a, l + 1, r - 1); // STEP: the gap closes by two }
# The shrinking quantity is the gap between l and r, not a count. def reverse(a, l, r): if l >= r: return # BASE: 0 or 1 element is reversed a[l], a[r] = a[r], a[l] reverse(a, l + 1, r - 1) # STEP: the gap closes by two
Using l == r as the base case. That catches odd-length arrays, where the pointers land on the same index, but even-length ones cross without ever being equal — l becomes greater than r and the recursion runs past the ends. l >= r covers both. This is the same even/odd oversight that breaks centre-expansion in Strings (step 05).
“Fibonacci” — or any recurrence with two recursive calls whose arguments overlap. It is the bridge from recursion to dynamic programming, and the reason DP exists.
fib(n) = fib(n-1) + fib(n-2) is correct and exponentially slow, because the two branches recompute the same subproblems. Caching each answer the first time collapses the call tree to a line: O(n). Keeping only the last two values drops the memory to O(1).
// The naive recursion is exponential because subproblems REPEAT. // Two variables carried forward is the same recurrence, computed once each. int fib(int n) { if (n < 2) return n; // fib(0)=0, fib(1)=1 int prev = 0, cur = 1; for (int i = 2; i <= n; i++) { int next = prev + cur; // the recurrence, bottom-up prev = cur; cur = next; } return cur; }
// The naive recursion is exponential because subproblems REPEAT. // Two variables carried forward is the same recurrence, computed once each. public int fib(int n) { if (n < 2) return n; // fib(0)=0, fib(1)=1 int prev = 0, cur = 1; for (int i = 2; i <= n; i++) { int next = prev + cur; // the recurrence, bottom-up prev = cur; cur = next; } return cur; }
# The naive recursion is exponential because subproblems repeat. # Two variables carried forward is the same recurrence, computed once each. def fib(n): if n < 2: return n # fib(0)=0, fib(1)=1 prev, cur = 0, 1 for _ in range(2, n + 1): prev, cur = cur, prev + cur # the recurrence, bottom-up return cur
Assuming the naive recursion is merely 'a bit slow'. It is O(1.6ⁿ): fib(40) is around 200 million calls and fib(50) is minutes. The depth is only n — the branching is what costs. Recognising repeated subproblems as the cause, rather than recursion itself, is exactly the observation Dynamic Programming (step 16) is built on.
You must count occurrences of values known to lie in 0 … 100. What do you reach for?
A plain array indexed by the value. For a bounded range it beats a hash map on every constant that matters — no hashing, no allocation, perfect cache behaviour — and two count tables can be compared with one loop. Reserve the map for genuinely unbounded keys: arbitrary integers, strings, pairs. Recognising the bound is what turns a map into an array, and an O(n log n) sort into an O(n) count. Strings (step 05) uses the 26-slot version of exactly this.
The values are arbitrary 32-bit integers instead. What changes?
A map, because a 2³²-slot array is 4 billion counters for maybe a thousand values. The array trick is not about arrays being fast; it is about the range being small enough to allocate. Once the keys are unbounded, the map's hashing overhead is the price of not allocating the universe. Sorting also works and costs O(n log n) with O(1) extra space — a real trade, not a worse answer, and worth naming when memory is the binding constraint.
The keys here are letters, so there are 26 of them and that is known before the scan begins. cnt[c - 'a']++ is one indexed write: no hash computed, no collision handled, nothing allocated. A map would return the same answer and do several times the work. Reach for the map when the key space is large, sparse, or not known up front — not by default.
“How many times does each element appear” — frequencies, duplicates, most common. The only real decision is which container holds the counts.
One pass increments a counter per element; a second pass reads them out. If the values are bounded — 0 … 100, lowercase letters, digits — a plain array indexed by the value is fastest and simplest. If they are arbitrary integers or strings, a hash map is the only option that does not allocate the universe.
// The container follows the VALUE RANGE, not the array length. // Bounded values: a plain array, no hashing at all. void countBounded(vector<int>& a, int K) { // values in 0..K-1 vector<int> count(K, 0); for (int v : a) count[v]++; for (int v = 0; v < K; v++) if (count[v]) cout << v << " -> " << count[v] << "\n"; } // Arbitrary values: a map, because a 2^32-slot array is not an option. void countAny(vector<int>& a) { unordered_map<int,int> count; for (int v : a) count[v]++; for (auto& [v, c] : count) cout << v << " -> " << c << "\n"; }
// The container follows the VALUE RANGE, not the array length. // Bounded values: a plain array, no hashing at all. void countBounded(int[] a, int K) { // values in 0..K-1 int[] count = new int[K]; for (int v : a) count[v]++; for (int v = 0; v < K; v++) if (count[v] != 0) System.out.println(v + " -> " + count[v]); } // Arbitrary values: a map, because a 2^32-slot array is not an option. void countAny(int[] a) { Map<Integer,Integer> count = new HashMap<>(); for (int v : a) count.merge(v, 1, Integer::sum); for (Map.Entry<Integer,Integer> e : count.entrySet()) System.out.println(e.getKey() + " -> " + e.getValue()); }
# The container follows the value range, not the list length. from collections import Counter def count_bounded(a, K): # values in 0..K-1 count = [0] * K for v in a: count[v] += 1 return {v: c for v, c in enumerate(count) if c} def count_any(a): return Counter(a) # a dict, for arbitrary keys
Sizing the counter array from the array length instead of the value range. vector<int> count(a.size()) is a buffer overrun the moment a value exceeds n, and it is the single most common bug in this family. Size it from the stated value bound. Reaching for a map when the range is small is the milder mistake — correct, but paying hashing costs and cache misses for nothing.
A problem gives n ≤ 10⁵ and asks for something over every pair of elements. What does the bound tell you before you have any idea how?
All pairs is 10¹⁰ — out by two orders of magnitude. So whatever the answer is, it does not enumerate pairs: it sorts, or hashes, or slides a window, or binary-searches. You know that before you know the algorithm, which is the whole point of reading constraints first. Two Sum (Arrays 1), 3Sum (Arrays 2) and every sliding-window problem in step 10 are this observation applied.
You write a recursion and it overflows the stack on valid input. Which obligation did it almost certainly break?
Usually the step, not the missing base case. A completely absent base case is easy to spot; the subtle failure is a step that shrinks on most paths but not all — an index that fails to advance when a branch is skipped, or f(n) calling f(n) in one condition. The base case is then perfectly correct and simply never reached. Name both obligations out loud before you write the body, and say which quantity shrinks.
None of these crash. Each one returns a wrong answer that looks right on the sample input — which is what makes them worth memorising rather than rediscovering.
The bound is the cheapest information in the statement and the only part you can use before you understand the problem. Skipping it means finding out at submission time that a correct algorithm was never fast enough.
It is an order of magnitude. A 2× margin tells you nothing — constant factors, cache behaviour and the language move it more than that. A 100× margin is decisive, and that is the only kind of judgement it supports.
if (n == 1) misses n = 0, and l == r misses even-length arrays whose pointers cross without meeting. Whenever the base case is an equality, ask what happens if the argument starts on the wrong side of it.
The digit loop consumes n. Armstrong and palindrome checks both need the original afterwards, so copy it first — forgetting to returns false for every input, including the true ones.
The product overflows long before the quotient would. Divide first: a / gcd * b is exact, because the GCD divides a by definition.
count(a.size()) overruns the moment a value exceeds n. The array is indexed by VALUE, so it must be sized from the value range — and if that range is unbounded, it has to be a map.
One screen, five facts. This is the slide to reopen before any other deck, because every other deck assumes it.
Twelve problems, and underneath them one number: about 10⁸ operations a second. Everything after this — every complexity target, every 'is this fast enough', every CONSTRAINTS slide in the series — reads off it.
No lectures in this step: Striver's A2Z has no harvested playlist for step 1, so the intros and drills carry it.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.