1. Problem Summary
You are given an integer array nums.
Your task is to compute and return a new array result where:
result[i] = nums[0] + nums[1] + ... + nums[i]
This is known as the running sum or prefix sum of the array.
Example interpretation:
If:
nums = [1,2,3,4]
Then:
running sum = [1,3,6,10]
2. Key Insights
Running sum accumulates progressively
Each position builds on previous sum rather than recomputing from scratch.
We can compute running sum in-place
We do not need extra space if overwriting original array is allowed.
Time efficiency is linear
We only pass through the array once.
Useful in many algorithmic contexts
Prefix sums support:
- range sum queries
- cumulative statistics
- sliding window enhancements
3. Approach
Single pass accumulating total
Steps:
- Initialize running variable:
sum = 0 - Iterate through each index
i - Update sum:
sum += nums[i] - Store sum into result array at index
i - Return result
If modifying array in-place:
nums[i] += nums[i-1]
4. Time and Space Complexity
Time Complexity:
O(N)
Each element processed once.
Space Complexity Options:
- Returning new array:
O(N)
- In-place version:
O(1)
5. Java Solution (returns new array)
class Solution {
public int[] runningSum(int[] nums) {
int[] result = new int[nums.length];
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
result[i] = sum;
}
return result;
}
}
6. Java In-Place Solution (space-optimized)
class Solution {
public int[] runningSum(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}
7. Dry Run Examples
Example 1
Input:
[1,2,3,4]
Running:
- sum = 1
- sum = 3
- sum = 6
- sum = 10
Output:
[1,3,6,10]
Example 2
Input:
[1,1,1,1,1]
Output:
[1,2,3,4,5]
Example 3
Input:
[3,1,2,10,1]
Output:
[3,4,6,16,17]
Example 4
Input:
[0,0,0]
Output:
[0,0,0]
Example 5
Input:
[-1,5,-2,3]
Output:
[-1,4,2,5]
8. Why This Solution Works
- Each running sum builds naturally from the previous sum
- No recalculation of earlier values needed
- In-place accumulation retains correctness
- Works for:
- negatives
- zeros
- large values
- single-element arrays
9. Common Mistakes
- Recomputing sum from index 0 each time (O(N²))
- Forgetting negative numbers are allowed
- Using extra space unnecessarily when in-place acceptable
- Off-by-one indexing errors
- Confusing with suffix sums (reverse direction)