Skip to main content
DSA patterns

Running Sum of 1d Array

easyPrefix sumTCSInfosysWipro

Problem statement

You're given an array of integers nums. Build a new array runningSum of the same length, where each position i holds the sum of every element from the start of nums up through index i, inclusive.

Examples

Example 1

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

Output: [1,3,6,10]

Explanation: Each value adds the next number in nums to the one before

Example 2

Input: nums = [1,1,1,1,1]

Output: [1,2,3,4,5]

Explanation: Every number is 1, so the running sum just counts upward:

Example 3

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

Output: [3,4,6,16,17]

Explanation: 3, then 3+1=4, then 4+2=6, then 6+10=16, then

Hints

Hint 1: runningSum[0] is always just nums[0] — there's nothing before it to add.

Approach

Optimal: Keep a running total

Intuition

Notice that each running sum only differs from the one right before it by a single new number. So there's no need to re-add everything from the start every time — just carry one running total forward, and add the next element to it as you go. That's what turns O(n²) worth of repeated additions into O(n): every number in nums gets added exactly once, ever.

Steps

  1. Start with total = 0 and an empty result list.
  2. For each number x in nums, in order:
    • Add x to total.
    • Append the new total to result.
  3. Return result.

Dry run

nums = [1, 2, 3, 4]

step nums[i] total before total after result[i]
0 1 0 1 1
1 2 1 3 3
2 3 3 6 6
3 4 6 10 10

Reading the last column top to bottom gives [1, 3, 6, 10] — the expected output. Each row only adds the one new number from nums to whatever total already was.

Edge cases: a single-element array returns that same element, since total only gets added to once. Negative numbers work exactly the same way — total can go up or down, and nothing about the loop needs to change for that.

Complexity

Time O(n) - each element of `nums` is added into the running total exactly once, no matter how far along the array you are.

Space O(1) - extra — one running total variable, beyond the output array.

class Solution:
    def runningSum(self, nums: list[int]) -> list[int]:
        result = []
        total = 0
        for x in nums:
            total += x
            result.append(total)
        return result


if __name__ == "__main__":
    print(Solution().runningSum([1, 2, 3, 4]))         # [1, 3, 6, 10]
    print(Solution().runningSum([1, 1, 1, 1, 1]))      # [1, 2, 3, 4, 5]
    print(Solution().runningSum([3, 1, 2, 10, 1]))     # [3, 4, 6, 16, 17]
RecapThe whole problem in a few lines, for the night before
  • Spot it: output[i] is the sum of nums[0..i]
  • Idea: one pass, each element becomes itself plus the previous running total
  • Cost: O(n) time, O(1) extra space if done in place
  • Trap: this is the base prefix-sum array; later problems reuse it to answer range sums fast

Interview follow-ups

  • What if you needed the sum of an arbitrary range [l, r], not just from the start?

    Compute this same running sum once, up front, in O(n). Then any range sum is just one subtraction: runningSum[r] - runningSum[l - 1] (using 0 in place of runningSum[l - 1] when l is 0). That turns every future range query into O(1) after the one-time O(n) setup — this is exactly the idea behind Range Sum Query - Immutable.

  • nums can change over time, and you need the running sum to stay current. What changes?

    Recomputing the whole running sum after every update costs O(n) each time. A Fenwick tree (binary indexed tree) supports both "update one value" and "sum of a prefix" in O(log n) each, which is worth reaching for once updates happen often.

  • Could you compute this without allocating a new array?

    Yes — since result[i] only ever needs result[i - 1] (which has already been computed) and nums[i], you can update nums in place: nums[i] += nums[i - 1] for each i from 1 onward. That drops the extra O(n) output array down to O(1) extra space, at the cost of overwriting the original input.

Frequently asked questions

Each value in the output is the sum of a prefix of the array — everything from the very start up to some index. This running-sum array is the standard building block behind range-sum queries: once you have it, you can answer "what's the sum between any two indices?" without adding anything up again.

That's exactly what the brute-force approach does under the hood — it's correct, but it re-adds almost the same numbers for every single position, which is why it costs O(n²) instead of O(n).

It's the base case for any "total so far" metric — cumulative bytes transferred over a session, cumulative deploys so far this month, a running total of retries across a batch job. Anywhere you'd plot a cumulative line on a dashboard, this is the calculation behind it.

The simple loop here is sequential, since each total depends on the one before it. At a larger scale, though, this exact operation — called an "inclusive scan" — does have well-known parallel algorithms that split the array into chunks, sum each chunk independently, and then combine the chunk totals; that's how large-scale data-processing systems compute running sums across many machines at once.