Review the fundamentals: Arrays guide and time complexities.
Cumulative Array Sum — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Cumulative Array Sum problem optimally.
O(n)O(1)Problem Description
Given an integer array scores, construct and return a new array cumulative where cumulative[i] equals the sum of scores[0] through scores[i] inclusive. The function must process the input in linear time and use O(1) additional space beyond the output array. The input size can be large, so an efficient single‑pass algorithm is required.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Cumulative Array Sum"
WHY DOES IT MATTER?
Prefix‑sum patterns appear in range‑query problems, sliding‑window calculations, and histogram building; mastering them reduces many seemingly quadratic tasks to linear time.
OPTIMIZATION CHALLENGE
Recognizing that each cumulative value can be expressed as the previous cumulative value plus the current element eliminates the need for nested loops, collapsing the complexity from O(n^2) to O(n).
REAL-WORLD CONNECTION
Think of a bank ledger where each entry updates the account balance; the balance after each transaction is the cumulative sum of all prior amounts, mirroring how distributed systems propagate state changes efficiently.
During an interview, compute the running total in a local variable, assign it to the output index, and resist the temptation to use extra arrays or nested loops—clarity and constant extra space win points.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The cumulative sum problem is a classic example of prefix computation, where each output element depends on all preceding inputs. A naive solution would recompute the sum for each index, leading to O(n^2) time, which quickly becomes prohibitive for large arrays. The optimal paradigm leverages the associative property of addition: cumulative[i] can be derived from cumulative[i‑1] plus scores[i], allowing a single linear pass while only storing the running total. This approach satisfies the O(n) time and O(1) auxiliary space constraints because the only extra variable needed is the current prefix sum, and the output array itself accounts for the required space.
Interview Questions on This Problem
Q1How would you modify the cumulative sum algorithm to handle updates where a single element in scores changes after the initial array is built?
Use a Binary Indexed Tree (Fenwick) or Segment Tree to support point updates and prefix‑sum queries in O(log n) time, preserving fast query performance while allowing dynamic modifications.
Q2At a fintech firm you need to compute daily running balances for millions of transactions; why is the O(1) extra‑space cumulative approach preferable to recomputing sums each day?
Because transaction logs can be massive, recomputing would be O(n^2) across days, causing latency and high CPU cost; a single‑pass prefix sum updates balances in linear time with negligible memory overhead, enabling real‑time reporting.
Q3A startup asks you to return the cumulative array but also keep the original scores immutable; how do you meet both requirements?
Allocate a new array for the result, iterate once copying scores while maintaining a running total, thereby preserving the input and achieving O(n) time and O(n) output space only.
Examples
Input
[4, -2, 7, 0, 5]
Output
[4, 2, 9, 9, 14]
Explanation: Start with the first element: 4 → cumulative[0]=4. Add -2 to previous sum (4) → 2, so cumulative[1]=2. Add 7 to 2 → 9, cumulative[2]=9. Add 0 to 9 → 9, cumulative[3]=9. Add 5 to 9 → 14, cumulative[4]=14.
Input
[10, 20, 30]
Output
[10, 30, 60]
Explanation: cumulative[0]=10. cumulative[1]=10+20=30. cumulative[2]=30+30=60.
Input
[-5, -3, -2]
Output
[-5, -8, -10]
Explanation: cumulative[0]=-5. cumulative[1]=-5+(-3)=-8. cumulative[2]=-8+(-2)=-10.
Constraints
- 1 <= scores.length <= 100000
- -1000000000 <= scores[i] <= 1000000000
- The cumulative sums fit within a 64‑bit signed integer.
Optimal Approach & Strategy
Maintain a running total while iterating once, store the total at each position, achieving O(n) time and O(1) extra space.
Brute Force Approach
For each index i, sum scores[0] through scores[i] using a nested loop, resulting in O(n^2) time.
Step-by-Step Dry Run
Step 1: Initialize an output array 'cumulative' of size 5. Let 'currentSum' = 0. Input: scores = [4, -2, 7, 0, 5]. Step 2: i=0: currentSum = 0 + scores[0] (4) = 4. Set cumulative[0] = 4. State: cumulative=[4, 0, 0, 0, 0], currentSum=4. Step 3: i=1: currentSum = 4 + scores[1] (-2) = 2. Set cumulative[1] = 2. State: cumulative=[4, 2, 0, 0, 0], currentSum=2. Step 4: i=2: currentSum = 2 + scores[2] (7) = 9. Set cumulative[2] = 9. State: cumulative=[4, 2, 9, 0, 0], currentSum=9. Step 5: i=3: currentSum = 9 + scores[3] (0) = 9. Set cumulative[3] = 9. State: cumulative=[4, 2, 9, 9, 0], currentSum=9. Step 6: i=4: currentSum = 9 + scores[4] (5) = 14. Set cumulative[4] = 14. State: cumulative=[4, 2, 9, 9, 14], currentSum=14. Final Answer: The result is [4, 2, 9, 9, 14], which matches the expected output.
Code Solutions
function cumulativeSum(scores) {
const res = new Array(scores.length);
let running = 0;
for (let i = 0; i < scores.length; i++) {
running += scores[i];
res[i] = running;
}
return res;
}
// Driver code
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (input.length) {
const n = input[0];
const scores = input.slice(1, n+1);
const result = cumulativeSum(scores);
console.log(result.join(' '));
}#include <bits/stdc++.h>
using namespace std;
vector<long long> cumulativeSum(const vector<long long>& scores) {
vector<long long> res(scores.size());
long long running = 0;
for (size_t i = 0; i < scores.size(); ++i) {
running += scores[i];
res[i] = running;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
vector<long long> scores(n);
for(int i=0;i<n;++i) cin>>scores[i];
vector<long long> result = cumulativeSum(scores);
for(size_t i=0;i<result.size();++i){
if(i) cout << ' ';
cout << result[i];
}
cout << '\n';
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static long[] cumulativeSum(long[] scores) {
long[] res = new long[scores.length];
long running = 0;
for (int i = 0; i < scores.length; i++) {
running += scores[i];
res[i] = running;
}
return res;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
long[] scores = new long[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
scores[i] = Long.parseLong(st.nextToken());
}
long[] result = cumulativeSum(scores);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
if (i > 0) sb.append(' ');
sb.append(result[i]);
}
System.out.println(sb.toString());
}
}def cumulative_sum(scores):
res = []
running = 0
for v in scores:
running += v
res.append(running)
return res
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit()
n = int(data[0])
scores = list(map(int, data[1:1+n]))
result = cumulative_sum(scores)
print(' '.join(map(str, result)))function cumulativeSum(scores) {
const res = new Array(scores.length);
let running = 0;
for (let i = 0; i < scores.length; i++) {
running += scores[i];
res[i] = running;
}
return res;
}
// Driver code
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (input.length) {
const n = input[0];
const scores = input.slice(1, n+1);
const result = cumulativeSum(scores);
console.log(result.join(' '));
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.