The brief
A sales report over a list of orders. It was written for a demo with two hundred rows and it is now being run over two hundred thousand, where it takes minutes. Nobody has said it is wrong — the numbers are right. It is simply too slow to use.
This is the shape of almost every real performance problem: working code, sensible-looking loops, and a growth rate nobody measured.
The three problems
Each one has a standard fix, and each fix is a structure from this course rather than a cleverer loop:
- Repeated range sums → a prefix-sum array, built once in O(n), every query then O(1).
- Counting by a key → a hash map, one pass, O(n).
- Finding pairs that match → a set of what you have already seen, one pass, O(n).
| Function | What it does | Growth |
|---|---|---|
slowTotal | Scans every order to sum one date range | O(n) per query — O(q·n) for q of them |
slowTopCustomer | For each order, scans the rest to count that customer | O(n²) |
slowDuplicates | Compares every pair of orders | O(n²) |
Prefix sums
O(n) once, then O(1) for ever. It is the cheapest trade in this course, and the reason to know it is that "sum this range" appears in reports, charts, sliding windows and time series constantly.
/* built once: prefix[i] is the total of the first i values */
const prefix = [0];
for (let i = 0; i < values.length; i++) prefix.push(prefix[i] + values[i]);
/* every range afterwards, in one subtraction */
const totalBetween = (from, to) => prefix[to + 1] - prefix[from];The rule for this kind of work
That last point is what makes the checks in this lab work: for every function you write, the fast version and the slow version are run on the same data and compared.
- Measure before you touch anything. Run it at two sizes and look at the ratio. The slow part is often not the part you would have guessed.
- Do not make the loop faster — remove it. An O(n²) loop that is twice as fast is still O(n²).
- Precompute what is asked for repeatedly. The prefix array, the index, the map.
- Keep the answers identical. Every fix here must return exactly what the slow version returned, including the tie-breaking.