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.
LeetCode Solutions1 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6The algorithm iterates through the array once, so the time complexity is linear in the size of the input array.
The algorithm uses only a constant amount of extra space, regardless of the input size.
In this approach, we iterate through the input array nums and maintain a variable sum that keeps track of the running sum up to the current index. For each element in the array, we add its value to sum and then update the element in the array to be the current value of sum. This way, by the end of the loop, each element in nums will have been replaced by the running sum up to that index.
The algorithm iterates through the array once, so the time complexity is linear in the size of the input array.
The algorithm uses only a constant amount of extra space, regardless of the input size.
In this approach, we start iterating from the second element of the array (index 1) and update each element to be the sum of itself and the previous element. This way, each element at index i will become the running sum up to that index by adding the value of the previous element (which already contains the running sum up to index i-1) to its own value.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Prefix Sum with Temporary Variable | Explicit running sum logic with a separate variable | Slightly more verbose with an extra variable | |||
| Prefix Sum In-place from Second Element | Most concise — directly updates each element using the previous one, no extra variable needed | None |
The optimal approach for this problem is Solution 2: Prefix Sum In-place from Second Element, which achieves time complexity and space complexity. It iterates from the second element and simply adds the previous element's value, making it the most elegant and concise solution.
class Solution: def runningSum(self, nums: List[int]) -> List[int]: if len(nums) > 1000 or len(nums) < 1: raise ValueError("The length of nums must be between 1 and 1000.")
# Initialize a variable to keep track of the running sum sum = 0
# Iterate through the input array and update each element to be the running sum up to that index for i in range(len(nums)): sum += nums[i] nums[i] = sum
return numsclass Solution: def runningSum(self, nums: List[int]) -> List[int]: if len(nums) > 1000 or len(nums) < 1: raise ValueError("The length of nums must be between 1 and 1000.")
# Iterate through the array starting from the second element and update each element to be the sum of itself and the previous element for i in range(1, len(nums)): nums[i] += nums[i - 1]
return nums