Running Sum of 1d Array

easy array prefix sum

Problem

Return the running sum of nums: out[i] = nums[0] + nums[1] + … + nums[i].

Inputnums = [1,2,3,4]

Output[1,3,6,10]

Each entry = sum of all preceding plus current.

nums

def running_sum(nums):
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return nums

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

class Solution {
    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) nums[i] += nums[i - 1];
        return nums;
    }
}

vector runningSum(vector& nums) {
    for (int i = 1; i < (int)nums.size(); i++) nums[i] += nums[i - 1];
    return nums;
}

Explanation

A running sum means each position should hold the total of everything up to and including it. The neat idea here is to build this in place: each number just adds the number sitting to its left, which already carries the full total so far.

We start the loop at i = 1 and do nums[i] += nums[i-1]. Index 0 is left alone because nothing comes before it. Each later cell folds in the cumulative value already stored just before it.

Why it works: by the time we reach index i, nums[i-1] has already been turned into the running total of indices 0..i-1. Adding the original nums[i] on top gives the running total through i.

Example: [1,2,3,4]. Index 1 becomes 2+1=3, index 2 becomes 3+3=6, index 3 becomes 4+6=10, giving [1,3,6,10].

It is a single pass, O(n) time, and uses O(1) extra space since we reuse the input array itself.

Time: O(n) Space: O(1)