Running Sum of 1d Array
Easy Single pass
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given an array, return a new array where each position holds the total of all elements from index 0 up to that position.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each position, what is the total of everything up to here? The answer for one position is just the answer for the position before it plus one more number.
Why this works: we reuse the total we already have instead of adding everything again. That turns O(n²) into O(n).
Example: nums = [1, 2, 3, 4]
i=0: total = 1 → [1, 2, 3, 4]i=1: total = 1 + 2 = 3 → [1, 3, 3, 4]i=2: total = 3 + 3 = 6 → [1, 3, 6, 4]i=3: total = 6 + 4 = 10 → [1, 3, 6, 10]
✦Hints open one at a time
↗Approach
Walk left to right and keep adding the previous value into the current one. One loop, constant work per element, so the whole thing is O(n). A nested loop that re-adds everything for each index would be O(n²) — this is the classic example of reusing work you already did.
</>Solution (Java)
class Solution {
public int[] runningSum(int[] nums) {
// each element becomes "itself + everything before it"
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}!Common mistake
Starting the loop at i = 0 and reading nums[-1]. Start at i = 1.
- Time: O(n) — one pass.
- Space: O(1) extra — we update the input in place.
