How to Approach Any Problem

The previous three sections gave us a definition of algorithm, the machinery of asymptotic analysis, and the discipline of abstraction. This section is the capstone: a methodology for attacking any algorithmic problem — homework, an interview, an on-call incident, a research notebook. You are about to read the same playbook used by Olympiad finalists, FAANG interviewers, ICPC coaches, and Site Reliability Engineers running an outage. The technical content of this book is the vocabulary; this section is the grammar.

The Polya Framework: Four Phases

In 1945 the Hungarian mathematician George Polya published How to Solve It, a slim book that distilled the problem-solving process into four phases. It was written for high-school geometry but holds up unreasonably well for modern algorithm design. The four phases, in order, are:

Most beginners spend 5% on phase 1, 10% on phase 2, 80% on phase 3, and 5% on phase 4. Most experts invert this: roughly 30 / 40 / 20 / 10. They write less code because they think harder before writing. The cost of a bug found in phase 1 is a corrected sentence; the cost of a bug found in phase 3 is a debugging session; the cost of a bug found in phase 4 is sometimes a postmortem. Every minute spent in the upper phases pays compound interest.

Phase 1 — Understand the Problem

The single most common interview failure mode — and the single most common production bug — is solving the wrong problem. Understand-the-problem is not optional warm-up; it is half the work.

Restate it in your own words

Read the problem. Now close it and write down what it asks in one sentence, without using any of the original wording. If you cannot do this, you do not yet understand the problem. This is the engineering analogue of the Feynman technique.

Pin down the contract

An algorithm is a contract. You owe the spec: given input of type T_in satisfying constraint C, return output of type T_out satisfying relation R. Until you can fill in those four slots, you cannot start.

Run small examples by hand

Take the smallest non-trivial input you can imagine, simulate the problem on paper, and check that your interpretation of the spec matches the expected output. If you cannot produce the expected output by hand, you cannot produce it in code.

Hunt edge cases

Edge cases are not bugs to fix later; they are part of the specification. Name them now, in writing.

• Empty input ($n = 0$).
• Single element ($n = 1$).
• All elements identical.
• Already sorted / reverse sorted.
• Negatives, zero, max int, min int.
• Duplicates of the target.
• No solution exists.
• Multiple solutions exist (which one to return?).
• Numerical: overflow at $(\text{lo} + \text{hi})/2$ on 32-bit. Famous binary-search bug fixed in Java's standard library in 2006, present in textbooks since 1962.

Phase 2 — Plan an Approach

With the spec pinned, the second phase is a deliberate, structured search through algorithm design. Three moves, in order.

Move 1: brute force first

Always have a baseline. Brute force is what you would do with infinite time and unbounded compute — try every pair, enumerate every permutation, simulate every step. Two reasons to write it down:

1. It anchors correctness. The brute force is almost always trivially correct and gives you something to test against.
2. It exposes the structure to optimize. Looking at "for every i, for every j, check sum" tells you exactly what you must remove.

Move 2: spot the structure

Real algorithm design is not invention; it is recognition. The same twenty patterns cover an astonishingly large fraction of problems. The question to ask is: what hidden structure does the input have, and what algorithmic technique exploits it?

Move 3: estimate complexity from the constraints

Constraints leak the intended complexity. If you see $n \leq 2 \times 10^5$, an $O(n^2)$ solution will time out and the setter is hinting at $O(n \log n)$. If you see $n \leq 20$, the setter is winking at bitmask DP. The next table is the practical heuristic that competitive programmers carry in their heads.

The Constraint-to-Complexity Table

Assume a generous one billion ($10^9$) simple operations per second — a healthy ceiling for compiled languages, an optimistic one for Python. With a one-second budget, the following complexity classes fit within these input sizes:

Read this table backward as well. If the only algorithm you know is quadratic and the constraint is $n = 10^6$, do not start coding — you are guaranteed to time out. Stop, return to phase 2, and find a better technique. The constraints are the problem author telling you what class of solution they expect.

Pattern Recognition: A Working Catalogue

Phase 2 is largely pattern recognition. The cue in the problem statement maps to the technique. After your first hundred problems the mapping becomes unconscious; until then, this catalogue is your cheat-sheet. Read the "cue" column with care — these are the verbal patterns that should fire your alarm.

Phase 3 — Execute the Plan

With a plan in hand, execution is mostly transcription. The pitfalls are mechanical, not intellectual.

