Cumulative Sum of an Array
Solve this ProblemEasy5–10 min
Topics
ArrayPrefix Sum
Companies
AmazonMicrosoftGoogleAdobe
Given an array of integers
nums, return an array result where result[i] is the sum of nums[0..i] (inclusive) — the running total up to and including that index.
Recomputing each of these totals from scratch works, but it throws away everything the previous total already knew: the sum through index i is just the sum through index i - 1 plus nums[i]. Carrying a single running total forward — the prefix sumPrefix SumA running total built up left to right, where each position holds the sum of every element up through that point — the foundation for answering range-sum questions in O(1) after one O(n) pass. technique — turns an O(n²) scan into a single O(n) pass.
Test Case 1:
Input:nums = [1, 2, 3, 4]
Output:[1, 3, 6, 10]
Explanation:result[i] is the running total of nums[0..i] — 1, 1+2, 1+2+3, 1+2+3+4.
Test Case 2:
Input:nums = [1, 1, 1, 1, 1]
Output:[1, 2, 3, 4, 5]
Explanation:Each step just adds one more 1 to the running total.
Test Case 3:
Input:nums = [-2, 3, -1, 5]
Output:[-2, 1, 0, 5]
Explanation:Negative values work the same way — the running total can dip and recover.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
-10⁴ ≤ nums[i] ≤ 10⁴
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int[] cumulativeSum(int[] nums) { |
| 3 | int[] result = new int[nums.length]; |
| 4 | int sum = 0; |
| 5 | for (int i = 0; i < nums.length; i++) { |
| 6 | sum += nums[i]; |
| 7 | result[i] = sum; |
| 8 | } |
| 9 | return result; |
| 10 | } |
| 11 | } |
| 12 |
1
2
3
4
0
1
2
3
Variables
sum
0INITIALIZE
Start a running sum at 0. Walk through the array once, adding each element to the running total as you go.
Step 1 / 10
Approach & Solutions
Brute Force
BruteFor each index i, re-sum everything from index 0 to i from scratch with a nested loop. Correct, but every one of these sums shares almost all of its work with the sum computed just before it — that overlap is thrown away and redone every time.
Time
O(n²)Space
O(1)Java
1class Solution {
2 public int[] cumulativeSum(int[] nums) {
3 int[] result = new int[nums.length];
4 for (int i = 0; i < nums.length; i++) {
5 int sum = 0;
6 for (int j = 0; j <= i; j++) {
7 sum += nums[j];
8 }
9 result[i] = sum;
10 }
11 return result;
12 }
13}Optimal — Prefix Sum
OptimalKeep a single running sum. Walk through the array once, adding each element to that running total and writing it straight into the result — the running total already has everything before it baked in, so there's never any need to re-scan. This is the prefix sum technique in its simplest form.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int[] cumulativeSum(int[] nums) {
3 int[] result = new int[nums.length];
4 int sum = 0;
5 for (int i = 0; i < nums.length; i++) {
6 sum += nums[i];
7 result[i] = sum;
8 }
9 return result;
10 }
11}