How to Solve Any Problem: The Method
Most people who fail algorithm problems do not fail because they lack knowledge. They fail because they have no procedure. They read the statement once, feel a flash of recognition ("this is a hash map thing"), start typing, hit an edge case they never considered, patch it, hit another, and run out of time with code that is half right and a mind that is fully panicked. The knowledge was there. The method was not.
This page is the method. It is eight steps, it fits on one printed page (the last section is that page), and it is the same procedure whether the problem is a 45-minute interview, a contest, or a performance bug in production code. Every later lesson in this course assumes you run it. The lesson on testing and debugging is step 7 of this method expanded to a full page; the complexity lesson is step 3 expanded.
Why this exists
A problem statement is a compressed description of a search space and a cost function. "Find the longest substring with at most k distinct characters" says: among all substrings, find the longest one satisfying a predicate. Nothing in that sentence tells you how to search efficiently. The method is a way of decompressing the sentence until the efficient search becomes visible.
The method is old. George Pólya's How to Solve It (1945) laid out four phases: understand the problem, devise a plan, carry out the plan, look back. Every "framework" taught since (UMPIRE, REACTO, the "Cracking the Coding Interview" seven steps) is Pólya with the phases subdivided for programming. What this page adds is the part Pólya could not: the signal-to-technique table, which exists because fifty years of algorithm research have produced a finite catalogue of techniques, and the phrasing of a problem leaks which one applies.
The method also exists because of a cognitive fact: under time pressure, working memory shrinks. An interview or a contest is exactly the situation where you cannot hold the whole problem in your head. The method externalises the process onto paper (or a shared editor) so that your working memory is free for the one hard step, which is almost always step 4, finding the bottleneck.
Where it shows up outside interviews: every performance investigation is this method. "The endpoint takes 12 seconds" is a problem statement. Clarify (which endpoint, which inputs, since when), find examples (a slow request, a fast one), name the brute force (what the code does now), find the bottleneck (profile), optimise (apply a known technique), code, test, communicate. Engineers who are good at production debugging and engineers who are good at algorithm problems are good at the same thing.
Pattern triggers: the signal → technique table
This is the table that turns a problem statement into a short list of candidate techniques. Read the statement, underline the literal phrases that match the left column, and you have your candidates for step 5. The right column links to the lesson where the technique is taught. The table is not exhaustive and the matches are not certainties: "sorted array" suggests binary search, but a sorted array with a pair-sum question wants two pointers. The table narrows; the bottleneck analysis in step 4 decides.
| Signal in the statement | Think of | Lesson |
|---|---|---|
| "sorted array", "find position of", "first/last occurrence" | Binary search | Sorting & Searching |
| "sorted array" + "pair / triplet with sum" | Two pointers from both ends | Two Pointers |
| "subarray" or "substring" with a constraint on its contents (sum, distinct count, at most k) | Sliding window | Sliding Window |
| "subarray sum equals k" with negatives allowed | Prefix sums + hash map | Prefix Sums |
| "range sum query", many queries, array static | Prefix sums; 2D prefix sums for grids | Prefix Sums |
| "range sum query" with point updates | Fenwick tree / segment tree | Advanced Data Structures |
| "range min/max query", array static | Sparse table; segment tree if updates | Advanced Data Structures |
| "k-th largest", "top k", "k most frequent" | Heap of size k; quickselect for a one-shot k-th | Heaps & Priority Queues |
| "median of a stream", "running median" | Two heaps | Heaps & Priority Queues |
| "merge k sorted lists / streams" | Heap keyed on the head of each list | Heaps & Priority Queues |
| "shortest path", unweighted or unit weights | BFS | Graphs |
| "shortest path", non-negative weights | Dijkstra | Graphs |
| "shortest path", negative weights, or "detect negative cycle" | Bellman-Ford / SPFA | Graphs |
| "dependencies", "prerequisites", "build order", "schedule tasks" | Topological sort (Kahn's BFS or DFS postorder) | Graphs |
| "connected components", "islands", "friend circles", "merge groups" | DFS/BFS flood fill; union-find when edges arrive online | Graphs |
| "minimum cost to connect all", "spanning" | Kruskal (union-find) or Prim (heap) | Greedy |
| "count the ways", "minimum cost" with a sequence of choices and overlapping subproblems | Dynamic programming | Dynamic Programming |
| "longest increasing / common subsequence", "edit distance" | Classic 1D/2D DP | Dynamic Programming |
| "all combinations / permutations / subsets", "generate every" | Backtracking (with pruning) | Backtracking & Recursion |
| "next greater / smaller element", "days until warmer", "largest rectangle" | Monotonic stack | Monotonic Stack & Deque |
| "maximum in every window of size k" | Monotonic deque | Monotonic Stack & Deque |
| "intervals", "meetings", "merge overlapping", "minimum rooms" | Sort by start, then sweep; heap of end times | Intervals |
| "parentheses", "brackets", "nested", "undo", "evaluate expression" | Stack | Stacks |
| "linked list middle", "cycle", "k-th from end" | Fast/slow pointers | Linked Lists |
| "find a duplicate in 1..n without extra memory" | Floyd's cycle finding on the index-as-pointer graph | Linked Lists |
| "grid", "paths from top-left", "minimum path sum" | Grid DP; BFS when the grid has obstacles and unit costs | Dynamic Programming |
| "minimise the maximum", "maximise the minimum", "smallest x such that feasible(x)" | Binary search on the answer | Sorting & Searching |
| "string matching", "find pattern in text", "repeated substring" | KMP, Z-function, rolling hash | String Algorithms |
| "palindrome", "longest palindromic substring" | Expand around centre; Manacher for | String Algorithms |
| "anagram", "same letters", "character frequency" | Counting array of size 26 / hash map of counts | Hash Tables |
| "have I seen this before", "two elements with property", "lookup by key" | Hash set / hash map | Hash Tables |
| "prefix of words", "autocomplete", "longest common prefix" | Trie | Trees |
| "XOR", "appears once while others appear twice", "subsets of a small set" | Bit manipulation | Bit Manipulation |
| "lowest common ancestor", "distance in a tree" | Binary lifting / Euler tour + RMQ | Trees |
| "k-th smallest in a BST", "inorder" | Inorder traversal; BST property | Trees |
| "choose locally best and never regret" (coins with canonical denominations, activity selection) | Greedy, with an exchange argument | Greedy |
| "probability", "expected number of", "random sampling from a stream" | Reservoir sampling, linearity of expectation | Probability for Engineers |
| or : bitmask over subsets | Bit Manipulation | |
| or "permutations" | backtracking is fine | Backtracking & Recursion |
| is fine (Floyd-Warshall, interval DP) | Complexity Analysis | |
| is fine; is borderline | Complexity Analysis | |
| to | : sort, heap, binary search, divide and conquer | Complexity Analysis |
| or | , possibly : one pass, counting, two pointers | Complexity Analysis |
| or : math, binary search, matrix exponentiation, digit DP | Complexity Analysis |
The constraint rows deserve a sentence. A compiled language performs very roughly simple operations per second on a judge; Python manages roughly . When a statement says , an solution does operations, which is a hundred seconds. The constraint is therefore not information about the data; it is the problem setter telling you the intended complexity class. Read it first.
Intuition & first principles
Three principles underlie the eight steps.
Brute force is not a failure; it is a measurement. The brute force solution is the fully decompressed problem statement: it enumerates the search space and evaluates the cost function on every candidate. Writing it down (not coding it, writing the idea) does two things. It confirms you understand what is being asked, since a brute force you cannot describe means a statement you have not understood. And it produces a number, the brute force complexity, which is the gap you must close. If the brute force is and the constraints demand , you know the shape of the optimisation: you need to remove two factors of , and that usually means removing an enumeration and replacing it with a lookup or a monotone pointer.
Every optimisation removes repeated work. When you go from to , the algorithm was computing something times that only needed computing once, or computing it from scratch when it could have been updated from the previous value. Finding the bottleneck means finding that repeated work and naming it: "I recompute the distinct-count of every substring from scratch, but adjacent substrings differ by one character." Once the waste is named, the fix is almost mechanical: maintain the quantity incrementally (sliding window, prefix sums), precompute it (hash map, sorted order), or prove that most candidates can be skipped (monotonicity, greedy exchange).
The data structure is chosen by the operation you keep needing. After naming the repeated work, you can usually state the operation your loop performs most often: "give me the smallest end time", "have I seen this prefix sum before", "what is the nearest larger element to the left". Each such sentence is the specification of a data structure. Smallest of a changing set is a heap. Membership is a hash set. Nearest larger to the left is a monotonic stack. You do not choose the data structure from a list of favourites; you derive it from the operation.
With these three ideas, the eight steps are not a ritual. They are the shortest path from a statement you do not understand to code you can defend.
Mechanics: the eight steps on a running example
The running example is longest substring with at most k distinct characters: given a string s and an integer k, return the length of the longest contiguous substring that contains at most k different characters. On s = "eceba", k = 2 the answer is 3 (the substring "ece"). This is LeetCode 340; the free variant with is Fruit Into Baskets (LeetCode 904).
flowchart TD
S1["1. Clarify<br/>inputs, outputs, constraints, assumptions"] --> S2["2. Examples<br/>normal, edge, adversarial — answers by hand"]
S2 --> S3["3. Brute force<br/>enumerate the search space, state complexity"]
S3 --> S4["4. Find the bottleneck<br/>what work is repeated?"]
S4 --> S5["5. Optimise<br/>signal table, invariant, data structure for the operation"]
S5 --> C{"Meets the<br/>constraint?"}
C -->|"no"| U["Get-unstuck tactics"]
U --> S4
C -->|"yes"| S6["6. Code<br/>edge cases first, helpers, plain names"]
S6 --> S7["7. Test<br/>trace one example, then edge cases, then complexity sanity"]
S7 --> B{"Bug?"}
B -->|"yes"| S6
B -->|"no"| S8["8. Communicate<br/>complexity, trade-offs, follow-ups"]
Step 1: Clarify
The goal of clarifying is to pin down the exact function you are implementing: its signature, its domain, and its output on the boundary of the domain. Interviewers under-specify on purpose; contest statements are complete but dense. Either way you extract the same facts.
The questions to ask, in order of how often they change the solution:
- What exactly is returned? The length, the substring itself, the start index, all maximal substrings? For the running example: the length only.
- What are the sizes? Length of
sup to? Range ofk? Assume and if nothing is said, and say that you are assuming it. The constraint fixes the target complexity ( or here). - What is the alphabet? Lowercase ASCII (26 symbols), full ASCII (128), or Unicode? This decides whether a fixed array of counts is legal or whether you need a hash map.
- Edge semantics. What does
k = 0return? (0: the empty substring is the only one with at most 0 distinct characters.) What does an emptysreturn? (0.) What ifkis at least the number of distinct characters ins? (The whole string, .) - Can the input be mutated? Is it a stream? Not for this problem, but ask whenever the input is an array: in-place solutions are often the follow-up.
- Is there anything about the data you can rely on? Sorted? Distinct? Non-negative? Each "yes" unlocks a row of the signal table.
Write the answers down as the first line of your notes: longest_k_distinct(s: str, k: int) -> int; |s| ≤ 1e5; ASCII; k=0 → 0; "" → 0. This line is your contract for steps 6 and 7.
The clarify checklist
Inputs (types, sizes, ranges, encodings) · Output (exactly what, ties, format) · Empty and minimal inputs · Degenerate parameters (0, 1, k > n) · Duplicates · Negative numbers · Sorted or not · Mutable or not · Single call or many queries · Memory limit.
Step 2: Examples
Write at least three examples and compute the expected output by hand before you have an algorithm. The point is to make your brain execute the specification, not an algorithm. If you cannot compute the answer by hand, you do not yet understand the problem; go back to step 1.
- Normal:
s = "eceba",k = 2. Substrings with at most 2 distinct characters:"e","ec","ece","ceb"? No,"ceb"has 3."eb","eba"? No, 3. So the longest is"ece", length 3. - Edge:
s = "aa",k = 1→ 2 (the whole string).s = "",k = 1→ 0.s = "abc",k = 0→ 0.s = "a",k = 5→ 1 (k larger than the distinct count). - Adversarial: an example designed to break the obvious approach.
s = "aabacbebebe",k = 3→ 7 ("cbebebe"). This example matters because the best window is at the end and the window must shrink past a character that appears again later: a naive "reset when a new character appears" approach gets this wrong.
For each example also record why the answer is what it is. "7 because cbebebe has exactly {c, b, e}" is a sentence you will reuse when tracing.
Step 3: Brute force, and say its complexity out loud
Enumerate the search space literally. The search space is all substrings s[i..j], of them. For each, compute the number of distinct characters, with a set. Keep the longest that satisfies the predicate.
best = 0
for i in 0..n-1:
for j in i..n-1:
if distinct(s[i..j]) <= k:
best = max(best, j - i + 1)
Complexity: time, space for the set, where is the alphabet size. Say it: "the brute force is cubic; with that is operations, so I need to remove two factors of ."
Saying the complexity out loud is not theatre. It sets the target and it makes the next step concrete. You now know you are looking for two separate pieces of repeated work, because each factor of you remove corresponds to one.
Step 4: Find the bottleneck
Ask the three bottleneck questions.
What work is repeated? distinct(s[i..j]) and distinct(s[i..j+1]) are computed independently, yet they differ by one character. Extending the inner loop one step to the right could update a count map in instead of recomputing from scratch in . That removes one factor: .
What information is recomputed? For a fixed i, as j increases, the distinct count never decreases. So once distinct(s[i..j]) > k, every larger j also fails. The inner loop can break early. That does not change the worst case yet, but it exposes a monotonicity.
What would an oracle need to know? Suppose an oracle told you, for each right endpoint j, the smallest left endpoint l(j) such that s[l(j)..j] has at most k distinct characters. Then the answer is in one pass. So the question becomes: can l(j) be computed incrementally? Observe that l(j+1) >= l(j): adding a character on the right can only add distinct characters, so the valid left boundary can only move right. Both endpoints move monotonically. That is the signal for a sliding window, and it removes the second factor of .
Name the waste in one sentence: "The brute force restarts the left endpoint from scratch for every right endpoint, but the left endpoint never needs to move backwards."
Step 5: Optimise
Check the signal table: "substring with a constraint on its contents (at most k distinct)" → sliding window. The bottleneck analysis agrees, which is the usual pattern: the table gives a candidate, the analysis confirms it.
Now state the invariant, the property that holds at the end of every iteration: the window s[left..right] contains at most k distinct characters, and left is the smallest index for which that is true. Everything else follows from maintaining this invariant:
- When
rightadvances, adds[right]to the counts. The invariant may break (distinct count becomesk + 1). - While it is broken, remove
s[left]from the counts and advanceleft. Because distinct count only decreases asleftadvances, the loop terminates with the invariant restored. - After the invariant is restored,
right - left + 1is the longest valid window ending atright; take the maximum.
flowchart LR
A["advance right<br/>count of s at right += 1"] --> Q{"distinct > k ?"}
Q -->|"yes"| S["count of s at left -= 1<br/>drop key if 0<br/>left += 1"]
S --> Q
Q -->|"no"| U["best = max(best, right - left + 1)"]
U -->|"right < n - 1"| A
U -->|"done"| R["return best"]
The data structure is derived from the operation: "add a character, remove a character, how many distinct characters are present". A hash map from character to count answers all three in , with the distinct count equal to the map's size. For a fixed alphabet, an array of 128 or 256 counts plus a separate distinct integer is faster and avoids hashing; the lesson on data structures in memory explains why.
Target check: time because each index enters the window once and leaves at most once; space. Matches the constraint.
Step 6: Write code
Rules that prevent most bugs:
- Handle degenerate cases at the top, explicitly, before the main loop:
k == 0or emptysreturns 0. The main loop might handle them anyway; the explicit guard is documentation and protection against later edits. - Name things after their role in the invariant.
left,right,counts,best. Noti,j,m,res. In a 20-line function this costs nothing and lets your reviewer (or interviewer) verify the invariant by reading. - Pull out a helper when a step has a name. Here nothing qualifies; in the second worked example below,
overlaps(a, b)is worth a helper because it is where the off-by-one lives. - No premature cleverness. Do not inline the shrink loop into a conditional expression. Do not use the array-of-256 optimisation before the hash map version works. Do not combine the add and the shrink into one statement. Clever code is where the bug hides when you have 20 minutes left.
- Write the invariant as a comment on the shrink loop. It is the single most useful comment in the function.
The canonical implementation in four languages is in the Implementation section.
Step 7: Test
Testing has three layers and you do them in this order.
Trace one example by hand. Not in your head: on paper or in a table, one row per step, columns equal to the state variables. For "eceba", k = 2 the trace is below. Doing it reveals whether your mental model of the code matches the code; the common discoveries are a shrink loop that runs one step too few, a best update placed before the shrink instead of after, or an off-by-one in the window length.
Run the edge cases from step 2. Empty string, k = 0, k larger than the distinct count, a string of one repeated character. Each should hit a specific line (the guard, the never-shrinking path, the always-shrinking path).
Complexity sanity. Re-read the loops: one for over right, one nested while over left. The nested loop looks quadratic. It is not, because left only increases and is bounded by right; total shrink steps across the whole run are at most . Say this out loud; an interviewer who sees a nested loop will ask.
The testing lesson turns this into a full discipline, including randomised comparison against the brute force from step 3, which is why writing the brute force was not wasted.
Trace table: s = "eceba", k = 2
Each row is one action of the algorithm. The window is s[left..right]; best is updated only after the invariant is restored (so rows ending in a shrink show best as it stands after the whole step).
| step | action | left | right | window s[left..right] | counts | distinct | best |
|---|---|---|---|---|---|---|---|
| 1 | add s[0]='e' | 0 | 0 | e | e:1 | 1 | 1 |
| 2 | add s[1]='c' | 0 | 1 | ec | e:1, c:1 | 2 | 2 |
| 3 | add s[2]='e' | 0 | 2 | ece | e:2, c:1 | 2 | 3 |
| 4 | add s[3]='b' | 0 | 3 | eceb | e:2, c:1, b:1 | 3 | 3 |
| 5 | shrink: drop s[0]='e' | 1 | 3 | ceb | e:1, c:1, b:1 | 3 | 3 |
| 6 | shrink: drop s[1]='c' | 2 | 3 | eb | e:1, b:1 | 2 | 3 |
| 7 | add s[4]='a' | 2 | 4 | eba | e:1, b:1, a:1 | 3 | 3 |
| 8 | shrink: drop s[2]='e' | 3 | 4 | ba | b:1, a:1 | 2 | 3 |
Row 5 is the one worth staring at: dropping the first e does not fix the window, because a second e remains at index 2. Beginners who "reset on a new character" assume one drop is enough. The while loop, not an if, is what makes row 6 happen. The final answer is 3, established at row 3 and never beaten.
Step 8: Communicate
In an interview you narrate steps 1 to 7 as you do them. The narration is not decoration; it is what the interviewer grades, since they cannot see inside your head and a silent correct solution is indistinguishable from a memorised one. Concretely:
- State the clarifying assumptions and get a nod before continuing.
- Announce the brute force and its complexity, then say "I think we can do better; let me find what is being recomputed." You have now demonstrated two things most candidates skip.
- When you pick the technique, name the invariant in one sentence. "The window always has at most k distinct characters, and I only ever move the left pointer right."
- Before coding, say what you will code: "I'll write the main loop with a hash map of counts;
k == 0and empty string return 0 up front." - After coding, trace one example aloud, then state time and space, then volunteer the follow-ups (the interview follow-ups section near the end of this page lists the standard ones).
Time boxing for a 45-minute interview. A budget that works: 5 minutes for steps 1 and 2, 10 minutes for steps 3 to 5, 20 minutes for step 6, 10 minutes for steps 7 and 8. The 10 minutes in the middle are the ones candidates squeeze, and squeezing them is what produces the 20 minutes of coding the wrong thing. If at minute 15 you have no plan that meets the constraint, say so and propose coding the best plan you have ("I'll implement the version and we can optimise if time allows"). Working code at a worse complexity beats no code at the right one.
The ladder: brute force → better → optimal
| Rung | Idea | Time | Space | Why it improves |
|---|---|---|---|---|
| Brute force | All substrings, recount distinct characters for each | Baseline; defines the search space | ||
| Incremental count | Fix left, extend right, update a count map per step, break when distinct exceeds k | Removes recomputation of the distinct count | ||
| Sliding window | Both pointers move monotonically right; shrink while distinct exceeds k | Removes restarting left for each right; each index enters and leaves once | ||
| Fixed-alphabet array | Same as sliding window with a 128- or 256-slot count array and a distinct counter | Same asymptotics, 3 to 10x faster in practice: no hashing, one cache line of counts |
The middle rung is worth doing in an interview if you cannot see the window: it is a legitimate answer and it exposes the monotonicity that leads to the last rung.
Correctness
Claim. After processing index right, best equals the length of the longest substring ending at or before right with at most k distinct characters.
Invariant. At the end of each iteration of the outer loop: (I1) the multiset counts equals the character counts of s[left..right]; (I2) s[left..right] has at most k distinct characters; (I3) left = 0 or s[left-1..right] has more than k distinct characters.
Proof sketch by induction on right. Initially left = right = 0 after the first add; I1 holds by construction. The shrink loop runs while the distinct count exceeds k; each step removes one character at left, preserving I1. It terminates because distinct count is a non-negative integer that can only decrease and the window of one character always has 1 distinct character which is at most k for k ≥ 1 (for k = 0 the guard returns early). On termination I2 holds. I3 holds because the loop stopped at the first left for which I2 is true, and before the shrink left satisfied I3 from the previous iteration, so no smaller left could work (distinct count is monotone non-increasing in left for fixed right).
Given I2 and I3, right - left + 1 is the length of the longest valid window ending exactly at right. Taking the maximum over all right gives the longest valid window overall, since every substring ends at some right.
The one subtle fact the proof depends on is monotonicity: for fixed right, distinct count of s[l..right] is non-increasing in l. This is what allows the "first valid left" to be found by scanning forward and never backward. Whenever you apply a sliding window to a new predicate, check this monotonicity first; the sliding window lesson catalogues predicates where it fails (for instance "exactly k distinct", which needs a two-window trick).
Complexity
Time. The outer loop runs times. The inner shrink loop executes at most times in total across the whole run because left increases by one per execution and never exceeds right < n. Each execution does hash map work (average case; worst case for a fixed-alphabet array). Total for best, average and worst case. There is no bad input: the pointer argument is an amortised bound that holds for every string.
Space. The count structure holds at most entries: , which is for a fixed alphabet and in the worst case for Unicode input where every character is distinct.
Constants. The hash map version in Python runs around 1 to 2 million characters per second; the array version in C++ several hundred million. The difference is almost entirely hashing and allocation, not the algorithm. See the capstone for measuring this yourself.
Implementation
The canonical sliding window with a hash map of counts. All four blocks run the same eight test cases from step 2.
def longest_k_distinct(s: str, k: int) -> int:
"""Length of the longest substring of s with at most k distinct characters."""
if k == 0 or not s:
return 0
counts: dict[str, int] = {}
left = 0
best = 0
for right, ch in enumerate(s):
counts[ch] = counts.get(ch, 0) + 1
# Invariant after this loop: s[left..right] has <= k distinct chars,
# and left is the smallest index for which that holds.
while len(counts) > k:
out = s[left]
counts[out] -= 1
if counts[out] == 0:
del counts[out]
left += 1
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
cases = [
("eceba", 2, 3), ("aa", 1, 2), ("", 1, 0), ("abc", 0, 0),
("aabacbebebe", 3, 7), ("abcabcbb", 2, 4), ("abaccc", 2, 4), ("a", 5, 1),
]
for s, k, want in cases:
got = longest_k_distinct(s, k)
assert got == want, (s, k, got, want)
print("all tests passed")
import java.util.HashMap;
import java.util.Map;
public class LongestKDistinct {
/** Length of the longest substring of s with at most k distinct characters. */
static int longestKDistinct(String s, int k) {
if (k == 0 || s.isEmpty()) return 0;
Map<Character, Integer> counts = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
counts.merge(s.charAt(right), 1, Integer::sum);
// Invariant after this loop: s[left..right] has <= k distinct chars,
// and left is the smallest index for which that holds.
while (counts.size() > k) {
char out = s.charAt(left);
int c = counts.get(out) - 1;
if (c == 0) counts.remove(out); else counts.put(out, c);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
Object[][] cases = {
{"eceba", 2, 3}, {"aa", 1, 2}, {"", 1, 0}, {"abc", 0, 0},
{"aabacbebebe", 3, 7}, {"abcabcbb", 2, 4}, {"abaccc", 2, 4}, {"a", 5, 1},
};
for (Object[] c : cases) {
int got = longestKDistinct((String) c[0], (Integer) c[1]);
if (got != (Integer) c[2]) throw new AssertionError(c[0] + " k=" + c[1] + " got " + got);
}
System.out.println("all tests passed");
}
}
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <tuple>
// Length of the longest substring of s with at most k distinct characters.
int longestKDistinct(const std::string& s, int k) {
if (k == 0 || s.empty()) return 0;
std::unordered_map<char, int> counts;
int left = 0, best = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
++counts[s[right]];
// Invariant after this loop: s[left..right] has <= k distinct chars,
// and left is the smallest index for which that holds.
while (static_cast<int>(counts.size()) > k) {
char out = s[left];
if (--counts[out] == 0) counts.erase(out);
++left;
}
best = std::max(best, right - left + 1);
}
return best;
}
int main() {
std::vector<std::tuple<std::string, int, int>> cases = {
{"eceba", 2, 3}, {"aa", 1, 2}, {"", 1, 0}, {"abc", 0, 0},
{"aabacbebebe", 3, 7}, {"abcabcbb", 2, 4}, {"abaccc", 2, 4}, {"a", 5, 1},
};
for (const auto& [s, k, want] : cases) {
int got = longestKDistinct(s, k);
assert(got == want);
}
std::cout << "all tests passed\n";
return 0;
}
import assert from "node:assert/strict";
/** Length of the longest substring of s with at most k distinct characters. */
function longestKDistinct(s: string, k: number): number {
if (k === 0 || s.length === 0) return 0;
const counts = new Map<string, number>();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
counts.set(ch, (counts.get(ch) ?? 0) + 1);
// Invariant after this loop: s[left..right] has <= k distinct chars,
// and left is the smallest index for which that holds.
while (counts.size > k) {
const out = s[left];
const c = (counts.get(out) ?? 0) - 1;
if (c === 0) counts.delete(out);
else counts.set(out, c);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
const cases: Array<[string, number, number]> = [
["eceba", 2, 3], ["aa", 1, 2], ["", 1, 0], ["abc", 0, 0],
["aabacbebebe", 3, 7], ["abcabcbb", 2, 4], ["abaccc", 2, 4], ["a", 5, 1],
];
for (const [s, k, want] of cases) {
assert.equal(longestKDistinct(s, k), want, `${s} k=${k}`);
}
console.log("all tests passed");
Two implementation notes. The TypeScript s[right] indexes UTF-16 code units, so an emoji counts as two "characters"; use Array.from(s) first if the alphabet is Unicode. The C++ version with std::unordered_map<char, int> is correct but a std::array<int, 256> indexed by static_cast<unsigned char>(s[i]) plus an integer distinct is the version you would ship; it is the fourth rung of the ladder.
How to get unstuck
Being stuck has a specific feeling: you have re-read the statement three times and nothing new has appeared. Re-reading a fourth time will not help. Each tactic below changes the input to your brain so something new can appear. Try them in roughly this order; each takes under two minutes to try.
- Make n tiny. Solve for , then , then by hand. The case often shows the structure ("the answer for 3 is the answer for 2 plus a decision about the third element", which is a DP or a greedy).
- Name the brute force and its wasted work. If you have not written the brute force, do it now. Then say which quantity it recomputes. This is step 4 and it is where most stuck states end.
- Read the constraints again. screams subsets. permits , so stop looking for the linear solution. says the answer is mathematics or binary search, not iteration.
- Sort the input. Ask what becomes easy if the input were sorted. Pair sums, intervals, "closest", "k-th", duplicates: all become one pass or binary search. If sorting destroys information you need (original indices), sort pairs of (value, index).
- Draw it. Arrays as boxes, graphs as dots and lines, intervals on a number line, recursion as a tree. A monotonic stack problem is obvious the moment you draw the histogram; it is invisible as a list of numbers.
- Fix one variable. Fix the left endpoint, the middle element, the pivot, the root of the subtree, the last element of the subsequence. "For a fixed x, how fast can I solve the rest?" turns a 2D search into copies of a 1D search, and the 1D search is usually a known pattern (3Sum is "fix one, two-pointer the rest").
- Work backwards from the output. What must the last step of any valid solution be? For a path, the last edge; for a parsed expression, the outermost operator; for a sorted result, the maximum. Backward reasoning is how most DP recurrences and most greedy proofs are found.
- Ask what the answer's structure forces. If the answer is a subsequence, must it include the first element? If it is a contiguous block, does it have a leftmost valid start? If the optimal solution exists, can you argue it has some normal form (sorted, starts at a particular position, uses the smallest coin first)? A forced structure shrinks the search space.
- Look for monotonicity. Is there a quantity that only goes one way as you scan? Distinct count as a window grows; feasibility as a budget grows; the set of reachable states as time passes. Monotone quantities give you two pointers, binary search, or an early break.
- Binary search on the answer. If you cannot compute the answer directly but you can check "is answer ≤ x feasible?" quickly, and feasibility is monotone in x, binary search over x. "Minimise the maximum load" and "smallest capacity to ship in D days" are the template.
- Solve the inverse or the complement. Count what you do not want and subtract from the total. "Number of subarrays with at most k distinct" minus "at most k − 1 distinct" equals "exactly k". "Longest valid" versus "shortest invalid". Inverting often converts a hard predicate into an easy one.
- Add a dimension to the state. If a DP state
dp[i]does not have enough information to decide the next step, it needs another index:dp[i][last],dp[i][remaining],dp[i][parity]. The sign that you need this is that two different histories reachdp[i]but should have different futures. - Ask what a greedy would need to be true. Propose the obvious greedy (take the earliest, the smallest, the largest). Try to break it with a 3-element example. If you cannot break it, try to prove it with an exchange argument. If you break it, the counterexample tells you which information the greedy was ignoring, and that information is the extra DP dimension from tactic 12.
- Change the data structure, keep the algorithm. If your algorithm is right but too slow, write down the operation inside the inner loop ("find the min of the active set", "is this value present") and ask which structure does it in or . The algorithm stays; the structure changes; the complexity drops.
If all fourteen fail in an interview, say so. "I'm not seeing the linear approach; I'll implement the quadratic one cleanly and talk through where I'd look for the improvement." Interviewers grade the process; a clean quadratic solution with a correct description of the bottleneck usually passes a round that a broken linear attempt fails.
The method in production (real-world uses)
The eight steps are a general-purpose engineering procedure. Three places where the exact same loop runs outside interviews:
Performance incidents. A slow endpoint is a problem statement. Clarify: which requests, which tenant, since which deploy. Examples: capture one slow and one fast request. Brute force: describe what the code does now, honestly ("for each order, load each line item, for each line item query the product"). Bottleneck: the N+1 query is the recomputed work. Optimise: the operation is "product by id, many times", so batch it into one IN query or a cache; see Caching Strategies and Query Planning. Test: measure at the old and new volume. Communicate: the incident write-up.
Database engines are the signal table applied at scale. A query planner reads a SQL statement and matches its shape to techniques: an equality predicate on an indexed column → B-tree lookup ("sorted array → binary search"); a range predicate → index range scan ("sorted + sweep"); a join on a large unsorted input → hash join ("have I seen this key → hash map"); a join on sorted inputs → merge join ("two pointers"). The Indexing Deep Dive is that table for one engine.
Debugging. Reproduce (examples), state what the code should do (clarify), find the smallest failing input (make n tiny), locate where the invariant first breaks (trace table). The testing and debugging lesson is the method with step 7 as the main course.
Second worked example: minimum meeting rooms
The problem: given meetings as [start, end) intervals, return the minimum number of rooms needed so that no two overlapping meetings share a room. This is Meeting Rooms II (LeetCode 253); the free near-equivalent is Car Pooling (LeetCode 1094).
- Clarify. Intervals half-open? (Yes: a meeting ending at 10 and one starting at 10 can share a room.) Up to meetings, times up to . Empty input returns 0.
- Examples. Normal:
[[0,30],[5,10],[15,20]]→ 2 (the 0–30 meeting overlaps both others, but 5–10 and 15–20 do not overlap each other). Edge:[[7,10],[2,4]]→ 1 (unsorted, non-overlapping). Adversarial:[[1,5],[2,6],[3,7],[4,8]]→ 4 (every pair overlaps; a solution that only compares adjacent meetings undercounts). Verified by script. - Brute force. For every time point t, count meetings with
start ≤ t < end; the answer is the maximum count. Only starts matter as candidate t. . - Bottleneck. Recounting from scratch at every start. Between consecutive starts, the count changes only by the meetings that ended in between. Sort both the starts and the ends and the count can be maintained incrementally.
- Optimise. Signal table: "intervals, minimum rooms" → sort by start + sweep; or the operation "which room frees up earliest" → min-heap of end times. Invariant: the heap holds the end times of meetings currently in progress; its size is the current room count. For each meeting in start order, pop every end time ≤ start (those rooms are free), push this meeting's end. The answer is the maximum heap size. Alternatively, the two-sorted-arrays sweep: sort starts and ends separately; walk starts, advancing an end pointer while
ends[e] ≤ starts[s]; the room count iss - e + 1. Both . - Code. Sort first. Use
<=for the free-room check because intervals are half-open (step 1 decided this). The heap version is in the Intervals lesson; here is the sweep in Python with the three examples:
def min_meeting_rooms(meetings: list[list[int]]) -> int:
"""Minimum rooms for half-open [start, end) meetings."""
starts = sorted(m[0] for m in meetings)
ends = sorted(m[1] for m in meetings)
rooms = best = 0
e = 0
for s in starts:
while e < len(ends) and ends[e] <= s: # a room frees up before this start
e += 1
rooms -= 1
rooms += 1
best = max(best, rooms)
return best
assert min_meeting_rooms([[0, 30], [5, 10], [15, 20]]) == 2
assert min_meeting_rooms([[7, 10], [2, 4]]) == 1
assert min_meeting_rooms([[1, 5], [2, 6], [3, 7], [4, 8]]) == 4
assert min_meeting_rooms([]) == 0
assert min_meeting_rooms([[1, 2], [2, 3], [3, 4]]) == 1 # touching: half-open shares a room
print("ok")
- Test. Trace
[[0,30],[5,10],[15,20]]: starts[0,5,15], ends[10,20,30]. s=0: no end ≤ 0, rooms 1. s=5: no end ≤ 5, rooms 2. s=15: end 10 ≤ 15, rooms 1, then 2. Max 2. Then the touching case[[1,2],[2,3]]: end 2 ≤ start 2 frees the room, answer 1; with<instead of<=the answer would be 2, which is the off-by-one that step 1 protected against. - Communicate. "Sort both lists, sweep, time, space. The heap version has the same complexity but also tells you which meeting is in which room, which matters if the follow-up is to produce the assignment."
Total time for an experienced engineer: under ten minutes, because every step was a known move.
Pitfalls & edge cases of the method itself
- Skipping step 2 because the problem "looks easy". The adversarial example is where you learn what the problem is really about.
"aabacbebebe"is the difference between knowing sliding window and knowing why the shrink is awhile. - Coding the brute force instead of describing it. Step 3 is a sentence and a complexity, not twenty lines. Code it only when it is also your fallback plan or your test oracle.
- Jumping to a technique from the table without the bottleneck check. The table says "sorted → binary search"; the problem wants the sum of all pairs within a distance, which is two pointers. The table proposes; the bottleneck analysis disposes.
- Confusing the invariant with the code. "I move left while the map is too big" is code. "The window always has at most k distinct characters" is the invariant. Only the second lets you prove anything or spot that a
whileis needed. - Testing by re-reading. Re-reading code you just wrote finds about a third of the bugs. A trace table finds most of the rest. The testing lesson has the numbers and the recipes.
- Letting the time budget collapse into coding. The 10 minutes of steps 3 to 5 are the highest-value minutes of the interview. Protect them.
- Optimising constants before the complexity class is right. The array-of-256 trick is a 5x win on top of a correct . It is nothing on top of an .
- Forgetting the degenerate parameters.
k = 0,k > n,n = 0,n = 1. Write them in step 1, test them in step 7.
Variations: adapting the method to other settings
Contests (Codeforces, AtCoder). Steps 1 and 2 shrink to reading the constraints and the provided samples; step 8 disappears. Step 3 is replaced by "what complexity do the constraints allow", and step 7 is replaced by a stress test against a brute force (see the testing lesson), because a wrong submission costs a penalty and the judge gives no feedback beyond "wrong answer".
Take-home assignments. Steps 6 and 7 expand: real tests, real naming, a README that is step 8 in writing. Step 5 contracts: pick the simplest technique that meets the stated scale, and say in the README what you would change at 100x scale.
System design interviews. The same loop at a different altitude. Clarify becomes requirements and scale estimates (System Design Math); brute force becomes the single-server design; the bottleneck is found by estimating QPS and bytes; the signal table becomes "read-heavy → cache", "write-heavy → log-structured storage", "hot keys → consistent hashing"; see Consistent Hashing and Storage Engines.
Pair programming with an AI assistant. The method does not change, the division of labour does: you do steps 1 to 5 and 8 (they are the understanding), the assistant drafts step 6, and you do step 7 with extra suspicion, because generated code is confident about edge cases it has never considered.
Practice ladder
Ten problems, chosen so that each one is mainly about one step of the method. Do them in order; after each, write down which step you spent the most time on and whether it was the intended one.
1. Two Sum — step 1, clarify
Two Sum (LeetCode 1). Return the indices of two distinct elements that add to a target. The problem is trivial once you have asked: exactly one answer or many? Can the same element be used twice? Are the indices returned in any order? Unsorted, so no two pointers; the operation "have I seen target - x" is a hash map.
Hint
For each element x at index i, check whether target - x is already in a map from value to index. Insert x after checking, which is what prevents using the same element twice.
2. Merge Intervals — step 2, examples
Merge Intervals (LeetCode 56). Combine all overlapping intervals into disjoint ones. The algorithm is one line after sorting; the problem is entirely about the examples you write: touching intervals [1,4],[4,5], nested [1,4],[2,3], and an interval that swallows several later ones.
Hint
Sort by start. Keep the last merged interval; if the next start is at most the last end, extend the last end to the max of the two ends, otherwise append. Decide on the touching case before coding: the LeetCode version treats [1,4] and [4,5] as overlapping.
3. Maximum Subarray — step 3, brute force first
Maximum Subarray (LeetCode 53). The largest sum of any contiguous subarray. State the brute force (all (i, j) pairs with a running sum) before anything else; then ask what is recomputed. The all-negative array is the edge case that breaks the popular "reset to zero" variant, and the testing lesson uses exactly that bug for its stress-test demonstration.
Hint
For each j, the best subarray ending at j is either a[j] alone or a[j] plus the best ending at j-1. That is Kadane's recurrence; initialise with a[0], not 0.
4. Product of Array Except Self — step 4, find the bottleneck
Product of Array Except Self (LeetCode 238). For each index, the product of all other elements, without division. The brute force recomputes multiplications per index; the recomputed information is "product of everything to my left" and "product of everything to my right", both of which are prefix and suffix products.
Hint
Two passes: left-to-right filling out[i] with the product of a[0..i-1], then right-to-left multiplying out[i] by a running suffix product. time, extra space.
5. Longest Substring Without Repeating Characters — step 5, the signal table
Longest Substring Without Repeating Characters (LeetCode 3). The running example with k replaced by "no character twice". Match the signal ("substring with a constraint on contents"), state the invariant, derive the structure.
Hint
Same window as the running example; the predicate is "no count exceeds 1". A map from character to its last index lets you jump left directly instead of shrinking one step at a time.
Solution
def length_of_longest_substring(s: str) -> int:
last_seen: dict[str, int] = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # jump past the previous occurrence
last_seen[ch] = right
best = max(best, right - left + 1)
return best
assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0
assert length_of_longest_substring("abba") == 2 # the >= left check matters here
print("ok")
time, space. The last_seen[ch] >= left test is the bug magnet: without it, "abba" moves left backwards when the second a is seen.
6. Top K Frequent Elements — step 5, the data structure for the operation
Top K Frequent Elements (LeetCode 347). Return the k values that occur most often. After counting, the operation is "keep the k largest by count", which is a heap of size k; or, since counts are bounded by n, bucket by count for .
Hint
Count with a hash map. Then either push (count, value) into a min-heap and pop whenever its size exceeds k (), or build an array of lists indexed by count and read it from the top ().
Solution
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for value, c in counts.items():
buckets[c].append(value)
out: list[int] = []
for c in range(len(nums), 0, -1): # highest count first
for value in buckets[c]:
out.append(value)
if len(out) == k:
return out
return out
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]
assert sorted(top_k_frequent([4, 4, 4, 5, 5, 6, 6, 7], 3)) == [4, 5, 6]
print("ok")
time and space. The bucket array is the "counting sort" move: when the key (a count) is bounded by n, sorting is linear.
7. Spiral Matrix — step 6, write code carefully
Spiral Matrix (LeetCode 54). Output the elements of an m × n matrix in clockwise spiral order. There is no algorithmic insight; the whole problem is step 6: four boundary variables, four loops, and the two guards that prevent double-visiting the middle row or column of a non-square matrix.
Hint
Keep top, bottom, left, right. Walk the top row, then the right column, then (if top <= bottom) the bottom row backwards, then (if left <= right) the left column upwards; shrink the boundary after each wall. Test on a 1×n, an n×1, a 2×3 and a 3×2.
8. Find Minimum in Rotated Sorted Array — step 7, test
Find Minimum in Rotated Sorted Array (LeetCode 153). A sorted array of distinct values was rotated; find its minimum in . The binary search is five lines and almost everyone writes one of them wrong; the problem is step 7. Trace it on [3,4,5,1,2], [1,2,3] (no rotation), [2,1], and [1].
Hint
Compare a[mid] with a[hi]. If a[mid] > a[hi] the minimum is to the right (lo = mid + 1), otherwise it is at mid or to the left (hi = mid). Loop while lo < hi; return a[lo]. Note the asymmetry: mid + 1 on one side, mid on the other, because mid can still be the answer in the second case.
9. Koko Eating Bananas — unstuck tactic 10, binary search on the answer
Koko Eating Bananas (LeetCode 875). Piles of bananas, h hours, one pile per hour at speed k; find the minimum integer speed that finishes in time. There is no direct formula, but "can speed k finish in h hours" is a one-pass check and is monotone in k.
Hint
The answer is between 1 and max(piles). Binary search the smallest k for which sum(ceil(p / k)) <= h.
Solution
def min_eating_speed(piles: list[int], h: int) -> int:
def feasible(k: int) -> bool:
return sum((p + k - 1) // k for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi: # invariant: answer in [lo, hi]
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
assert min_eating_speed([3, 6, 7, 11], 8) == 4
assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30
assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23
assert min_eating_speed([1], 1) == 1
print("ok")
where . The template generalises to every "minimise the maximum" problem: write feasible, prove it monotone, binary search.
10. Trapping Rain Water — the full method, then communicate
Trapping Rain Water (LeetCode 42). Given bar heights, how much water sits between them after rain. Run every step: brute force (: for each bar, the max to its left and right), bottleneck (the maxes are recomputed), better (prefix and suffix max arrays, time and space), optimal (two pointers, space), and a monotonic stack alternative. Then practise step 8: explain the three solutions and their trade-offs in under three minutes.
Hint
Water above bar i is min(maxLeft[i], maxRight[i]) - h[i]. With two pointers, whichever side has the smaller running max is the side whose water you can finalise, because the other side guarantees a wall at least that high.
Solution
def trap(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9
assert trap([]) == 0
assert trap([3, 3, 3]) == 0
assert trap([5, 0, 5]) == 5
print("ok")
time, space. The correctness argument is the sentence in the hint: when height[left] < height[right], right_max >= height[right] > height[left], so the water at left is bounded by left_max alone.
Common mistakes & interview follow-ups
The follow-ups below are the ones interviewers ask after a correct solution. Having an answer ready is step 8.
"Can you do better?" First check whether a lower bound forbids it: any algorithm must read all characters, so is optimal for the running example and you can say so. If you are at because of a sort, ask whether the keys are bounded (counting sort) or whether the sort is even necessary. If you are at , name the recomputed work and say which structure would remove it, even if you cannot finish coding it.
"What if the input is huge / does not fit in memory?" Say what your algorithm actually needs to hold. A sliding window needs the window plus the count map: , so it streams fine. A sort needs everything: switch to external merge sort, or ask whether an approximate answer is acceptable (sampling, a Count-Min sketch). For prefix sums, the prefix array can be replaced by a running total if queries arrive in order.
"What if it is a stream?" Can you process each element once with bounded state? Sliding windows, Kadane, reservoir sampling, two-heap median, counting with a hash map of bounded key space: yes. Anything that needs the sorted input or random access: no, unless the window is bounded and you keep a buffer of that size.
"What if there are many queries?" Precompute. Prefix sums for range sums, a sparse table for range minima, a sorted copy for rank queries. The trade-off sentence is "I spend or once so that each query is or ."
"What if the data is mostly sorted / mostly duplicates / adversarial?" Say which rung of your ladder degrades. Quicksort degrades on sorted input without randomisation; a hash map degrades on adversarial keys (Hash Tables covers the attack); the sliding window never degrades, which is a property worth stating.
"How would you test this?" The next lesson is the answer. The short version: the edge cases from step 2, a hand trace, then a randomised comparison against the brute force from step 3.
Common mistakes under pressure, each a violation of one step: solving a different problem than the one asked (step 1), only testing on the provided example (step 2), announcing "I'll use a hash map" before saying what it is for (step 5), inventing clever index arithmetic (step 6), declaring victory after the code compiles (step 7), and going silent for ten minutes (step 8).
Quick quiz
1. A problem says and asks for a count over all pairs. What complexity are you looking for, and what does that rule out?
Answer
, possibly . It rules out enumerating pairs (). You need to count pairs without touching each pair: sort and two-pointer, or a hash map of complements, or a Fenwick tree over values.
2. Why is the shrink step in the running example a while and not an if?
Answer
Removing one character from the left reduces the distinct count only if that character's count drops to zero. In "eceb" with k = 2, removing the first e leaves {e:1, c:1, b:1}, still 3 distinct; a second removal is needed. The while restores the invariant however many removals it takes.
3. Your brute force is and the constraint demands . What does that tell you about the optimisation?
Answer
Two independent factors of must go, so there are usually two pieces of repeated work. In the running example: recomputing the distinct count (fixed by incremental counting) and restarting the left pointer (fixed by monotonicity).
4. You are at minute 18 of a 45-minute interview with no plan that meets the constraint. What do you do?
Answer
Say so, then code the best plan you have (usually the one) cleanly, naming the bottleneck you would attack with more time. A working slower solution plus a correct diagnosis beats a broken fast one.
5. The predicate is "exactly k distinct characters" instead of "at most k". Does the single sliding window still work? Why or why not?
Answer
No. "Exactly k" is not monotone in the left endpoint: shrinking the window can move the distinct count from to to , so there is no single "first valid left". Use the complement trick: count windows with at most k minus windows with at most k − 1, or maintain two windows.
The one-page checklist
Print this. Run it on every problem until you no longer need to.
| Step | Do | Say (interview) | Minutes of 45 |
|---|---|---|---|
| 1. Clarify | Signature; sizes and ranges; alphabet; empty, 0, 1, k > n; duplicates; negatives; sorted?; mutable?; stream? | "Let me confirm: the input is …, the output is …, and I'm assuming …" | 2–3 |
| 2. Examples | One normal, two edge, one adversarial; expected outputs by hand; a sentence on why | "Here's an example that would break a naive approach …" | 2–3 |
| 3. Brute force | Enumerate the search space; state the complexity; compare with the constraint | "The brute force is ; the constraint wants , so two factors must go" | 2 |
| 4. Bottleneck | What is repeated? What is recomputed? What would an oracle need to know? Name the waste in one sentence | "The waste is: I recompute … for every …" | 3 |
| 5. Optimise | Signal table → candidates; state the invariant; derive the data structure from the inner-loop operation; check the target | "The invariant is …; the operation I need is …, which is a …" | 5 |
| 6. Code | Degenerate cases first; names from the invariant; helpers for named steps; no cleverness; invariant as a comment | "I'll write … first, then the main loop" | 20 |
| 7. Test | Trace one example in a table; run every edge case; re-derive the complexity from the loops | "Let me trace eceba … and here is why the nested loop is still linear" | 5 |
| 8. Communicate | Time, space, trade-offs; the follow-ups before they are asked: better? huge? stream? many queries? | "This is time, space; if the input were a stream …" | 5 |
| Stuck? | Tiny n · name the waste · re-read constraints · sort · draw · fix one variable · work backwards · answer's structure · monotonicity · binary search the answer · complement · add a state dimension · test the greedy · change the structure | "I'm not seeing the linear version yet; let me try …" | as needed |
Further reading / sources
- George Pólya, How to Solve It (1945). The four phases; everything here is a specialisation.
- Steven Skiena, The Algorithm Design Manual, 3rd ed., Chapter 1 ("Introduction to Algorithm Design") and the "war stories" throughout, which are the method applied to real consulting problems.
- Antti Laaksonen, Competitive Programmer's Handbook, Chapter 1 and 2 (time complexity and the constraints-to-complexity table). Free online.
- Gayle Laakmann McDowell, Cracking the Coding Interview, 6th ed., "Technical Questions": the BUD optimisation (Bottlenecks, Unnecessary work, Duplicated work) is step 4 under another name.
- Thomas Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 2 (loop invariants) for the proof style used in the Correctness section.
- cp-algorithms, Two pointers type problems, for the monotonicity argument behind sliding windows.
Previous lesson: Your Language's Data Structures · Next lesson: Testing & Debugging Algorithms · Module: Foundations · Course: DSA: Zero to Mastery
Related: Complexity Analysis · Sliding Window · Intervals · Arrays & Strings · Recursion & Induction