Running Sum of 1d Array: Your First Prefix Sum
You are given an integer array nums. Return an array result where result[i] is the sum of nums[0] through nums[i]. That is it. No tricks, no edge-case minefield. Just accumulate as you go.
This is LeetCode 1480: Running Sum of 1d Array, an easy problem that introduces one of the most reusable patterns in all of algorithms: the prefix sum.
For example, given nums = [1, 2, 3, 4], the running sum is [1, 3, 6, 10] because 1 = 1, 1+2 = 3, 1+2+3 = 6, and 1+2+3+4 = 10.
Why this problem matters
This problem is dead simple on its own. You could solve it in a few lines without even thinking about it. So why bother studying it?
Because the prefix sum pattern hides inside dozens of harder problems. Subarray sum equals K, range sum queries, product of array except self, and many interval-based problems all rely on the same idea: precompute cumulative totals so you can answer range queries in constant time.
If you drill this pattern until it is automatic, you will recognize it instantly when it shows up wearing a disguise in a medium or hard problem. That recognition is worth more than memorizing the solution to any single problem.
The key insight
Each element in the output is just the previous output plus the current input. You do not need to re-sum from the beginning every time. You carry a running total forward:
result[0] = nums[0]result[i] = result[i-1] + nums[i]fori > 0
This is the textbook definition of a prefix sum. One pass, one accumulator, done.
The solution
def runningSum(nums):
for i in range(1, len(nums)):
nums[i] += nums[i - 1]
return nums
This solution modifies nums in place. Each nums[i] gets overwritten with the cumulative sum so far. If you need to keep the original array intact, create a separate result list and accumulate into that instead.
Visual walkthrough
Step 0: Copy the first element
result[0] = nums[0] = 1. The running sum starts with the first element.
Step 1: Add nums[1] to the previous sum
result[1] = result[0] + nums[1] = 1 + 2 = 3.
Step 2: Add nums[2] to the previous sum
result[2] = result[1] + nums[2] = 3 + 3 = 6.
Step 3: Add nums[3] to the previous sum
result[3] = result[2] + nums[3] = 6 + 4 = 10. Done: [1, 3, 6, 10].
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| In-place prefix sum | O(n) | O(1) |
| Separate result array | O(n) | O(n) |
Both approaches make a single pass through the array. The in-place version reuses the input array, so it needs no extra space beyond a loop variable. If you allocate a new result array, space becomes O(n).
The building blocks
1. Prefix sum accumulation
The core pattern: walk left to right, keeping a running total that incorporates each new element.
total = 0
for x in nums:
total += x
prefix.append(total)
You will see this exact loop in range sum queries, subarray sum problems, and anywhere you need to turn "sum from index L to R" into a constant-time lookup.
2. In-place array transformation
Instead of allocating a new array, you overwrite each element with its new value. The trick is processing in the right order so you never read a value after it has been overwritten. For prefix sums, left-to-right works because you only need the immediately previous element.
3. Recurrence relation recognition
The formula result[i] = result[i-1] + nums[i] is a simple recurrence. Recognizing when a problem can be expressed as "current answer depends on previous answer plus new data" is the first step toward dynamic programming. This problem is the gentlest possible introduction to that way of thinking.
Edge cases
Before submitting, make sure your solution handles these:
- Single element
nums = [5]: the running sum is just[5]. The loop body never executes and the original array is returned unchanged. - All zeros
nums = [0, 0, 0]: the running sum is[0, 0, 0]. Zeros accumulate correctly. - Negative numbers
nums = [-1, 2, -3]: the running sum is[-1, 1, -2]. Prefix sums work the same way with negatives. - Large values: with up to 1000 elements each up to 10^6, the maximum sum is 10^9, which fits comfortably in a 32-bit integer. No overflow concerns in Python.
From understanding to recall
You have read the prefix sum pattern and it makes sense. Carry a running total, add each element, done. Three lines of code. Could not be simpler.
But simplicity is deceptive. When this pattern appears inside a harder problem, you need to recognize it instantly and write it without thinking. That only happens if you have practiced it enough times that it is burned into muscle memory.
Spaced repetition is how you get there. You write the prefix sum loop from scratch today, then again in two days, then in a week. After a few rounds, the pattern is automatic. When you see "compute a cumulative total" buried inside a subarray sum problem or a range query, you do not pause to think. You just write it.
The prefix sum is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning each one independently and drilling it with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.
Related posts
- Subarray Sum Equals K - Uses prefix sums with a hash map to count subarrays that sum to a target
- Product of Array Except Self - Prefix and suffix products instead of prefix sums
- Contiguous Array - Prefix sums applied to binary arrays with a hash map for balance tracking
CodeBricks breaks the running sum of 1d array LeetCode problem into its prefix sum building block, then drills it independently with spaced repetition. You type the accumulation loop from scratch until it is automatic. When a prefix sum question shows up in your interview, you do not think about it. You just write it.