Coding problem · Easy · Basics

Running Sum

Easy Algorithms & data structures

Return an array where element i is the sum of nums[0] through nums[i].

Example 1

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

Example 2

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

Hints

Hint 1

Keep a running total and append it after adding each number.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

One pass with an accumulator. This is the same idea as prefix sums, which later make range-sum questions O(1).

Reference solution

function runningSum(nums) {
  const out = [];
  let total = 0;
  for (const n of nums) out.push((total += n));
  return out;
}

function runningSum(nums: number[]): number[] {
  const out: number[] = [];
  let total = 0;
  for (const n of nums) out.push((total += n));
  return out;
}

def running_sum(nums: list[int]) -> list[int]:
    out, total = [], 0
    for n in nums:
        total += n
        out.append(total)
    return out

<?php

function runningSum(array $nums): array
{
    $out = [];
    $total = 0;
    foreach ($nums as $n) {
        $total += $n;
        $out[] = $total;
    }
    return $out;
}

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

Was this page helpful?