LeetCode Problem 1480

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

LeetCode 1480 - Running Sum of 1d Array

Problem Understanding

The problem asks us to compute the running sum, also called the prefix sum, of a one dimensional integer array.

For every index i, the result at position i should equal the sum of all elements from index 0 through index i in the original array. In other words, each position accumulates everything that came before it, including the current element.

If the input is:

[1,2,3,4]

then:

• The first value is 1
• The second value is 1 + 2 = 3
• The third value is 1 + 2 + 3 = 6
• The fourth value is 1 + 2 + 3 + 4 = 10

So the output becomes:

[1,3,6,10]

The input consists of an integer array nums, and the output should be another array of the same length where each index stores the cumulative total up to that position.

The constraints are relatively small:

• The array length is at most 1000
• Each value can range from -10^6 to 10^6

These constraints tell us that performance is not extremely demanding, but we should still aim for an efficient linear solution. Since the array can contain negative numbers, the running sum is not necessarily increasing. The algorithm must correctly handle positive, negative, and zero values.

One important edge case is an array with only one element. In that situation, the running sum is simply the original value itself. Another important case is arrays containing negative numbers, because cumulative totals can decrease. Arrays containing zeros are also important because the running total may remain unchanged across positions.

Approaches

Brute Force Approach

The brute force solution computes each running sum independently.

For every index i, we iterate from index 0 through i and calculate the total sum manually. That computed sum is then stored in the result array.

For example, to compute the value at index 3, we would sum:

nums[0] + nums[1] + nums[2] + nums[3]

This approach is correct because it directly follows the definition of a running sum. However, it repeatedly recalculates sums that were already computed earlier.

If the array has n elements:

• Computing the first prefix sum takes 1 operation
• The second takes 2
• The third takes 3

and so on.

The total work becomes:

1 + 2 + 3 + ... + n = O(n^2)

While this is acceptable for small arrays, it is inefficient compared to what is possible.

Optimal Prefix Sum Approach

The key observation is that each running sum builds directly on the previous one.

Suppose we already know:

runningSum[i - 1]

Then the next value is simply:

runningSum[i] = runningSum[i - 1] + nums[i]

This means we never need to recompute earlier sums from scratch. We can maintain a cumulative total while traversing the array once from left to right.

This reduces the time complexity from quadratic to linear.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Recomputes prefix sums repeatedly
Optimal	O(n)	O(n)	Maintains cumulative running total

Algorithm Walkthrough

1. Create an empty result array that will store the running sums.
2. Initialize a variable called current_sum to 0. This variable keeps track of the cumulative total seen so far.
3. Traverse the input array from left to right.
4. For each element:

• Add the current number to current_sum
• Append the updated current_sum to the result array

5. After processing all elements, return the result array.

The algorithm only needs one pass through the array because each running sum depends only on the previous cumulative total.

Why it works

The algorithm maintains the invariant that current_sum always equals the sum of all elements processed so far.

After processing index i, we know:

current_sum = nums[0] + nums[1] + ... + nums[i]

Since this exactly matches the definition of the running sum at index i, appending current_sum to the result array guarantees correctness.

Python Solution

from typing import List

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = []
        current_sum = 0

        for number in nums:
            current_sum += number
            result.append(current_sum)

        return result

The implementation begins by creating an empty list called result, which stores the final running sums.

The variable current_sum tracks the cumulative total while iterating through the array.

During each iteration:

• The current number is added to current_sum
• The updated cumulative total is appended to the result list

Because the running total is updated incrementally, each prefix sum is computed in constant time. The algorithm processes every element exactly once.

Go Solution

func runningSum(nums []int) []int {
    result := make([]int, len(nums))
    currentSum := 0

    for i, num := range nums {
        currentSum += num
        result[i] = currentSum
    }

    return result
}

The Go implementation follows the same logic as the Python solution.

One small difference is that Go requires explicit allocation of the result slice using make. Since the final size is already known, we allocate the slice with length len(nums) immediately.

