Problem Description

You are given an array nums. The running sum of an array is calculated where each element at position i contains the sum of all elements from index 0 to index i (inclusive).

Specifically, runningSum[i] = nums[0] + nums[1] + ... + nums[i].

Your task is to return a new array containing the running sum of the input array nums.

For example, if nums = [1, 2, 3, 4]:

• runningSum[0] = 1 (just the first element)
• runningSum[1] = 1 + 2 = 3 (sum of first two elements)
• runningSum[2] = 1 + 2 + 3 = 6 (sum of first three elements)
• runningSum[3] = 1 + 2 + 3 + 4 = 10 (sum of all four elements)

So the output would be [1, 3, 6, 10].

The solution uses Python's accumulate function from the itertools module, which efficiently computes the running sum by iterating through the array once and maintaining a cumulative sum as it goes.

Intuition

The key observation is that each element in the running sum array builds upon the previous one. Instead of recalculating the sum from the beginning for each position, we can use the fact that runningSum[i] = runningSum[i-1] + nums[i].

Think of it like keeping a running total as you walk through the array. At each step, you just add the current number to your running total, and that becomes the value at the current position in the result array.

For example, if we have [1, 2, 3, 4]:

• Start with 1
• Add 2 to get 3
• Add 3 to the previous sum 3 to get 6
• Add 4 to the previous sum 6 to get 10

This gives us [1, 3, 6, 10].

This pattern of maintaining a cumulative sum as we iterate through the array is exactly what Python's accumulate function does internally. It starts with the first element and keeps adding each subsequent element to the accumulated sum, yielding each intermediate result.

The beauty of this approach is its efficiency - we only need to traverse the array once, performing a single addition operation at each step, giving us O(n) time complexity with minimal code.

Learn more about Prefix Sum patterns.

Solution Approach

The solution implements a Prefix Sum approach, which is a fundamental technique for computing cumulative sums efficiently.

The implementation traverses the array once, and for each element at position i, it calculates the prefix sum by adding the current element nums[i] to the previously computed sum nums[i-1].

Here's how the algorithm works step by step:

1. Start with the first element as is (since there are no previous elements to add)
2. For each subsequent element, add it to the running total from the previous position
3. Store each cumulative sum in the result array

The Python solution uses the built-in accumulate function from the itertools module:

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

The accumulate function internally maintains a running total and yields each intermediate sum. It essentially performs:

• result[0] = nums[0]
• result[1] = result[0] + nums[1]
• result[2] = result[1] + nums[2]
• And so on...

This could also be implemented manually:

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

The time complexity is O(n) where n is the length of the array, as we visit each element exactly once. The space complexity is O(1) if we modify the input array in place, or O(n) if we create a new array for the result.

Example Walkthrough

Let's walk through the solution with nums = [3, 1, 2, 10, 1].

Step 1: Start with the first element

• Running sum at index 0: 3
• Result so far: [3]

Step 2: Add the second element to our running total

• Previous sum: 3
• Current element: 1
• Running sum at index 1: 3 + 1 = 4
• Result so far: [3, 4]

Step 3: Add the third element to our running total

• Previous sum: 4
• Current element: 2
• Running sum at index 2: 4 + 2 = 6
• Result so far: [3, 4, 6]

Step 4: Add the fourth element to our running total

• Previous sum: 6
• Current element: 10
• Running sum at index 3: 6 + 10 = 16
• Result so far: [3, 4, 6, 16]

Step 5: Add the fifth element to our running total

• Previous sum: 16
• Current element: 1
• Running sum at index 4: 16 + 1 = 17
• Final result: [3, 4, 6, 16, 17]

Notice how each new value builds upon the previous sum. We never need to go back and re-add elements from the beginning. The accumulate function handles this pattern automatically, maintaining the running total as it iterates through the array once.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. This is because the accumulate function needs to iterate through all elements in the input array exactly once to compute the running sum.

The space complexity is O(n), not O(1) as stated in the reference answer. The reference answer appears to be incorrect here. While accumulate itself is a generator that doesn't create the entire list upfront, the code explicitly converts it to a list using list(accumulate(nums)), which creates a new list of size n to store all the running sums. Therefore, the space complexity is O(n) for the output list.

If we were to modify the solution to update the input array in-place (e.g., nums[i] += nums[i-1] for each element), then we could achieve O(1) space complexity. However, the given code creates and returns a new list, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Input Array Without Consideration

A common mistake is modifying the input array in-place without realizing this might cause issues if the original data needs to be preserved.

Problematic Code:

def runningSum(self, nums: List[int]) -> List[int]:
    for i in range(1, len(nums)):
        nums[i] = nums[i-1] + nums[i]  # Modifies original array
    return nums

Issue: If the caller expects the original nums array to remain unchanged, this will cause unexpected behavior.

Solution: Create a copy of the array first or build a new result array:

def runningSum(self, nums: List[int]) -> List[int]:
    result = nums.copy()  # Create a copy first
    for i in range(1, len(result)):
        result[i] = result[i-1] + result[i]
    return result

2. Empty Array Handling

Failing to handle empty arrays can cause index errors or unexpected behavior.

Problematic Code:

def runningSum(self, nums: List[int]) -> List[int]:
    result = [nums[0]]  # IndexError if nums is empty
    for i in range(1, len(nums)):
        result.append(result[-1] + nums[i])
    return result

Solution: Add a guard clause for empty arrays:

def runningSum(self, nums: List[int]) -> List[int]:
    if not nums:
        return []
    result = [nums[0]]
    for i in range(1, len(nums)):
        result.append(result[-1] + nums[i])
    return result

3. Integer Overflow in Other Languages

While Python handles large integers automatically, implementing this in languages like Java or C++ requires consideration of integer overflow.

Issue in Java:

// May overflow for large sums
int[] runningSum(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        nums[i] = nums[i-1] + nums[i];  // Can overflow
    }
    return nums;
}

Solution: Use appropriate data types like long or check for overflow conditions:

long[] runningSum(int[] nums) {
    long[] result = new long[nums.length];
    result[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        result[i] = result[i-1] + nums[i];
    }
    return result;
}