The optimization task gives you a new, bigger input that your working code can't handle. Your job is to find out why and make it fast enough without breaking it.
Find the bottleneck#
Understand the input and measure before you change any code.
1. Look at the new input first#
Check its size, and also its shape. Is it dense or sparse? Lots of duplicates? Skewed? Deeply nested? Many queries against the same data? The shape is usually the hint for which fix you need.
2. Measure before changing anything#
Run the code on the big input and note how it fails: timeout, out of memory, or RecursionError. Then find which function dominates. Timing prints with time.perf_counter() around the main sections are usually enough, and cProfile is there if you need more detail.
3. Name the bottleneck out loud, with its complexity#
For example:
"This is O(2ⁿ) because it recomputes the same subproblems, and n = 40 is far too large."
Pick the fix#
Match what you found to a technique, and check it fits before you build it.
4. Match what you find to a technique#
| What you see | Technique |
|---|---|
| Same subproblems recomputed | Memoization / DP |
| Repeated scans or lookups | A hash map or set index, precomputation |
| Many queries on the same data | Preprocess once: prefix sums, sorting, building an index |
| Repeated min/max or top-k | Heap |
| Prefix matching across many strings | Trie |
| A small set of items as part of the state (~20 or fewer) | Bitmask |
| Exploring branches that can't succeed | Pruning, early termination |
| Repeated connectivity checks | Union-find |
| Shortest path | BFS if unweighted, Dijkstra if weighted, not DFS |
| Deep recursion crash | Iterate with an explicit stack. setrecursionlimit is only a band-aid |
| Sorted data, or data you can sort | Binary search, two pointers |
5. Check the new complexity fits#
Python manages roughly 10⁶–10⁷ simple operations per second. Estimate your new complexity on the big n and confirm it fits before you build it.
Build it and prove it#
The faster version has to give the same answers as the slow one.
6. Implement it, and keep the old version#
The AI can write the optimization from your spec. Keep the slow version, because it becomes your correctness check: run both on small and medium inputs and confirm the outputs match.
When you memoize, make sure the cache key includes every piece of state the result depends on, and never cache a function that reads mutable shared state. Both mistakes give wrong answers that still pass small tests.
7. Benchmark#
Time the code before and after on the big input, and say the numbers:
"Down from timing out to 0.4 seconds."
8. If time runs out#
State the bottleneck, the better approach, its complexity, and what you'd implement next. That still earns credit.