Running Sum of 1d Array

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.

Constraints:

1 <= nums.length <= 1000
-10⁶ <= nums[i] <= 10⁶

Examples

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].

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].

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

Solution

This problem is a straightforward application of the prefix sum (or cumulative sum) concept. The running sum at each position is simply the sum of all elements from the beginning of the array up to that position.

Algorithm:

Create a result array of the same length as the input
Initialize the first element: result[0] = nums[0]
For each subsequent position i, calculate: result[i] = result[i-1] + nums[i]
Return the result array

Example walkthrough:

For nums = [1, 2, 3, 4]:

i=0: result[0] = 1
i=1: result[1] = result[0] + nums[1] = 1 + 2 = 3
i=2: result[2] = result[1] + nums[2] = 3 + 3 = 6
i=3: result[3] = result[2] + nums[3] = 6 + 4 = 10

Result: [1, 3, 6, 10]

Optimization: You can also modify the input array in-place to achieve O(1) space complexity (excluding the output):

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

Time Complexity: O(n) - single pass through the array Space Complexity: O(n) - for the result array (or O(1) if modifying in-place)

function runningSum(nums: number[]): number[] {
  const n = nums.length
  const result = new Array(n).fill(0)
  result[0] = nums[0]

  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] + nums[i]
  }

  return result
}

Problem​

Solution​

Problem

Solution