Running Sum of 1D Array (LC 1480) — Prefix Sum Foundation [Amazon Easy]

Problem Statement#

Given an array of integers nums, compute the running sum of the array. The running sum of an index i is defined as runningSum[i] = sum(nums[0] + nums[1] + ... + 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, 2, 10, 1]
Output: [3, 4, 6, 16, 17]

Constraints:

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

Why This Problem Matters#

LeetCode 1480 is classified as Easy, and you can solve it in one line of Python. But dismissing it as trivial is a mistake. This problem is the entry point to the prefix sum pattern — a technique that underlies hundreds of medium and hard problems at every major tech company.

When an Amazon interviewer asks you this problem, they are watching for two things. First, can you produce the correct solution quickly? (If it takes more than two minutes, that is a red flag.) Second — and this is the part that actually matters — can you explain why you would ever want to precompute prefix sums in the first place?

The answer: prefix sums convert a repeated O(n) range query into an O(1) lookup. If you need to answer ten thousand queries of the form "what is the sum of nums[l..r]?" you have two options: brute force every query in O(n) time for O(n * Q) total, or spend O(n) once to build the prefix sum array and then answer every query in O(1) for O(n + Q) total. When Q is large, this difference is enormous.

That insight — precompute once, query many — shows up in sliding window problems, 2D matrix queries, subarray problems (LC 560 — Subarray Sum Equals K is pure prefix sums + hashmap), and even in data warehouse systems where column-store aggregations are essentially prefix sum lookups over sorted data. Understanding LeetCode 1480 deeply means understanding all of those.

Beyond the follow-up questions, this problem is also a clean introduction to in-place transformation: modifying the input array itself rather than allocating a new result array. The in-place approach uses O(1) extra space, and recognizing when in-place is safe (and when it is not) is a frequently tested skill.

The Prefix Sum Insight#

The definition is straightforward: prefix[i] = nums[0] + nums[1] + ... + nums[i].

The key observation is that you can compute prefix[i] from prefix[i-1] with a single addition:

prefix[i] = prefix[i-1] + nums[i]

This recurrence is what makes the whole pattern work. You do not need to sum from scratch for every index — you simply add the current element to the accumulated total you already have. That is an O(1) operation per element, so the entire prefix array is built in O(n) time.

Once built, you can answer any range sum query sum(nums[l..r]) as:

range_sum(l, r) = prefix[r] - prefix[l - 1]

(Using a 1-indexed prefix array, or equivalently prefix[r+1] - prefix[l] if you add a leading zero.)

For LeetCode 1480 specifically, the output is the prefix sum array — so the range query power is the bonus, not the goal. But understanding it is what separates a candidate who "just solved 1480" from one who understands a pattern.

Two implementation styles:

1. Extra array: Allocate a new result array, fill it using the recurrence. Space: O(n). Does not mutate the original input — important when the caller needs nums unchanged.
2. In-place: Overwrite nums[i] with the running total directly. Space: O(1). Destroys the original input — only safe if the caller does not need the original values again.

Both approaches have O(n) time. The in-place approach is preferred in interviews unless the problem explicitly requires preserving the input.

Visual Dry Run#

Let us trace through nums = [1, 2, 3, 4] step by step using the in-place approach.

Initial state:

Index:  0   1   2   3
nums:  [1,  2,  3,  4]

Iteration starts at index 1 (index 0 is already its own running sum — nothing to add).

Step 1 — i = 1:

nums[1] = nums[1] + nums[0]
        = 2 + 1
        = 3
 
Array:  [1,  3,  3,  4]

Step 2 — i = 2:

nums[2] = nums[2] + nums[1]
        = 3 + 3         ← nums[1] is already updated to 3 (the running sum, not the original 2)
        = 6
 
Array:  [1,  3,  6,  4]

Step 3 — i = 3:

nums[3] = nums[3] + nums[2]
        = 4 + 6
        = 10
 
Array:  [1,  3,  6,  10]

Output: [1, 3, 6, 10] — correct.

Notice the critical detail in Step 2: when we compute nums[2], we use nums[1] — which is already updated to 3 (the running sum up to index 1), not the original 2. This is why the in-place approach works correctly: each nums[i-1] already holds prefix[i-1] by the time we need it.

If instead we had written nums[i] = nums[i] + nums[i-1] while nums[i-1] still held the original value, the calculation would be wrong. The left-to-right traversal order is what guarantees the invariant holds.

Now trace the extra-array approach on nums = [3, 1, 2, 10, 1]:

prefix = [0, 0, 0, 0, 0]   ← same length as nums
 
i=0: prefix[0] = nums[0] = 3
     prefix = [3, 0, 0, 0, 0]
 
