Running Sum of 1d Array — LeetCode 1480 Python Solution

The problem

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

Example

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

Python solution

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        return list(accumulate(nums))

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1480. Running Sum of 1d Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems