Sign in to watch this lesson
Algorithms - Capstone · 5:29
The Problem-Solving Routine
A routine for a problem you have never seen: read the constraints to find the target complexity, write the obviously correct brute force, find its bottleneck and name the pattern that removes it, and check the edge cases before trusting anything. We run one problem, counting subarrays with sum k, through it four times: a triple loop, prefix sums, a one-pass hash map, and the shrinking window that negative numbers break. Then we time the three correct versions on a Mac.
You will learn
- Read the intended complexity off the constraints (n up to 20, 500, 5000, 2 * 10^5, 10^7 with about 10^8 simple steps per second)
- Start from a correct brute force, find its bottleneck and name the pattern that removes it (prefix sums, then a hash map of running totals)
- State the invariant of the one-pass hash-map solution and explain why the shrinking window fails when values can be negative
- Check edge cases before submitting: empty input, one element, all equal values (answers beyond 32 bits) and maximum values