009.md

1480. Running Sum of 1d Array

Difficulty: 🟢 Easy

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.

Examples:

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

Solutions

We need to iterate over existing array of elements and update number at position with sum of previously seen numbers. In order to keep previously seen numbers sum we need to keep current by adding num at position.

O(n) solution

Python3

class Solution(object):
    def runningSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        current = 0
        for i in range(len(nums)):
            num = nums[i]
            nums[i] += current
            current += num
        return nums

The given solution solves the problem by iteratively calculating the running sum of the array nums. It uses a variable current to keep track of the current running sum. The algorithm performs the following steps:

1. Initialize current to 0.
2. Iterate through each element num in nums using a for loop.
3. Update nums[i] by adding current to it.
4. Update current by adding the original value of num.
5. Return the modified nums array.

Complexity Analysis

The time complexity of this algorithm is O(n), where n is the length of the input array nums. The algorithm iterates through each element of nums once.

The space complexity of the algorithm is O(1) since it does not use any additional data structures that grow with the input size.

Summary

The given solution calculates the running sum of an array nums by iterating through each element and updating the array in-place. The algorithm has a time complexity of O(n) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.