Prefix sums, two pointers and sliding windows

After this page, you should be able to:

• Connect prefix totals, sorted endpoint elimination and fixed-window updates to invariants.

• Specify boundaries, duplicate positions, numeric assumptions and time/space costs.

Builds on: Array indexing, ordered-search exclusion and analysis conventions.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

State definitions, pruning conditions and tie policies are shared. Julia returns one-based position tuples/subsets, and its coin table uses slot a+1 for amount a. The finite numeric examples require representable intermediate arithmetic in each runtime.

Precompute repeated range totals¶

Let prefix[i] be the sum of the first i values, so prefix[0] = 0. The sum of half-open range [left,right) is prefix[right] - prefix[left].

def prefix_sums(values):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix

function prefix_sums(values) {
    const prefix = [0]; for (const value of values) prefix.push(prefix.at(-1) + value);
    return prefix;
}

function prefix_sums(values)
    prefix = Any[0]
    for value in values; push!(prefix, prefix[end] + value); end
    return prefix
end

For [3,1,4,2], prefixes are [0,3,4,8,10]; indices [1,3) sum to 8-3=5. Building takes $O(n)$ time and storage; each valid bounded range query then takes constant time. Updates to the original values invalidate affected prefix totals. Dynamic range-query structures are a separate extension.

Use sorted order to eliminate one endpoint¶

def two_sum_sorted(values, target):
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None

function two_sum_sorted(values, target) {
    let left = 0, right = values.length - 1;
    while (left < right) {
        const total = values[left] + values[right];
        if (total === target) return [left,right];
        if (total < target) left++; else right--;
    }
    return null;
}

function two_sum_sorted(values, target)
    left, right = 1, length(values)
    while left < right
        total = values[left] + values[right]
        total == target && return (left,right)
        if total < target; left += 1; else; right -= 1; end
    end
    return nothing
end

The input must be ascending, with consistent numeric comparison and addition. A sum too small rules out the current left value with every remaining right value; a sum too large rules out the current right value with every remaining left value. Each step moves an endpoint, so time is $O(n)$ and auxiliary space is constant. Two equal values can be used if they occupy different positions.

Update a fixed window by removing and adding one value¶

def max_fixed_window_sum(values, k):
    if type(k) is not int or not 1 <= k <= len(values):
        raise ValueError("window size must be between 1 and input length")
    total = sum(values[i] for i in range(k))
    best = total
    for right in range(k, len(values)):
        total += values[right] - values[right - k]
        best = max(best, total)
    return best

function max_fixed_window_sum(values, k) {
    if (!Number.isSafeInteger(k) || k<1 || k>values.length) throw new RangeError("invalid window size");
    let total = 0; for (let i=0;i<k;i++) total += values[i];
    let best = total;
    for (let right=k;right<values.length;right++) {
        total += values[right] - values[right-k]; best = Math.max(best,total);
    }
    return best;
}

function max_fixed_window_sum(values, k)
    (k isa Int && 1 <= k <= length(values)) || throw(ArgumentError("invalid window size"))
    total = sum(values[i] for i in 1:k); best = total
    for right in k+1:length(values)
        total += values[right] - values[right-k]; best = max(best,total)
    end
    return best
end

Each iteration preserves the sum of the current k-item window. Negative numbers are allowed because the window size is fixed. Time is $O(n)$ and additional working space is $O(1)$ under the numeric word model; no sliced window lists are allocated.

State query boundaries and returned results¶

Arithmetic and comparisons must be consistent for the supplied numeric values. Prefix queries use 0≤left≤right≤n; an empty half-open range sums to zero. There is no separate checked query helper on this page: prefix[right]-prefix[left] assumes valid boundaries. The two-pointer result is one valid pair selected by its endpoint walk, not every pair or a promised smallest-index pair.

Negative values are permitted by all three shown algorithms, with sorted order additionally required for two-sum. A fixed window needs no positive-value monotonicity argument. Prefix totals are snapshots and must be rebuilt or appropriately updated after source values change.

Variable windows need an additional argument¶

A variable-size window seeking a target sum often relies on positivity or another monotone condition to know which endpoint to move. The fixed-window algorithm above needs no such claim. Do not transfer it to arbitrary constraints merely because both methods are called sliding windows.

Compare preprocessing, working state and output¶

Prefix construction uses amortised list append. Temporary backing storage during growth remains within linear peak additional storage. The two-pointer invariant eliminates the current left endpoint when even its largest remaining partner is too small, or the right endpoint when even its smallest remaining partner is too large. Each move shrinks the candidate interval.

For a fixed window, updating by outgoing/incoming values preserves its k-item total; best remembers the maximum seen. Initialising best from the first valid window, rather than zero, is essential when every window has a negative sum. Variable windows and dynamic range updates need additional algorithms and assumptions.

Check your understanding¶

Predict the result or justify the choice before opening the explanation.

1. For values [3,1,4,2], what is the sum of [1,3), and how many entries are in the prefix list?

2. For [-5,-2,-3] and k=2, what is the maximum fixed-window sum?

These patterns reuse array indexing, sorted-order exclusion and rolling-window policies. Next: Complexity limits.