1480. Running Sum of 1d Array
Given an array
nums. We define a running sum of an array as
runningSum[i] = sum(nums…nums[i]).
Return the running sum of
Input: nums = [1,2,3,4]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Input: nums = [1,1,1,1,1]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Input: nums = [3,1,2,10,1]
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
This is an easy question. All we need to do is run a loop that starts with the second number in the list. The loop takes the number in the previous position and current position in the list, and store the result in the current position.
def runningSum(self, nums: List[int]) -> List[int]:
for i in range(1, len(nums)):
nums[i] = nums[i-1] + nums[i]
We are traversing through the list once. Hence the time complexity is O(N).
We are not using any extra data structure to store any intermediate results. Hence the space complexity is O(1).
I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.