Running Sum of 1d Array
Description
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
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Prefix sum accumulation
- Approach
- Iterate through array, keep track of cumulative sum, store each intermediate sum
- Complexity
- Single pass through array, maintain running total
Solutions
Show PY Solution
def solution(nums):
result = [nums[0]]
for i in range(1, len(nums)):
result.append(nums[i] + result[-1])
return result