Skip to content
Hello Python
Pattern1 Practice5 Interview

Prefix Sum

Precompute cumulative aggregates so range queries become constant-time differences. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Prefix Sum when the prompt's constraints and required operations match this shape: Precompute cumulative aggregates so range queries become constant-time differences.

Pybit demonstrates the Prefix Sum decision pattern in a professional coding interview workspace.
On this page · Store Work at Every Boundary

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Prefix Sum Code Labs

Store Work at Every Boundary

prefix[i] stores the aggregate of the first i values. The leading identity at boundary zero describes the empty prefix and makes every input position correspond to the gap immediately after it.

Use Half-Open Prefixes

A half-open range [left, right) has sum prefix[right] - prefix[left]. This single formula covers empty ranges and ranges beginning at zero, avoiding left - 1 branches and off-by-one special cases.

Build Prefix Boundaries

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

Implement build_prefix_aggregates(values). Return length n + 1 with prefix[0] = 0 and prefix[i + 1] including values[i].

Public tests

  • Keep the empty boundary

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Turn Subarrays into Differences

Two boundaries summarize any immutable subarray in O(1). For target-sum counting, rearrange current_prefix - earlier_prefix = target and store frequencies of earlier prefixes in a hash map.

Answer Range Sum Queries

Reference
def range_sum_queries(values, queries):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return [prefix[right] - prefix[left] for left, right in queries]
Practice

Implement range_sum_queries(values, queries). Each query is a half-open [left, right] range. Return its sum.

Public tests

  • Subtract half-open boundaries

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Prefix Sums or a Window

Use prefix sums for many immutable range queries, arbitrary signed values, or prefix-frequency equations. Use a sliding window when validity changes monotonically as a contiguous boundary moves. Building prefixes costs O(n) time and space; each direct range query is O(1).

Explain It in an Interview

Say: “prefix[i] is the sum before index i, so subtracting two boundaries cancels everything outside the range.” Trace a range beginning at zero and an empty range. Binary Subarrays With Sum(opens in a new tab) adds a frequency map to the same difference identity.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Prefix Sum invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Prefix Sum decision loopO(n)O(n)Repeated range totals become simple differences when one cumulative boundary value is stored before every input position. After consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries.

Space

O(n) for the focused Build Prefix Aggregates implementation.

Assumptions

  • The initial zero is the sum of the empty prefix. Appending the previous aggregate plus the next value produces the next prefix sum, so every returned position has the required cumulative total.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise Prefix Sum invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. prefix[i] summarizes exactly the first i values.
  3. The leading identity entry removes the left-boundary special case.
  4. Repeated range totals become simple differences when one cumulative boundary value is stored before every input position. Preserve this property after every transition.
  5. After consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. Preserve this property after every transition.

When To Use Or Avoid Prefix Sum

Use It When

  • Use Prefix Sum when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when prefix[i] summarizes exactly the first i values.

Choose Another Tool When

  • Avoid Prefix Sum when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Build Prefix Aggregates before optimizing.

Avoid

def build_prefix_aggregates(values):
    pass

Use instead

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

Where you will hit this: Build Prefix Aggregates(opens in a new tab)

Breaking the maintained state

Omits the leading zero boundary, shifting every range endpoint and returning the wrong required length.

Prevent it: Use the public tests and preserve this state: prefix[i] summarizes exactly the first i values.

Avoid

def build_prefix_aggregates(values):
    prefix = []
    total = 0
    for value in values:
        total += value
        prefix.append(total)
    return prefix

Use instead

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

Where you will hit this: Build Prefix Aggregates(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).

Avoid

def build_prefix_aggregates(values):
    prefix = []
    total = 0
    for value in values:
        total += value
        prefix.append(total)
    return prefix

Use instead

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

Where you will hit this: Binary Subarrays With Sum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.