i=1: prefix[1] = prefix[0] + nums[1] = 3 + 1 = 4
     prefix = [3, 4, 0, 0, 0]
 
i=2: prefix[2] = prefix[1] + nums[2] = 4 + 2 = 6
     prefix = [3, 4, 6, 0, 0]
 
i=3: prefix[3] = prefix[2] + nums[3] = 6 + 10 = 16
     prefix = [3, 4, 6, 16, 0]
 
i=4: prefix[4] = prefix[3] + nums[4] = 16 + 1 = 17
     prefix = [3, 4, 6, 16, 17]
 
Output: [3, 4, 6, 16, 17]   ✓

Here nums is untouched throughout — useful when the caller needs the original array for something else.

Common Mistakes#

Mistake 1: Starting the loop at index 0 instead of index 1#

The most frequent off-by-one error: writing for i in range(len(nums)) (Python) or for (let i = 0; ...) (JavaScript) and then trying to access nums[i-1] when i = 0. This causes an index-out-of-bounds crash or silently reads nums[-1] in Python (which wraps around to the last element — a subtle and nasty bug).

The fix is simple: start the loop at index 1. nums[0] is already its own running sum: sum(nums[0..0]) = nums[0]. No modification needed.

# WRONG — crashes or gives wrong result
for i in range(len(nums)):
    nums[i] += nums[i - 1]   # when i=0, nums[-1] is the LAST element in Python!
 
# CORRECT
for i in range(1, len(nums)):
    nums[i] += nums[i - 1]

Mistake 2: Reading stale values in the extra-array approach#

When building a separate prefix array, candidates sometimes write:

# WRONG — reads original nums[i-1], not prefix[i-1]
for i in range(1, len(nums)):
    prefix[i] = prefix[i - 1] + nums[i - 1]   # BUG: this adds nums[i-1], not prefix[i-1]

The correct formula is prefix[i] = prefix[i-1] + nums[i] — add the current original element to the previous prefix. The recurrence is prefix[i] = prefix[i-1] + nums[i], not prefix[i-1] + nums[i-1].

Mistake 3: Modifying the input when the caller needs it preserved#

The in-place approach is efficient, but it destroys the original nums. In a real codebase — and sometimes in an interview problem that reuses nums — this is a correctness bug. Always ask: "Does the caller need the original array after this call?" If the answer is yes, use the extra-array approach and return the new array without touching nums.

In an interview, stating this trade-off explicitly — even when the problem does not require it — signals strong engineering judgement.

Mistake 4: Using itertools.accumulate without understanding it#

Python's itertools.accumulate(nums) produces the prefix sums in one line. It is correct and idiomatic, but if you reach for it without being able to explain what it does internally, you are at risk of a follow-up like "how would you implement this without the standard library?" Know the manual implementation cold.

Mistake 5: Forgetting that prefix sums enable range queries#

After writing the solution, candidates often stop there. The real interview value of this problem is the follow-up: "Now that you have the prefix array, how would you answer sum(nums[l..r]) in O(1)?" If you cannot answer this immediately, you have missed the point. The answer: prefix[r] - prefix[l-1] (with a sentinel prefix[-1] = 0 to handle l = 0).

Solutions#

Python#

from typing import List
import itertools
 
