Running Sum of 1d Array

Easy
187.

Running Sum of 1d Array

EasyArrayPrefix SumAmazonMicrosoftAccenture

Running Sum of 1d Array is an easy coding problem on arrays and prefix sum, asked in Amazon, Microsoft and Accenture interviews.

Given an array nums, the running sum is defined as runningSum[i] = sum(nums[0] … nums[i]).

Return the running sum of nums.

Example 1

Input
nums = [1,2,3,4]
Output
[1,3,6,10]
Explanation
[1, 1+2, 1+2+3, 1+2+3+4].

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 <= 40
  • -1000 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var runningSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Running Sum of 1d Array — Solution in Python, Java & C++

Running Sum of 1d Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Running Sum of 1d Array is an easy coding problem on arrays and prefix sum, asked in Amazon, Microsoft and Accenture interviews.

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Microsoft, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array nums, the running sum is defined as runningSum[i] = sum(nums[0] … nums[i]).

Return the running sum of nums.

Example 1

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

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 <= 40
  • -1000 <= nums[i] <= 1000

Hints for Running Sum of 1d Array

  1. Hint 1

    Each answer is the previous answer plus the current element — one pass, one accumulator.

  2. Hint 2

    You can also write the result in place, since position i only ever reads position i - 1.

How to solve Running Sum of 1d Array

Each prefix sum is the previous prefix sum plus the current element — one accumulator, one pass.

Approach

  1. Start total = 0.
  2. For each x, add it to total and append total.

Why it works

runningSum[i] = runningSum[i - 1] + nums[i] by definition, so a single accumulator carries all the needed state.

Complexity

  • Time — O(n)
  • Space — O(n) for the output (O(1) if done in place)

Pitfalls

  • Recomputing each prefix from scratch is O(n²).

Reference solution

Python

def runningSum(nums):
    out = []
    total = 0
    for x in nums:
        total += x
        out.append(total)
    return out

Java

public static int[] runningSum(int[] nums) {
    int[] out = new int[nums.length];
    int total = 0;
    for (int i = 0; i < nums.length; i++) {
        total += nums[i];
        out[i] = total;
    }
    return out;
}

C++

vector<int> runningSum(vector<int>& nums) {
    vector<int> out;
    int total = 0;
    for (int x : nums) {
        total += x;
        out.push_back(total);
    }
    return out;
}

JavaScript

var runningSum = function(nums) {
    const out = [];
    let total = 0;
    for (let i = 0; i < nums.length; i++) {
        total += nums[i];
        out.push(total);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum