Running Sum of 1D Array — Prefix Sum Foundation [Amazon Easy]

Problem Statement

Given nums, return running_sum where running_sum[i] = sum(nums[0..i]).

Input: [1,2,3,4] → [1,3,6,10] Input: [1,1,1,1,1] → [1,2,3,4,5]

Intuition
C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity: O(n) time, O(1) extra space

Intuition

Each element becomes the sum of itself and all previous elements. Do it in-place: nums[i] += nums[i-1].

C Solution

int* runningSum(int* nums, int n, int* rsz) {
    *rsz = n;
    for (int i = 1; i < n; i++) nums[i] += nums[i-1];
    return nums;
}

C++ Solution

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

Java Solution

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

JavaScript Solution

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

Python Solution

def runningSum(nums):
    for i in range(1, len(nums)): nums[i] += nums[i-1]
    return nums
    # Or: import itertools; return list(itertools.accumulate(nums))

Complexity: O(n) time, O(1) extra space

Why It Matters: Prefix sum enables O(1) range sum queries: sum(l..r) = prefix[r+1] - prefix[l]. Used in hundreds of FAANG problems.