class Solution:
 
    # ──────────────────────────────────────────────────
    # Approach 1: In-place — O(n) time, O(1) extra space
    # ──────────────────────────────────────────────────
    def runningSum_inplace(self, nums: List[int]) -> List[int]:
        # nums[0] is already correct: sum(nums[0..0]) = nums[0]
        # Start from index 1 and accumulate left-to-right
        for i in range(1, len(nums)):
            # nums[i-1] already holds the running sum up to index i-1
            # Adding nums[i] (the current element) gives the running sum up to index i
            nums[i] += nums[i - 1]
 
        # Return the modified array (the caller now has the prefix sums)
        return nums
 
    # ──────────────────────────────────────────────────
    # Approach 2: Extra array — O(n) time, O(n) space
    # Preserves the original nums array
    # ──────────────────────────────────────────────────
    def runningSum_extra(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix = [0] * n          # allocate a fresh array of the same length
 
        prefix[0] = nums[0]       # base case: prefix sum of the first element is itself
 
        for i in range(1, n):
            # Each prefix[i] is the previous prefix sum plus the current original element
            prefix[i] = prefix[i - 1] + nums[i]
 
        # nums is untouched — safe to use again after this call
        return prefix
 
    # ──────────────────────────────────────────────────
    # Approach 3: Pythonic one-liner using itertools.accumulate
    # Same O(n) time, O(n) space — but idiomatic Python
    # ──────────────────────────────────────────────────
    def runningSum_accumulate(self, nums: List[int]) -> List[int]:
        # itertools.accumulate applies a binary function cumulatively
        # Default function is addition, which is exactly what we want
        # accumulate([1, 2, 3, 4]) yields 1, 3, 6, 10
        return list(itertools.accumulate(nums))
 
    # ──────────────────────────────────────────────────
    # Bonus: range sum query using the prefix array
    # Shows WHY you would build a prefix array in the first place
    # ──────────────────────────────────────────────────
    def range_sum_query(self, nums: List[int], l: int, r: int) -> int:
        # Build prefix sums first — O(n) one-time cost
        prefix = self.runningSum_extra(nums)
 
        # Add a leading sentinel so that l=0 does not require a special case
        # prefix_with_sentinel[0] = 0, prefix_with_sentinel[i+1] = prefix[i]
        sentinel = [0] + prefix      # e.g. [0, 1, 3, 6, 10] for nums=[1,2,3,4]
 
        # sum(nums[l..r]) = sentinel[r+1] - sentinel[l]
        # This runs in O(1) — any range query after the one-time O(n) build
        return sentinel[r + 1] - sentinel[l]

JavaScript#

/**
 * LeetCode 1480 — Running Sum of 1d Array
 *
 * Approach 1: In-place (O(n) time, O(1) extra space)
 * Modifies the input array directly.
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function runningSum_inplace(nums) {
    // Index 0 is already its own running sum — nothing to do
    // Start the loop at index 1 and accumulate left-to-right
    for (let i = 1; i < nums.length; i++) {
        // nums[i - 1] already holds the running sum up to index i-1
        // Adding nums[i] gives the running sum up to index i
        nums[i] += nums[i - 1];
    }
 
    // Return the same (now modified) array
    return nums;
}
 
/**
 * Approach 2: Extra array (O(n) time, O(n) space)
 * Does NOT mutate the input — safe when the caller still needs the original nums.
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function runningSum_extra(nums) {
    const n = nums.length;
    const prefix = new Array(n);   // allocate a fresh array of the same length
 
    prefix[0] = nums[0];           // base case: sum of first element is itself
 
    for (let i = 1; i < n; i++) {
        // prefix[i-1] holds the accumulated sum through index i-1
        // Adding nums[i] (the current ORIGINAL element) gives the sum through index i
        prefix[i] = prefix[i - 1] + nums[i];
    }
 
    // nums is untouched — the original array is preserved
    return prefix;
}
 
/**
 * Approach 3: Functional one-liner using Array.reduce
 * Same O(n) time, O(n) space — idiomatic JavaScript.
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function runningSum_reduce(nums) {
    // reduce with an accumulator that tracks the running total
    // For each element, the running total becomes total + current,
    // and we push that new total into the result array
    const result = [];
    nums.reduce((runningTotal, current) => {
        const newTotal = runningTotal + current;   // add current element to accumulated sum
        result.push(newTotal);                     // record this running sum in the output
        return newTotal;                           // pass the new total to the next iteration
    }, 0);                                         // initial running total is 0
    return result;
}
 
/**
 * Bonus: Range sum query — demonstrates WHY you precompute prefix sums
 * O(n) build time, then O(1) per query.
 *
 * @param {number[]} nums
 * @param {number} l  - left index (inclusive)
 * @param {number} r  - right index (inclusive)
 * @return {number}
 */
function rangeSumQuery(nums, l, r) {
    // Build a sentinel-prefixed prefix array once
    // sentinel[0] = 0 removes the need for a special case when l = 0
    const sentinel = [0];
    for (let i = 0; i < nums.length; i++) {
        // Each position: accumulated sum from index 0 through index i
        sentinel.push(sentinel[sentinel.length - 1] + nums[i]);
    }
    // sentinel = [0, 1, 3, 6, 10] for nums = [1, 2, 3, 4]
 
    // Answer any range query in O(1) using prefix difference
    // sum(nums[l..r]) = sentinel[r+1] - sentinel[l]
    return sentinel[r + 1] - sentinel[l];
}

Complexity Analysis#

All four approaches share the same time complexity. The choice between them is purely about space and whether the original input needs to remain untouched. In an interview, state this trade-off explicitly — it shows you think beyond "just make it work."

Follow-up Questions#

Once you solve LeetCode 1480 in under two minutes, the interviewer will pivot to these follow-ups. These are the questions that actually gate the offer.

Follow-up 1: Range Sum Query — O(1) per query after O(n) build (LC 303)#

"Now that you have the prefix array, if I give you indices l and r, how do you find the sum of nums[l..r] in O(1) time?"

This is LeetCode 303 — Range Sum Query - Immutable. The answer uses the prefix array directly:

sum(nums[l..r]) = prefix[r] - prefix[l - 1]

Or with a sentinel zero at the front:

sentinel = [0] + prefix   # e.g. [0, 1, 3, 6, 10]
sum(nums[l..r]) = sentinel[r + 1] - sentinel[l]

The sentinel eliminates the edge case where l = 0 (no prefix[l-1] would exist). The range sum is the difference between two prefix values — a single subtraction, O(1).

Why this matters: If you have Q range queries, brute force costs O(n * Q). With the prefix array, it costs O(n + Q). When Q is one million and n is ten thousand, the difference is roughly 10 billion operations vs. 1.01 million — a factor of ten thousand.

Follow-up 2: Subarray Sum Equals K (LC 560)#

"How many contiguous subarrays of nums have a sum equal to exactly k?"

This is LeetCode 560, one of the most common medium problems at Amazon and Google. The naive approach — check every pair (l, r) — is O(n^2). The optimal approach combines prefix sums with a hash map and runs in O(n).

The insight: sum(nums[l..r]) = k is equivalent to prefix[r] - prefix[l-1] = k, which rearranges to prefix[l-1] = prefix[r] - k. As you iterate right to left building prefix sums, you want to know "how many times have I seen the value prefix[r] - k as a prefix sum before this point?" A hash map gives you that count in O(1).

def subarraySum(nums, k):
    count = 0
    running = 0
    freq = {0: 1}           # sentinel: prefix sum of 0 has been seen once (before index 0)
 
    for num in nums:
        running += num                           # build prefix sum incrementally
        count += freq.get(running - k, 0)       # how many prior prefixes allow a valid subarray?
        freq[running] = freq.get(running, 0) + 1  # record this prefix sum
 
    return count

Understanding LeetCode 1480 is a literal prerequisite for understanding this solution. The running variable here is the running sum from 1480.

Follow-up 3: 2D Matrix Prefix Sums (LC 304)#

"Extend the idea to a 2D matrix. How do you answer rectangle sum queries in O(1)?"

This is LeetCode 304 — Range Sum Query 2D - Immutable. The 2D prefix sum is defined as:

prefix2D[i][j] = sum of all elements in the rectangle
                 from (0, 0) to (i, j) inclusive

It is built using the 2D recurrence (the inclusion-exclusion principle):

prefix2D[i][j] = matrix[i][j]
               + prefix2D[i-1][j]
               + prefix2D[i][j-1]
               - prefix2D[i-1][j-1]

And a rectangle query from (r1, c1) to (r2, c2) is answered as:

rect_sum = prefix2D[r2][c2]
         - prefix2D[r1-1][c2]
         - prefix2D[r2][c1-1]
         + prefix2D[r1-1][c1-1]

This is the same inclusion-exclusion logic as the 1D case, extended to two dimensions. You cannot solve LC 304 without first internalizing LC 1480.

Follow-up 4: Product Array Without Division (LC 238)#

"What if instead of sums, you needed the running product? And you cannot use division?"

LeetCode 238 — Product of Array Except Self. The solution uses the same prefix-sweep idea but with two passes: a left-product sweep (identical in structure to the running sum), then a right-product sweep combined with the left-product. Recognizing that LC 238 is "prefix sum but with multiplication" is only possible if you have internalized the prefix sum pattern from LC 1480.

This Pattern Solves#

The general shape: precompute a prefix structure in O(n), then answer each query in O(1) using the structure. Once you see this pattern in LeetCode 1480, you will recognize it immediately across all of these problems.

Key Takeaways#

• LeetCode 1480 — Running Sum of 1D Array is an Easy problem asked at Amazon; it introduces the prefix sum pattern that powers dozens of harder problems.
• Recurrence: prefix[i] = prefix[i-1] + nums[i] — compute left-to-right in a single O(n) pass.
• In-place version overwrites the input array, achieving O(1) extra space; mention this explicitly when interviewers ask about space.
• Prefix sum enables O(1) range sum queries: sum(l, r) = prefix[r] - prefix[l-1] — this is the real value of the prefix array.
• The prefix array is the foundation for LC 303 (Range Sum Query), LC 560 (Subarray Sum Equals K), LC 304 (2D Range Sum), and LC 974 (Subarray Sums Divisible by K).
• Any "how many subarrays satisfy X?" or "sum of a rectangular region?" problem almost certainly uses prefix sums in the optimal solution.
• Solving this in under two minutes then volunteering the range query insight is what separates pattern-knowers from problem-memorizers in FAANG interviews.