1480 - Running Sum of 1d Array

Difficulty: Easy | Pattern: Prefix Sum | Company tags: Amazon, Google

Problem Statement

Given an array nums, return the running sum of nums.

The running sum (also called prefix sum) of an array is defined as runningSum[i] = sum(nums[0]...nums[i]).

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]

Example 3:

Input: nums = [3,1,4,1,5,9,2,6]
Output: [3,4,8,9,14,23,25,31]

Solution: In-Place — O(n), O(1)

def runningSum(nums: list[int]) -> list[int]:
    for i in range(1, len(nums)):
        nums[i] += nums[i-1]
    return nums

Or creating a new array (if you shouldn't modify input):

def runningSum(nums: list[int]) -> list[int]:
    result = []
    total = 0
    for n in nums:
        total += n
        result.append(total)
    return result

Python One-Liner

import itertools

def runningSum(nums: list[int]) -> list[int]:
    return list(itertools.accumulate(nums))

itertools.accumulate computes prefix sums by default.

Dry Run

nums = [1,2,3,4]

i	nums[i] before	nums[i-1]	nums[i] after
1	2	1	3
2	3	3	6
3	4	6	10

Output: [1,3,6,10] ✓

Why Prefix Sums Matter

This is the simplest version of a prefix sum array. The technique extends to:

• Range sum queries in O(1): sum(i, j) = prefix[j] - prefix[i-1]
• LeetCode 560 (Subarray Sum Equals K)
• LeetCode 238 (Product of Array Except Self)

Algorithm Flow

Complexity

• Time: O(n)
• Space: O(1) in-place (or O(n) if creating new array)

Key Terms

Term	Definition
Prefix sum	Array where index i holds the sum of all elements from index 0 to i.
Running total	An accumulator variable updated incrementally as the array is traversed.
In-place mutation	Modifying the input array directly instead of allocating a new one, saving O(n) space.
Range sum query	Computing sum(i, j) in O(1) using prefix[j] - prefix[i-1] once prefix sums are precomputed.

FAQ

Q: Can this be solved without extra space? A: Yes — update nums in place (nums[i] += nums[i-1]), giving O(1) extra space since no new array is allocated.

Q: What if the input array is empty? A: The loop simply doesn't execute and an empty array is returned; no special-casing is needed since range(1, 0) is empty.

Q: What if the input has only one element? A: The running sum is just [nums[0]] — the loop starting at index 1 never runs, so the single value is returned unchanged.

Q: How would this extend to answering many range-sum queries efficiently? A: Precompute the prefix sum array once in O(n), then each sum(i, j) query becomes O(1) via prefix[j] - prefix[i-1] instead of re-summing the range each time.

Q: Does the order of operations matter if we can't mutate the input? A: If the input must stay unmodified, use a separate result array or itertools.accumulate, which returns a new iterable rather than touching the original list.

Quick Revision

• Running sum at index i = sum of all elements from 0 to i.
• In-place approach: nums[i] += nums[i-1] for i from 1 to n-1.
• Alternative: accumulate into a new result array with a running total.
• itertools.accumulate(nums) gives the same result as a one-liner.
• No extra space needed if in-place mutation of input is allowed.
• Time: O(n) single pass; Space: O(1) in-place or O(n) for a new array.
• This is the base case of the general prefix-sum technique used in range-query problems.
• Prefix sums let you answer sum(i, j) in O(1) after O(n) preprocessing.

Related Problems

• 560 - Subarray Sum Equals K — uses prefix sums with a hash map to count subarrays with a target sum.
• 238 - Product of Array Except Self — same prefix/suffix accumulation idea applied to products instead of sums.
• Related pattern: any range-sum or range-update problem (e.g., difference arrays) builds directly on this prefix sum foundation.