Prefix sum
The total of everything up to each position, so any range's total is one subtraction.
The trail club has a counter at the trailhead that records hikers each day. "How many came between day 30 and day 90?" Adding up the range every time costs O(n) per question. Instead, build the running totals once:
prefix[i]is the total of the firstidays. Then any range total is one subtraction,prefix[b] - prefix[a].
Try it now
Most problems give themselves away: sorted input, a count, a range, or a fixed-size window.
Learn it properly
Patterns for coding problems · Two pointers, counting with dictionaries, prefix sums and sliding windows: O(n) answers to classic problems. About 45 minutes.
Other terms from the same lesson
- sliding window: A range that moves along the data, adding what enters and removing what leaves instead of starting over.
- two pointers: A pattern that moves two positions through data, often inward from both ends of a sorted list, to avoid a nested loop.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.