Module 06 · Prefix Sums, Prefix State, and Difference Arrays

051. Build a Prefix-Sum Array

Foundation · Download this solution · All solutions and shared helpers

Problem

Build a boundary-based prefix-sum list for integers nums. Return n+1 values with prefix[0]=0 and prefix[i] equal to sum(nums[:i]). The extra leading zero represents the empty prefix; do not mutate the input.

Examples

Example 1

prefix_sums([2, -1, 3, 4])
=> [0, 2, 1, 4, 8]

The leading zero belongs to boundary zero.

Example 2

prefix_sums([])
=> [0]

Even an empty array has one boundary.

Example 3

prefix_sums([5])
=> [0, 5]

A singleton has two boundaries.

Reveal the worked solution and reasoning

Why this mechanism works

Attach sums to boundaries between cells rather than to cells themselves. Then every half-open range [left,right) has the uniform expression prefix[right]-prefix[left], including ranges starting at zero. The leading zero removes a special case from every later query.

State and boundaries

prefix has one entry for each processed boundary. Its last value is the sum of all consumed elements.

Protocol

Start prefix with zero.
For each value append prefix[-1]+value.
Return the complete boundary array.

Visualization

cells:       2   -1    3    4
boundaries: 0    1    2    3    4
prefix:     0    2    1    4    8

Python implementation

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

prefix_sums([2, -1, 3, 4])

L2 prefix_sums: prefix = [0]
nums=[2, -1, 3, 4]; prefix=[0]

L3 prefix_sums: for value in nums:
nums=[2, -1, 3, 4]; prefix=[0]; value=2

L4 prefix_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; prefix=[0, 2]; value=2

L3 prefix_sums: for value in nums:
nums=[2, -1, 3, 4]; prefix=[0, 2]; value=-1

L4 prefix_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; prefix=[0, 2, 1]; value=-1

L3 prefix_sums: for value in nums:
nums=[2, -1, 3, 4]; prefix=[0, 2, 1]; value=3

L4 prefix_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; prefix=[0, 2, 1, 4]; value=3

L3 prefix_sums: for value in nums:
nums=[2, -1, 3, 4]; prefix=[0, 2, 1, 4]; value=4

L4 prefix_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; prefix=[0, 2, 1, 4, 8]; value=4

Result: [0, 2, 1, 4, 8]. The leading zero belongs to boundary zero.

prefix_sums([])

L2 prefix_sums: prefix = [0]
nums=[]; prefix=[0]

Result: [0]. Even an empty array has one boundary.

Why the solution is correct

The zero entry correctly represents no elements. Each append extends the preceding prefix by one value, establishing the next boundary sum. Induction gives the required meaning at every index.

Time and space

O(n) time and O(n) returned space.

Common mistakes

Returning n rather than n+1 entries mixes cell-based and boundary-based definitions. Negative numbers do not invalidate prefix subtraction.

Reasoning card

State: prefix has one entry for each processed boundary. Its last value is the sum of all consumed elements.

Invariant: prefix[i] is the sum of the first i elements.

Decision to rehearse: Define whether the current element is included before or after each boundary.

Finish: Return the complete boundary array

Transfer exercise

Build prefix counts of odd values by replacing each incoming integer with its Boolean oddness.