01 / The idea
Sorted prices and running totals both let you skip work.
A customer has a 19-dollar gift card and wants two books that use it up exactly. The shelf
is sorted by price: [3, 5, 7, 8, 12, 14, 17]. Checking every pair works, and
for seven books it is 21 pairs. The order of the shelf lets you do better: most of those
pairs can be ruled out without being added up.
The same shop runs a report that asks for the total of a stretch of that list, again and again: positions 1 to 4, then 2 to 6, then 0 to 3. Adding each stretch from scratch reads the same prices over and over. A list of totals so far, built once, turns every stretch into one subtraction.
Two pointers walk a sorted list from both ends and use the order to throw away pairs that cannot work. Prefix sums store the total before each position so any contiguous range is the difference of two of them. Both use something true of the data, its order or its stability, to skip work.
02 / Name the rule
Keep a bracket of possible pairs, and a zero in front of the totals.
Place left at index 0 and right at the last index. When the sum is
too large, move right in; when it is too small, move left in. The invariant:
every pair outside the bracket is already known to be wrong. The cheapest and dearest books make
3 + 17 = 20, too much, and no cheaper partner could rescue 17, so 17 is out. Each move removes
a whole row or column of the pair table.
while left < right:
if values[left] + values[right] == target: found
if sum < target: left += 1
else: right -= 1For the prices, the prefix array is [0, 3, 8, 15, 23, 35, 49, 66]. The zero in
front means prefix[i] is the total of everything before position i, so positions 1 through 4 are prefix[5] − prefix[1], or 35 − 3 = 32. That extra zero turns every inclusive range into the same
subtraction, with no special case when a range starts at 0.
What each rule assumesSorted input, and values that stay put
Two pointers need sorted values for the direction argument. If the values arrive unsorted, sort them first and remember whether the original positions matter.
Prefix sums need values that stay put between building and asking. If one price changes, every total after it changes too. When edits are frequent, a Fenwick tree or segment tree keeps range totals fast while allowing updates, at the cost of more machinery.
03 / Follow one operation
Three comparisons for the gift card, one subtraction for the range.
Before you watch, predict which pair uses up the 19-dollar card and how many sums it takes to find it. The animation follows the two pointers on the shelf, then checks pairs one by one for contrast. Then it builds the prefix array, answers positions 1 to 4 with one subtraction, and lines up the work each approach did. Try it lets you pick your own target and range.
Move one edge or subtract two prefixes.
sorted book prices
Use up the 19 gift card
sum = 195 + 14 = 19
Compare 3 + 17 = 20 with 19. Step 1 of 6.
Compare 3 + 17 = 20 with 19. Step 1 of 6.
Follow the next safe move.
Compare 3 + 17 = 20 with 19. Step 1 of 6.
Reduced motion: choose a scene to see its completed state.
Read this scene
Compare 3 + 17 = 20 with 19. Step 1 of 6.
Compare 3 + 17 = 20 with 19. Step 1 of 6.
Find a pair totaling 19.
Watch restarts when you return. Step through keeps the selected trace. Try it measures a fresh pair or range query.
04 / Read the shape
Keep the baseline beside the fast version.
Basic form is findPair and rangeTotal: the
pointer moves and the prefix construction, each beside its baseline mode, plus prefixSums and rangeFromPrefix for building once and asking many
times. In the wild reviews one shelf: a gift card pair and a price range together.
Both modes return the same answer shape, so the faster one is testable: two pointers must find a pair whenever brute force does, with the same total (on repeated prices they can pick different positions), and a prefix query must agree with scanning.
pairPrices and totalRange are the small contracts: find an index pair or return one inclusive range total, with brute-force and scan baselines available for comparison.
// Two pointers are safe here because the values are sorted: moving the left pointer only raises
// the sum, and moving the right pointer only lowers it. The source records comparisons for the UI.
export function findPair(
values: readonly number[],
target: number,
mode: PairMode = 'two-pointers',
trace = false
): PairEvaluation {
const checked = validateValues(values, mode === 'two-pointers');
validateTarget(target);
const steps: PairStep[] = [];
let comparisons = 0;
let pair: [number, number] | null = null;
if (mode === 'brute-force') {
for (let left = 0; left < checked.length - 1; left++) {
for (let right = left + 1; right < checked.length; right++) {
const sum = checked[left] + checked[right];
comparisons++;
if (trace)
steps.push({
kind: 'compare',
left,
right,
leftValue: checked[left],
rightValue: checked[right],
sum,
target
});
if (sum === target) {
pair = [left, right];
if (trace) steps.push({ kind: 'found', left, right, sum });
return { kind: 'pair', mode, values: checked, target, pair, comparisons, steps };
}
}
}
if (trace) steps.push({ kind: 'miss' });
return { kind: 'pair', mode, values: checked, target, pair, comparisons, steps };
}
let left = 0;
let right = checked.length - 1;
while (left < right) {
const sum = checked[left] + checked[right];
comparisons++;
if (trace)
steps.push({
kind: 'compare',
left,
right,
leftValue: checked[left],
rightValue: checked[right],
sum,
target
});
if (sum === target) {
pair = [left, right];
if (trace) steps.push({ kind: 'found', left, right, sum });
break;
}
if (sum < target) {
const from = left;
left++;
if (trace) steps.push({ kind: 'move', pointer: 'left', from, to: left });
} else {
const from = right;
right--;
if (trace) steps.push({ kind: 'move', pointer: 'right', from, to: right });
}
}
if (!pair && trace) steps.push({ kind: 'miss' });
return { kind: 'pair', mode, values: checked, target, pair, comparisons, steps };
}
// Prefix sums spend O(n) once so every later inclusive range [start, end] is one subtraction.
export function rangeTotal(
values: readonly number[],
start: number,
end: number,
mode: RangeMode = 'prefix-sum',
trace = false
): RangeEvaluation {
const checked = validateValues(values, false);
validateRange(checked.length, start, end);
const steps: RangeStep[] = [];
if (mode === 'scan') {
let total = 0;
for (let index = start; index <= end; index++) {
total += checked[index];
if (trace) steps.push({ kind: 'scan', index, value: checked[index], running: total });
}
return {
kind: 'range',
mode,
values: checked,
start,
end,
total,
work: end - start + 1,
prefix: [],
steps
};
}
const prefix = [0];
for (let index = 0; index < checked.length; index++) {
const total = prefix[index] + checked[index];
prefix.push(total);
if (trace) steps.push({ kind: 'prefix', index, value: checked[index], total });
}
const total = prefix[end + 1] - prefix[start];
if (trace)
steps.push({
kind: 'range',
start,
end,
fromPrefix: prefix[start],
toPrefix: prefix[end + 1],
total
});
// The preparation pass is part of this call's work: one addition per value, then one
// subtraction. It pays for itself only when the same prefix array answers many ranges.
return {
kind: 'range',
mode,
values: checked,
start,
end,
total,
work: checked.length + 1,
prefix,
steps
};
}
// Build once, then answer any number of inclusive ranges with rangeFromPrefix.
export function prefixSums(values: readonly number[]): number[] {
const prefix = [0];
for (const value of validateValues(values, false)) prefix.push(prefix[prefix.length - 1] + value);
return prefix;
}
export function rangeFromPrefix(prefix: readonly number[], start: number, end: number): number {
validateRange(prefix.length - 1, start, end);
return prefix[end + 1] - prefix[start];
}// Two pointers use sortedness as their invariant: the left move can only raise a sum and the
// right move can only lower it. The brute-force version is retained as a correctness baseline.
func FindPair(values []int, target int, mode PairMode, trace bool) (PairEvaluation, error) {
checked, err := validateValues(values, mode == TwoPointers)
if err != nil {
return PairEvaluation{}, err
}
if err := validateTarget(target); err != nil {
return PairEvaluation{}, err
}
result := PairEvaluation{Mode: mode, Values: checked, Target: target}
compare := func(left, right int) bool {
sum := checked[left] + checked[right]
result.Comparisons++
if trace {
result.Steps = append(result.Steps, PairStep{Kind: "compare", Left: left, Right: right, LeftValue: checked[left], RightValue: checked[right], Sum: sum, Target: target})
}
if sum == target {
result.Pair = [2]int{left, right}
result.HasPair = true
if trace {
result.Steps = append(result.Steps, PairStep{Kind: "found", Left: left, Right: right, Sum: sum})
}
return true
}
return false
}
if mode == BruteForce {
for left := 0; left < len(checked)-1; left++ {
for right := left + 1; right < len(checked); right++ {
if compare(left, right) {
return result, nil
}
}
}
if trace {
result.Steps = append(result.Steps, PairStep{Kind: "miss"})
}
return result, nil
}
left, right := 0, len(checked)-1
for left < right {
if compare(left, right) {
return result, nil
}
sum := checked[left] + checked[right]
if sum < target {
from := left
left++
if trace {
result.Steps = append(result.Steps, PairStep{Kind: "move", Pointer: "left", From: from, To: left})
}
} else {
from := right
right--
if trace {
result.Steps = append(result.Steps, PairStep{Kind: "move", Pointer: "right", From: from, To: right})
}
}
}
if trace {
result.Steps = append(result.Steps, PairStep{Kind: "miss"})
}
return result, nil
}
// Prefix sums store the total before each position, turning every later inclusive range into one
// subtraction. Scanning remains available as the simple baseline for the same query.
func RangeTotal(values []int, start, end int, mode RangeMode, trace bool) (RangeEvaluation, error) {
checked, err := validateValues(values, false)
if err != nil {
return RangeEvaluation{}, err
}
if err := validateRange(len(checked), start, end); err != nil {
return RangeEvaluation{}, err
}
result := RangeEvaluation{Mode: mode, Values: checked, Start: start, End: end}
if mode == Scan {
for index := start; index <= end; index++ {
result.Total += checked[index]
result.Work++
if trace {
result.Steps = append(result.Steps, RangeStep{Kind: "scan", Index: index, Value: checked[index], Running: result.Total})
}
}
return result, nil
}
result.Prefix = []int{0}
for index, value := range checked {
total := result.Prefix[index] + value
result.Prefix = append(result.Prefix, total)
if trace {
result.Steps = append(result.Steps, RangeStep{Kind: "prefix", Index: index, Value: value, Total: total})
}
}
result.Total = result.Prefix[end+1] - result.Prefix[start]
// The preparation pass is part of this call's work: one addition per value, then one
// subtraction. It pays for itself only when the same prefix array answers many ranges.
result.Work = len(checked) + 1
if trace {
result.Steps = append(result.Steps, RangeStep{Kind: "range", Start: start, End: end, FromPrefix: result.Prefix[start], ToPrefix: result.Prefix[end+1], Total: result.Total})
}
return result, nil
}
// PrefixSums builds once; RangeFromPrefix then answers any number of inclusive ranges.
func PrefixSums(values []int) ([]int, error) {
checked, err := validateValues(values, false)
if err != nil {
return nil, err
}
prefix := []int{0}
for _, value := range checked {
prefix = append(prefix, prefix[len(prefix)-1]+value)
}
return prefix, nil
}
func RangeFromPrefix(prefix []int, start, end int) (int, error) {
if err := validateRange(len(prefix)-1, start, end); err != nil {
return 0, err
}
return prefix[end+1] - prefix[start], nil
}Reading the TypeScriptImmutable inputs and explicit modes
findPair checks that the values are sorted only in the two-pointer mode. rangeTotal keeps the scan baseline beside the prefix implementation, so the work
counters describe the strategy that ran, preparation included.
Reading the GoThe same invariant with explicit structs
Go returns structs holding the answer, the work count, and an optional trace. Validation happens at the boundary, so the loops stay about pointer moves and running totals.
What would I normally use in application code?A loop, or the database’s window function
Neither language ships either technique; each is a few lines. When the numbers live in a
database, SUM(amount) OVER (ORDER BY day) computes the running totals for you,
and a range is two rows of that result.
05 / Try a decision
Choose the preparation only when the questions repay it.
A preparation pass costs a read of every price. Decide when that pays for itself before the feedback tells you.
06 / Follow the cost
Count the preparation once, then each question.
Here is every operation at a glance, with n prices and q range questions. The rest of this section is about when preparation wins.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Brute-force pair search | O(n²) | O(1) | Try every distinct pair until one adds up to the target. |
| Two pointers on sorted values | O(n) | O(1) | Each pointer only moves inward; the input must be sorted or sorted as a separate step. |
| Build prefix sums | O(n) | O(n) | One running total for each position plus an initial zero. |
| One range from a built prefix array | O(1) | O(1) | An inclusive range [start, end] is prefix[end + 1] − prefix[start]. |
| Scan one range | O(end − start + 1) | O(1) | Simple and often right when there are only a few queries or the ranges are short. |
Two pointers are linear because each pointer moves at most n times in total. In the animation, three sums found 5 + 14; checking pairs in order took ten.
Prefix sums shine only across many questions. One range from positions 1 to 4 costs a scan
four additions, and costs the prefix mode seven additions to prepare plus one subtraction:
the lab shows 4 against 8. A thousand such questions cost the scan up to seven thousand
additions and the built prefix array seven additions and a thousand subtractions. The useful
comparison is O(n) + q · O(1) against q · O(r) for ranges of length
r.
07 / Give it a real job
Build the totals where the numbers stop changing.
In a real shop, the sales report reads a day’s prices once, builds the running totals, and answers every “how much between these two positions” from them. The same totals serve every question until the price list changes, and then they are rebuilt. The gift card check runs on a sorted copy of the shelf and reports prices, not positions, because sorting moves them.
What the examples leave out is a decision too. Prices are whole dollars, so totals stay exact; real money needs cents or a decimal type. A price list that changes all day needs an update structure instead of a rebuild. And two pointers find one pair; listing every pair that fits needs a different loop.
Build UIs?See the running totals your charts and lists already keep, and the day you keep them yourself.
Where it already is in your components
A cumulative line on a spending chart is a prefix sum: each point is the total so far. The moment someone brushes a date range and asks how much was spent in it, that line answers with two lookups and a subtraction instead of a loop over the days.
Virtualized lists keep one too. TanStack Virtual measures each row and stores its start as the end of the row before it, a running total of heights, then finds the first row on screen by searching those starts with the scroll offset.
When you have to own it
Now the list is a chat transcript with messages of different heights, and your own component renders only what is on screen. Keep the top of every message as the heights before it added up. A scroll then needs two searches over those tops, one for the first message in view and one for the last, instead of adding up thousands of heights. When an image loads and a message grows, every top after it moves, so rebuild the totals from the new list, or reach for a Fenwick tree if heights change constantly.
The running totals behind a cumulative spend chart. Built once per data change; the spend in any brushed range is two lookups and a subtraction.
import { useMemo } from 'react';
type Day = { date: string; spentCents: number };
export function SpendBetween({ days, from, to }: { days: Day[]; from: number; to: number }) {
// The running totals behind a cumulative spend chart, with a zero in front:
// totals[i] is everything spent before day i.
const totals = useMemo(() => {
const running = [0];
for (const day of days) running.push(running[running.length - 1] + day.spentCents);
return running;
}, [days]);
// Spent from day `from` through day `to`, inclusive: two lookups and one subtraction,
// however wide the range someone brushes on the chart.
const spent = totals[to + 1] - totals[from];
return (
<p>
{(spent / 100).toFixed(2)} spent from {days[from].date} to {days[to].date}
</p>
);
}
08 / Make the call
Ask what the input promises.
Reach for two pointers when the values are sorted and a move in one direction only raises the sum while the other only lowers it: pairs that meet a target, or a partition around a value. Reach for prefix sums when the sequence stays put and many questions ask for contiguous totals.
Look elsewhere when the question changes. A handful of short ranges: scan them. Values that change often: a Fenwick or segment tree. One contiguous range that moves with the data and grows or shrinks under a rule: a sliding window. A pair in unsorted data you would rather not sort: a hash set of the values seen so far.
09 / Take the idea with you
Explain it without saying “two pointers” or “prefix sums.”
“The prices are in order, so I start with the cheapest and the dearest. Too much, and I drop the dearest; too little, and I drop the cheapest. For totals, I write down how much I have added up before each position, once, and any stretch is the later number minus the earlier one.” That describes the mechanism. The names are what you call it in a review.
Before moving on, explain three things without the names: why 17 could be ruled out after one sum, why the prefix array starts with a zero, and why a single range question does not repay the preparation. Then find a loop in your own code that adds up a stretch of numbers every time someone asks, and decide whether the numbers change more often than they are asked about.
Connections to follow nextRelated lessons
- Sliding window keeps one moving range and its running summary instead of answering separate ranges.
- Binary search uses the same sortedness to discard half of what is left, and finds a row among prefix sums.
- Sorting is the setup two pointers depend on, and its merge walks two pointers of its own.