How to Calculate the Running Sum of an Array in Python

The original problem of “1480. Running Sum of 1d Array” was published on LeetCode.com

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

Solution

To solve this problem, you need to understand how to calculate a running sum of an array. This involves adding the current element of the array to the sum of all the elements that came before it. You must also understand how to loop through an array and access each element. Finally, you need to understand how to return the running sum of the array.

What is an array?

An array is a data structure that stores a collection of elements. Each element can be accessed by its index. Arrays are commonly used in programming to store and manipulate data.

How to calculate a running sum of an array?

A running sum of an array is calculated by adding the current element of the array to the sum of all the elements that came before it. This can be done by looping through the array and keeping track of the sum. For example, if the array is [1,2,3,4], the running sum would be [1,3,6,10].

How to loop through an array and access each element in Python?

In Python, you can loop through an array using a for loop. For example, if the array is called nums, you can loop through it like this:

for num in nums:
    # do something with num

This will loop through each element in the array and assign it to the variable num. You can then use the variable num to access the current element.

How to calculate a running sum of an array in Python?

In Python, you can calculate a running sum of an array by looping through the array and keeping track of the sum as you go. For example, if the array is called nums, you can calculate the running sum like this:

running_sum = 0
for num in nums:
    running_sum += num

This will loop through each element in the array and add it to the running sum. The final value of running_sum will be the running sum of the array.

Let’s develop a solution with an explanation.

The problem asks us to return the running sum of an array. To solve this problem, we can loop through the array and keep track of the running sum.

First, we need to create a variable to store the running sum. We can set this to 0 initially.

running_sum = 0

Next, we can loop through the array and add each element to the running sum. We can also create a new array to store the running sum of each element.

result = []
for num in nums:
    running_sum += num
    result.append(running_sum)

Finally, we can return the array containing the running sum of each element.

return result

The complete solution looks like this:

def runningSum(nums):
    running_sum = 0
    result = []
    for num in nums:
        running_sum += num
        result.append(running_sum)
    return result

What is the time complexity of this code?

The runningSum() function takes an array of numbers as an input and returns an array where each element equals the initial array’s running sum. This function has a linear time complexity of O(n), because it iterates through the entire array once. As the number of elements in the array increase, the time complexity of the function increases proportionally.

What is the space complexity of this code?

The space complexity of this code is O(n), as the size of the result array increases in direct proportion to the size of the given input array, nums. This is because the result array contains the accumulated running sum, meaning that the result array will always be the same size as the input array.

Can this code be shortened to a one-liner?

Yes. The following code is a one-liner that returns the running sum of an array:

def runningSum(nums):
    return [sum(nums[0:i+1]) for i in range(len(nums))]

This one-liner creates a list containing the accumulated running total of the given array elements from index 0 up to the given index. It does this by looping through the indices of the nums array and, at each index, calculating the running total using the sum() function on a slice of the array from index 0 up to the current index. The resulting list is then returned.

What is list comprehension?

List comprehension is a concise way of creating a list from an existing list. It is a powerful tool for quickly transforming data. In the example above, we are using list comprehension to create a new list containing the running sum of each element in the original list.

What is the syntax of list comprehension?

The syntax of list comprehension is as follows:

[expression for item in list]

In the example above, the expression is sum(nums[:i+1]) and the list is range(len(nums)). This will create a new list containing the running sum of each element in the original list.