Recap: Optimising a Solution

Cost each step, compare the largest with the best conceivable runtime, remove its waste with a standard move, and say what the move costs.

Optimising a correct solution follows six steps:

Cost each step and find the one that dominates.
State the best conceivable runtime: the cost of reading the input and writing the output.
If the dominant step already matches it, stop.
Name the waste in that step: a bottleneck, unnecessary work or duplicated work.
Apply the standard move that removes it.
State the memory the move costs, then cost the solution again from step 1.

Each kind of waste has a sign in the code and a move that removes it.

Kinds of waste and the moves that remove them
Kind of waste	How it shows	Standard move	Memory it costs
Bottleneck	A search of a list inside a loop	A hash set or map	O(n)
Bottleneck	A check of every pair in a sorted array	Two pointers	O(1)
Duplicated work	Range totals added up again and again	Prefix sums	O(n), or O(1) in a single pass
Duplicated work	The same recursive call made many times	Memoisation	One entry per distinct call
Unnecessary work	Every value sorted when only the smallest few are needed	A heap	O(k) for k values kept
Bottleneck	Comparing every item with every other	Sorting, then a scan or a search by halving	The sort's

Speed up only the step that dominates, since a faster line elsewhere leaves the total almost unchanged, and stop at the best conceivable runtime, where only memory can still improve.

Complexity Analysis
Performance

← → move through sections and cards