Running Sum Of 1d Array - Leetcode Solution

Problem Statement:

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 by adding previous elements. [1, 1+2, 1+2+3, 1+2+3+4].

Solution:

In this problem, we are given an array nums and we are supposed to find the running sum of the array where the running sum is defined as the sum of all the elements from the beginning of the array up to that element.

We can solve this problem by using a simple method. We first create a new array of the same length as the input array and initialize it with 0. Then we iterate through the input array and add the previous element to the current element. This will give us the running sum. Finally we return the resultant array.

Here's the algorithm:

1. Initialize a new array res of the same length as the input array with all elements set to 0.
2. Initialize a variable sum to 0.
3. Iterate through the input array nums.
4. For each element i of nums, add it to sum and assign the value of sum to res[i].
5. Return the resultant array res.

Here's the python code:

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        res = [0]*len(nums)
        sum = 0
        for i in range(len(nums)):
            sum += nums[i]
            res[i] = sum
        return res

This solution has a time complexity of O(n) as we iterate through the input array only once and a space complexity of O(n) as we create a new array of the same length as the input array.

1