Running Sum of 1d Array

Difficulty: Easy | Acceptance: 86.90% | Paid: No Topics: Array, Prefix Sum

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
• Constraints
• Approach 1: In-Place Iteration
• Approach 2: New Array Iteration
• Approach 3: Built-in Accumulate

Examples

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].

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].

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints

1 <= nums.length <= 1000
-10⁶ <= nums[i] <= 10⁶

Approach 1: In-Place Iteration

Intuition We can calculate the running sum by iterating through the array and adding the previous element’s value to the current element. This modifies the original array to store the result.

Steps

• Iterate through the array starting from index 1.
• For each element at index i, add the value of the element at index i-1 to it.
• Return the modified array.

class Solution:
    def runningSum(self, nums: list[int]) -> list[int]:
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        return nums

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Modifies input array in-place, which is optimal for space.

Approach 2: New Array Iteration

Intuition If we need to preserve the original array, we can create a new array to store the running sums. We copy the first element and then iteratively calculate subsequent sums based on the previous sum in the new array.

Steps

• Initialize a result array with the first element of nums.
• Iterate from index 1 to the end of nums.
• Calculate the sum of the previous value in the result array and the current value in nums.
• Append this sum to the result array.
• Return the result array.

class Solution:
    def runningSum(self, nums: list[int]) -> list[int]:
        res = [nums[0]]
        for i in range(1, len(nums)):
            res.append(res[-1] + nums[i])
        return res

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space to keep the input array intact.

Approach 3: Built-in Accumulate

Intuition Many languages provide built-in functions or libraries to perform cumulative operations (like prefix sums) in a concise manner. We can leverage these standard library features.

Steps

• Use the language’s specific built-in function for cumulative sum (e.g., accumulate in Python, partial_sum in C++, reduce in JavaScript).
• Return the result.

from itertools import accumulate

class Solution:
    def runningSum(self, nums: list[int]) -> list[int]:
        return list(accumulate(nums))

Complexity

• Time: O(n)
• Space: O(n) or O(1) depending on language implementation
• Notes: Concise and readable, utilizing standard library optimizations.