The variable currentSum stores the cumulative total, and each updated value is written directly into the corresponding index of the result slice.

Go integers are sufficient for the given constraints because the maximum possible cumulative sum remains within the range of a standard integer type.

Worked Examples

Example 1

Input:

nums = [1,2,3,4]

Step	Current Number	Running Total	Result
Start	-	0	[]
1	1	1	[1]
2	2	3	[1,3]
3	3	6	[1,3,6]
4	4	10	[1,3,6,10]

Final output:

[1,3,6,10]

Example 2

Input:

nums = [1,1,1,1,1]

Step	Current Number	Running Total	Result
Start	-	0	[]
1	1	1	[1]
2	1	2	[1,2]
3	1	3	[1,2,3]
4	1	4	[1,2,3,4]
5	1	5	[1,2,3,4,5]

Final output:

[1,2,3,4,5]

Example 3

Input:

nums = [3,1,2,10,1]

Step	Current Number	Running Total	Result
Start	-	0	[]
1	3	3	[3]
2	1	4	[3,4]
3	2	6	[3,4,6]
4	10	16	[3,4,6,16]
5	1	17	[3,4,6,16,17]

Final output:

[3,4,6,16,17]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	The output array stores one value per input element

The algorithm performs a single linear traversal through the array. Every iteration does constant work, consisting of one addition and one append or assignment operation.

The additional space usage comes entirely from the result array required by the problem statement.

Test Cases

from typing import List

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = []
        current_sum = 0

        for number in nums:
            current_sum += number
            result.append(current_sum)

        return result

solution = Solution()

# Provided example 1
assert solution.runningSum([1, 2, 3, 4]) == [1, 3, 6, 10]

# Provided example 2
assert solution.runningSum([1, 1, 1, 1, 1]) == [1, 2, 3, 4, 5]

# Provided example 3
assert solution.runningSum([3, 1, 2, 10, 1]) == [3, 4, 6, 16, 17]

# Single element array
assert solution.runningSum([5]) == [5]

# Array with negative values
assert solution.runningSum([1, -2, 3, -1]) == [1, -1, 2, 1]

# Array with zeros
assert solution.runningSum([0, 0, 0]) == [0, 0, 0]

# Mixed positive and negative values
assert solution.runningSum([-1, -2, 5, 3]) == [-1, -3, 2, 5]

# Large values within constraints
assert solution.runningSum([10**6, 10**6, -10**6]) == [10**6, 2 * 10**6, 10**6]

# Increasing sequence
assert solution.runningSum([1, 2, 3, 4, 5]) == [1, 3, 6, 10, 15]

Test	Why
[1,2,3,4]	Validates standard running sum behavior
[1,1,1,1,1]	Tests repeated values
[3,1,2,10,1]	Tests mixed magnitude values
[5]	Validates single element handling
[1,-2,3,-1]	Ensures negative values are handled correctly
[0,0,0]	Confirms zeros do not break accumulation
[-1,-2,5,3]	Tests cumulative totals that decrease and increase
[10^6,10^6,-10^6]	Verifies large values within constraints
[1,2,3,4,5]	Tests normal increasing sequence

Edge Cases

One important edge case is a single element array. Since there are no previous elements to accumulate, the running sum should simply equal the original value. The implementation handles this naturally because the loop executes once, adds the element to current_sum, and appends it to the result.

Another important case involves negative numbers. A common mistake is assuming the running sum always increases. With negative values, the cumulative total may decrease. Since the algorithm directly adds each number to the current total without making assumptions about sign, it correctly handles positive and negative transitions.

Arrays containing zeros are also important. Adding zero should preserve the previous cumulative total. The implementation handles this correctly because adding zero leaves current_sum unchanged, and that unchanged value is appended to the result.

A final edge case involves very large values near the constraint boundaries. Even when numbers approach 10^6, the algorithm still works correctly because it only performs integer addition, and the cumulative totals remain safely within standard integer limits for both Python and Go.