Skip to content
Hello Python

Build Prefix Aggregates

Practice ExerciseInterviewEasyPrefix Sum

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement build_prefix_aggregates(values). Return a list of length len(values) + 1 whose first entry is 0 and whose entry at i + 1 equals the sum of values through index i. Do not mutate values.

Starter code

def build_prefix_aggregates(values):
    pass
Test cases

mixed-values

{
  "args": [
    [
      3,
      -1,
      4,
      2
    ]
  ]
}

Expected: [0,3,2,6,8]

single-value

{
  "args": [
    [
      7
    ]
  ]
}

Expected: [0,7]

Wizard outline
  1. Step 1: Seed the empty-prefix sum

    Create state 0 with aggregate value 0. Every later prefix extends a valid earlier prefix, so the empty prefix is the recurrence base.

  2. Step 2: Extend one prefix

    Append the first value to the base aggregate. A one-value input exposes the recurrence prefix[-1] + value without loop complexity.

  3. Step 3: Extend every prefix

    Apply the same recurrence from left to right for positive and negative values. The recurrence is local and does not change when the running total decreases.

Footguns and prerequisites
  • Omitting the leading zero makes half-open range formulas require special cases.
  • Appending the current value instead of cumulative total produces a copy, not prefix aggregates.
  • arrays strings two pointers sliding window
Reviewed references
Prepared Interview Problems
  • Binary Subarrays With Sum(opens in a new tab)

    Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing binary subarrays with sum as a complete Interview Problem.

  • Friends of Appropriate Ages(opens in a new tab)

    Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing friends appropriate ages as a complete Interview Problem.

  • Product Except Self(opens in a new tab)

    Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing product except self as a complete Interview Problem.

  • Resolve a Weighted Random Pick(opens in a new tab)

    Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing resolve weighted random pick as a complete Interview Problem.

Recommended approach and implementation

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.

Why it works: 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.

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