Running Sum of 1d Array

easyLeetCode #1480
prefix-sum

Description

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.

Example 1:
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:
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:
Input: nums = [3, 1, 2, 10, 1]
Output: [3, 4, 6, 16, 17]

Constraints

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

Signature

def solution(nums: list[int]) -> list[int]: ...

Complexity
  • Time: O(n)
  • Space: O(n)

Hints
Pattern
Prefix sum accumulation
Approach
Iterate through array, keep track of cumulative sum, store each intermediate sum
Complexity
Single pass through array, maintain running total

Solutions

def solution(nums):
    result = [nums[0]]

    for i in range(1, len(nums)):
        result.append(nums[i] + result[-1])

    return result