Pythonic Way to Solve Prefix Sum

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.

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

Old Way

A straight forward solution would be to use loops and a prefixSum variable to hold the sum

def getPrefixSum(arr):
    prefixSum[0] = arr[0]
    for i in range(1, len(arr)):
        prefixSum[i] = arr[i] + prefixSum[i-1]
    return prefixSum

However, Python's internal libraries allow this to be handled more efficiently.

Pythonic Solution

Use itertools.accumulate. The itertools module contains multiple methods for performing multiple operations on iterables.

from itertools import accumulate

def getPrefixSum(arr):
    return list(accumulate(arr))

• Time Complexity: O(N)
• Space Complexity: O(1)

Result:

• Memory: Beats 94.67%
• Runtime: Beats 100%