Running Sum of 1d Array
Problem Statement
Given an integer array nums, return an array runningSum where runningSum[i] equals the sum of nums[0] through nums[i] inclusive.
Input
An integer array nums.
Output
An integer array where each index stores the sum of all values from the start through that index.
Constraints
- •
1 <= nums.length <= 1000 - •
-10^6 <= nums[i] <= 10^6
Examples
Example 1
nums = [1,2,3,4]
[1,3,6,10]Example 2
nums = [1,1,1,1,1]
[1,2,3,4,5]Example 3
nums = [3,1,2,10,1]
[3,4,6,16,17]Learning Objectives
- Recognise when every answer is the sum of a prefix ending at the current index.
- Use the previous prefix sum instead of recomputing from the start each time.
- Safely update the input array in place when the original values are no longer needed.
Intuition
Pattern Recognition
This is the smallest prefix-sum signal: every result asks for the total from index 0 through the current index. The tempting approach is to recompute that sum for every i, which repeats the same additions and turns a simple task into O(n^2) work.
A prefix sum carries history forward. Once you know the sum through i - 1, the sum through i is just that value plus nums[i]. Because the output can overwrite the input, nums[i - 1] can become the previous prefix sum and nums[i] can be updated directly.
Common mistakes
- ×Starting the loop at index **0** and trying to read **nums[-1]**.
- ×Recomputing the sum from the beginning for every index.
- ×Allocating a second array even when the problem allows returning the modified input array.
- ×Forgetting that negative values still work because addition is accumulated exactly the same way.
Algorithm Explanation
Key idea
Store each prefix sum where the current value lives. After processing index i - 1, nums[i - 1] already equals the sum of all values through i - 1. Add it into nums[i] to make nums[i] the next prefix sum.
Walkthrough
For nums = [1,2,3,4], leave index 0 as 1 because the first prefix contains only the first element. At index 1, add the previous prefix 1 to get 3. At index 2, add the previous prefix 3 to get 6. At index 3, add 6 to get 10. The array has become [1,3,6,10], which is exactly the required answer.
Algorithm
- If the array has one element, it is already its running sum.
- Start at index 1 because index 0 has no previous prefix.
- For each index, add nums[i - 1] into nums[i].
- After the loop, return nums because every cell now stores its prefix sum.
Solutions
Solution: In-place prefix accumulation
The input array can become the answer. Once index i - 1 has been converted into a prefix sum, add it to the current value to create the prefix sum at i.
Step-by-step
- Keep nums[0] unchanged because it is already the first prefix sum.
- Iterate from index 1 to the end.
- Replace nums[index] with nums[index] + nums[index - 1].
- Return the same array after all prefixes have been written.
O(n)
O(1)
Each element after the first is updated once, and the input array is reused as the output.
Java implementation
Dry Run
Sample input
nums = [1,2,3,4]. Track how each current value absorbs the prefix sum on its left.
| index | value before update | previous prefix sum | prefix sum after update | answer array so far |
|---|---|---|---|---|
| 0 | 1 | none | 1 | [1,2,3,4] |
| 1 | 2 | 1 | 3 | [1,3,3,4] |
| 2 | 3 | 3 | 6 | [1,3,6,4] |
| 3 | 4 | 6 | 10 | [1,3,6,10] |
The final array stores the prefix sum ending at each index, so the answer is [1,3,6,10].
Interview Tips
Say that this is prefix sum in its simplest in-place form. The important observation is not the loop itself; it is that after index i - 1 is processed, that cell already contains all information needed for index i. Mention that if the input could not be modified, you would write the same recurrence into a new output array.
Likely follow-ups
- How would you solve it if the input array must remain unchanged?
- How would you answer many range-sum queries after computing running sums?
- How would the idea change for a 2D matrix of prefix sums?
- What integer type would you choose if values and array length were much larger?
Similar Problems
Key Takeaways
- A prefix sum at index **i** is the previous prefix plus the current value.
- In-place prefix sums are safe when the original previous value will not be needed again.
- Replacing repeated summation with a carried total changes O(n^2) work into O(n).