Running Sum of 1D Array — Prefix Sum Foundation at Amazon and Adobe

Problem Statement#

Given an array nums, return an array runningSum where runningSum[i] = nums[0] + nums[1] + ... + nums[i].

Constraints:

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

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

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

Why This Problem Matters#

LeetCode 1480 Running Sum of 1D Array is the simplest possible introduction to the prefix sum technique. Amazon, Adobe, and Meta use it as a 5 minute phone screen opener before pivoting to a harder range query or subarray sum problem.

The technique generalizes immediately to LC 303 Range Sum Query Immutable, LC 560 Subarray Sum Equals K, LC 974 Subarray Sums Divisible by K, and LC 1109 Corporate Flight Bookings. Every prefix sum problem starts with the same one-line accumulator that this problem teaches.

The interview value is in showing that you can write the in-place version (no auxiliary array) and that you understand the relationship between prefix sums and range queries.

The Core Insight#

A prefix sum is a cumulative running total. prefix[i] equals the sum of the first i + 1 elements. The recurrence prefix[i] = prefix[i - 1] + nums[i] lets us build the array in a single pass.

The in-place version overwrites nums itself: nums[i] += nums[i - 1] for i >= 1. This uses O(1) extra space beyond the output, which is what interviewers prefer when memory is tight.

Once a prefix sum array exists, the sum of any contiguous range [l, r] is prefix[r] - prefix[l - 1], achieving O(1) range queries.

Visual Dry Run#

For nums = [3, 1, 2, 10, 1]:

Solution (Optimal)#

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

var runningSum = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
};

Time: O(n) — single pass Space: O(1) — in-place modification

Common Mistakes#

• Allocating a new array of size n when the in-place version is allowed
• Starting the loop at i = 0 and accessing nums[-1], which is the last element in Python or undefined in JavaScript
• Using a nested loop that recomputes the sum from index 0 each step, costing O(n^2)
• Forgetting to return nums in languages where the function signature requires a return value
• Confusing the prefix sum convention with off-by-one (some authors define prefix[0] = 0)

Interview Tips#

• Say "prefix sum" out loud and mention that this is the foundation for range queries
• Offer the LC 303 follow-up unprompted: "Once we have this array, range sum is one subtraction"
• Show the in-place version even when the interviewer does not request it; it demonstrates pattern fluency
• Mention that the convention prefix[0] = 0 and prefix[i] = sum(nums[0..i-1]) is more common in interviews because it simplifies range queries

Follow-up Questions#

• How do you answer many range sum queries on an immutable array? (Hint: LC 303, prefix sum array)
• What if updates are allowed? (Hint: LC 307, Fenwick tree or segment tree)
• How do you count subarrays with sum equal to k? (Hint: LC 560, prefix sum and hash map)
• How would you do this in 2D? (Hint: LC 304, 2D prefix sum)
• What about subarray sums divisible by k? (Hint: LC 974, prefix sum modulo k)

Key Takeaways#

• LeetCode 1480 Running Sum of 1D Array is the prefix sum primer
• The recurrence prefix[i] = prefix[i - 1] + nums[i] builds the array in one pass
• In-place version uses O(1) extra space and is preferred in interviews
• Once built, range sum queries are O(1) using prefix[r] - prefix[l - 1]
• Pattern extends directly to LC 303, LC 304, LC 307, LC 560, LC 974, and LC 1109
• Amazon, Adobe, and Meta use this as a 5 minute warm-up before harder prefix sum problems
• Avoid the O(n^2) inner loop; recomputing prefixes is the most common mistake