Problem

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Examples

Example 1

1
2
3

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2

1
2
3

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3

1
2

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints

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

Solution

Method 1 - Prefix Sum

Intuition

The running sum is a prefix sum: each element is the sum of all previous elements plus itself. We can compute this in a single pass.

Approach

  1. Initialize a result array.
  2. Iterate through nums, keep a running total, and append it to the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
using namespace std;
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> res;
        int sum = 0;
        for (int x : nums) {
            sum += x;
            res.push_back(sum);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9

func runningSum(nums []int) []int {
    res := make([]int, len(nums))
    sum := 0
    for i, x := range nums {
        sum += x
        res[i] = sum
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] runningSum(int[] nums) {
        int[] res = new int[nums.length];
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            res[i] = sum;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun runningSum(nums: IntArray): IntArray {
        val res = IntArray(nums.size)
        var sum = 0
        for (i in nums.indices) {
            sum += nums[i]
            res[i] = sum
        }
        return res
    }
}
1
2
3
4
5
6
7

def runningSum(nums):
    res = []
    s = 0
    for x in nums:
        s += x
        res.append(s)
    return res
1
2
3
4
5
6
7
8
9

pub fn running_sum(nums: Vec<i32>) -> Vec<i32> {
    let mut res = Vec::with_capacity(nums.len());
    let mut sum = 0;
    for x in nums {
        sum += x;
        res.push(sum);
    }
    res
}
1
2
3
4
5
6
7
8
9

function runningSum(nums: number[]): number[] {
    const res: number[] = [];
    let sum = 0;
    for (const x of nums) {
        sum += x;
        res.push(sum);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)