• Off-by-one. Half-open vs. closed intervals. Decide once: do you use [lo, hi) or [lo, hi]? Be consistent for the whole function.
• Mutation while iterating. Modifying a list while looping over it is a guaranteed bug in Python and a footgun in JS.
• Integer overflow. In Java/C++ the midpoint (lo + hi) / 2 overflows for $\text{lo} + \text{hi} > 2^{31}$. The fix is lo + (hi - lo) / 2. Python ints are unbounded so this bug is invisible there.
• Hash collisions on adversarial inputs. Some competitive judges deliberately construct inputs that blow up Python's default dict hashing. Wrapping keys with a random salt fixes it.
• Recursion depth. Python defaults to 1000. A backtracking on a 10000-node tree will RecursionError — raise the limit or convert to a stack.
• Floating point. Never compare floats with ==; use a tolerance.

Worked Example: Two Sum in Python

Let us walk the entire Polya cycle on the canonical interview problem.

Two Sum. Given an array $A$ of integers and a target integer $t$, return indices $(i, j)$ with $i \neq j$ such that $A[i] + A[j] = t$. You may assume exactly one such pair exists.

Phase 1 (Understand). Input: an integer array, a target integer. Output: a pair of indices. Constraints, by clarification: lengths up to $10^5$; values fit in 32-bit; exactly one solution; the same index cannot be used twice. Edge cases: duplicates ($A = [3, 3], t = 6$ — the two 3s have different indices, so this is valid); negatives; zero target. Hand example: $A = [2, 7, 11, 15], t = 9$ → $(0, 1)$.

Phase 2 (Plan). Brute force: nested loop over all pairs, $O(n^2)$. At $n = 10^5$ that is $10^{10}$ operations — too slow. Improvement: for each $x = A[i]$, the partner we need is $t - x$. Looking up "have we seen $t - x$ already?" in a hash map is $O(1)$. So one pass suffices: $O(n)$ time, $O(n)$ space.

Phase 3 (Execute).

After one step on A = [2,7,11,15]: seen = {2: 0}.

Iteration order on [2,7,11,15]: (0,2), (1,7), (2,11), (3,15).

i = 1, x = 7, t = 9 -> need = 9 - 7 = 2.

seen = {2: 0}. need = 2 is in seen — hit!

seen[2] = 0, i = 1 -> return (0, 1). Verify: A[0] + A[1] = 2 + 7 = 9 = t.

After i = 0: seen = {2: 0}. After i = 1 we would write seen[7] = 1, but we already returned.

1from typing import List, Tuple
2
3def two_sum(A: List[int], t: int) -> Tuple[int, int]:
4    """Indices (i, j) with A[i] + A[j] == t, i != j."""
5    seen: dict[int, int] = {}             # value -> index seen so far
6    for i, x in enumerate(A):
7        need = t - x                      # the partner we are looking for
8        if need in seen:                  # has it appeared earlier?
9            return (seen[need], i)        # found: indices in left-to-right order
10        seen[x] = i                       # otherwise remember x for the future
11    raise ValueError("no two-sum pair")   # spec says this never fires
12
13
14# Worked example
15print(two_sum([2, 7, 11, 15], 9))   # -> (0, 1)
16print(two_sum([3, 2, 4], 6))        # -> (1, 2)
17print(two_sum([3, 3], 6))           # -> (0, 1) — duplicate-aware

Two Sum in TypeScript

The same algorithm in TypeScript. Notice that the algorithmic content is identical — only the syntax and the choice of Map over dict changes.

After one step on [2,7,11,15]: seen = Map(1) { 2 => 0 }.

Iteration order on [2,7,11,15]: i = 0,1,2,3.

i = 1 -> x = A[1] = 7.

x = 7, t = 9 -> need = 2.

seen.has(2) on { 2 => 0 } -> true.

seen.get(2) = 0, i = 1 -> [0, 1].

seen.set(7, 1) -> Map { 2 => 0, 7 => 1 }.

1function twoSum(A: number[], t: number): [number, number] {
2  // Map<value, index>: average O(1) get/set, ordered insertion.
3  const seen = new Map<number, number>();
4
5  for (let i = 0; i < A.length; i++) {
6    const x = A[i];
7    const need = t - x;
8
9    if (seen.has(need)) {
10      // Non-null assertion: has(need) guarantees get(need) is defined.
11      return [seen.get(need)!, i];
12    }
13    seen.set(x, i);
14  }
15
16  throw new Error("no two-sum pair");
17}
18
19console.log(twoSum([2, 7, 11, 15], 9));  // -> [0, 1]
20console.log(twoSum([3, 2, 4], 6));        // -> [1, 2]
21console.log(twoSum([3, 3], 6));           // -> [0, 1]

Phase 4 — Reflect

Most students stop at "it passes the examples." The fourth phase is what separates engineers from coders. Five questions, in order:

1. Does it handle every edge case I listed in phase 1? Empty input, single element, duplicates, negatives, max int, no solution. Run them.
2. What is the loop invariant? For Two Sum: at the top of iteration $i$, seen contains exactly {A[k]: k} for $0 \leq k < i$, and no answer has been found among $A[0..i-1]$. Combined with the loop's exit (we return as soon as a partner is found), this implies correctness.
3. What is the Big-O? Two Sum is $O(n)$ time, $O(n)$ space — one pass, one hash entry per element in the worst case.
4. Could it be simpler? Faster? Less memory? Faster: no — we must read every element, so $\Omega(n)$ is a lower bound. Less memory: if the input is sorted, we can use two pointers from the ends and drop the hash map — $O(1)$ extra space, still $O(n)$ time. That is a different algorithm for a different precondition.
5. What does the solution generalize to? The pattern "hash the complement" generalizes to: for any predicate over pairs that decomposes into independent functions of each element, replace nested loops with one pass + a hash lookup. 4-Sum, count-of-pairs-with-difference-K, subarray sum equals K — all the same idea.

Interactive: The Problem-Solving Cockpit

The widget below ties the four phases to a live trace and a complexity meter. The left column lets you flip between phases and see the checklist for each. The middle column steps through the Two Sum algorithm on $A = [2, 7, 11, 15], t = 9$: watch the hash map fill, watch the hit fire on iteration 1. The right column lets you slide $n$ across nine orders of magnitude and see how $O(n)$, $O(n \log n)$, and $O(n^2)$ diverge in absolute time.

Two things to look for. First, slide $n$ from $10$ to $10^9$: at the small end every algorithm is instant; somewhere around $n = 10^4$ the quadratic class crosses one millisecond; by $n = 10^6$ the quadratic class is many minutes; by $n = 10^9$ the quadratic class is centuries. The asymptotic class is not academic — it is the difference between "ships" and "does not ship."

Second, step through the Two Sum trace. On iteration $i = 0$, the hash map is empty so the lookup misses; we store $(2, 0)$. On iteration $i = 1$, we look up $9 - 7 = 2$, find it at index $0$, and return immediately. The whole algorithm visits each element at most once, exactly as the loop invariant predicts.

Debugging Strategies

Even the best methodology produces buggy code on the first attempt. These are the techniques senior engineers use, in roughly the order they reach for them.

1. Print invariants, not values

Beginners print the value of every variable. Experts print the invariant: a single line per iteration that says "here is what should be true right now." If the invariant prints false, you have found the bug.

1# Beginner debugging
2print("i =", i, "x =", x, "seen =", seen)
3
4# Expert debugging — print the invariant
5assert all(seen[A[k]] == k for k in range(i)), \
6    f"invariant violated at i={i}, seen={seen}"

2. Binary-search the bug

If you have a 200-line function and one of them is wrong, do not re-read the file. Comment out the second half and re-run; if the bug is gone, the bug is in the second half. Repeat. Five rounds of binary search localizes the bug to a single line.

3. Minimize the failing input

A failure on a 10,000-element array is unreadable. Find the smallest input that still fails. Halve, quarter, eighth — usually a 2-element input reproduces the bug. The minimal input is also the regression test you commit.

4. Rubber-duck

Explain the code, line by line, to an inanimate object. The act of verbalizing what each line is supposed to do surfaces the gap between intent and implementation. The duck has been a member of software engineering teams since at least 1986 (Brian Kernighan, The Practice of Programming).

5. Re-read the spec

After two failed debugging attempts, stop debugging. Go back to phase 1 and re-read the problem statement. Roughly half of all "impossible" bugs are in fact correct code solving the wrong problem.

Where This Methodology Lives

Polya's framework is not just for Olympiad problems. It is the same loop senior engineers use across every corner of computing.

Notice the universality of the four phases. The artefact at each phase changes — a clarifying question in an interview, a timeline in an outage, a derivation in a physics simulation — but the loop is the same. Spend time on phase 1, structure phase 2, execute carefully in phase 3, learn from the result in phase 4. The engineers who do this consistently are the engineers who ship.

From here, the rest of the book is fuel for phase 2. Every chapter introduces structures and algorithms; what makes them useful is the ability, in phase 2, to recognize when one of them is the right tool. That recognition is what we will build, problem by problem, for the next 14 chapters.