Cumulative Subsequence Sum — Problem Statement & Solution Guide
Problem Description
You are given an array of length N containing integer values. Your task is to produce a new array of the same length where the i-th element is the sum of the first i elements of the original array. In other words, compute the prefix sums of the input sequence. The input consists of two lines: the first line contains the integer N, and the second line contains N space‑separated integers. The output should be a single line with N space‑separated integers representing the cumulative sums.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Cumulative Subsequence Sum"
WHY DOES IT MATTER?
Prefix sums embody the incremental DP pattern where each state depends only on its immediate predecessor, teaching candidates how to turn quadratic recomputation into linear work—a skill that scales to many algorithmic challenges.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the sum of the first i elements can be derived from the sum of the first i‑1 elements, eliminating the need for nested loops and reducing time from O(N^2) to O(N).
REAL-WORLD CONNECTION
In distributed logging systems, a cumulative counter (e.g., total bytes transferred) is updated per event; each update adds the new value to the previous total, mirroring the prefix‑sum computation across a time‑ordered stream.
During an interview, write the recurrence first (dp[i] = dp[i‑1] + a[i]), then translate it directly into a tight for‑loop; keep an eye on off‑by‑one indexing and whether you need a separate output array or can reuse the input.
COMPLEXITY AT A GLANCE
O(N)O(N)Core Theory — Why This Approach?
The problem asks for the prefix sum (cumulative sum) of an array, a classic example of a one‑dimensional dynamic programming recurrence. The i‑th prefix sum can be expressed as dp[i] = dp[i‑1] + a[i], where dp[i] stores the sum of the first i+1 elements (0‑based indexing). This recurrence captures the optimal substructure: the solution for a larger prefix builds directly on the solution for the previous prefix, eliminating the need to recompute sums from scratch. Naïve methods that sum each prefix independently run in O(N^2) time because each of the N positions would iterate over up to N elements, which quickly becomes prohibitive for large N (e.g., N = 10^6). By recognizing the overlapping sub‑problems and reusing the previously computed sum, we achieve a linear‑time solution that scales gracefully.
In practice, this DP formulation translates to a simple loop that maintains a running total. Each iteration updates the running total with the current element and stores it in the result array. The algorithm runs in O(N) time and O(N) auxiliary space for the output (or O(1) extra space if we overwrite the input). This pattern—building answers incrementally using previously computed results—is a cornerstone of dynamic programming and appears in many higher‑level problems such as range‑sum queries, sliding‑window aggregates, and cumulative frequency tables.
Interview Questions on This Problem
Q1How would you compute prefix sums for a massive stream of numbers where you cannot store the entire array in memory?
Maintain a running total variable and emit each cumulative sum as you read each number from the stream; this uses O(1) extra space and O(N) time, leveraging the same recurrence dp[i] = dp[i‑1] + a[i].
Q2Given an array, how can you answer multiple range‑sum queries efficiently after a single preprocessing step?
Preprocess the array into a prefix‑sum array in O(N) time; then each range sum [l, r] can be answered in O(1) as prefix[r] - prefix[l‑1] (handling l = 0 as a special case).
Q3Why might a candidate choose to compute prefix sums in‑place versus allocating a new array, and what are the trade‑offs?
In‑place computation saves memory (O(1) extra space) and can improve cache locality, but it destroys the original data, which may be needed later; allocating a new array preserves input at the cost of O(N) additional space.
Examples
Input
5 1 2 3 4 5
Output
1 3 6 10 15
Explanation: The cumulative sums are computed as follows: 1, 1+2=3, 1+2+3=6, 1+2+3+4=10, 1+2+3+4+5=15.
Input
3 -1 0 5
Output
-1 -1 4
Explanation: First element: -1. Second element: -1+0=-1. Third element: -1+0+5=4.
Input
4 1000000000 -1000000000 5 5
Output
1000000000 0 5 10
Explanation: Prefix sums: 1000000000, 1000000000-1000000000=0, 0+5=5, 5+5=10.
Constraints
- 1 <= N <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The cumulative sums fit within a 64‑bit signed integer.
Optimal Approach & Strategy
Maintain a single running sum while traversing the array once; at each step add the current element to the running sum and record it as the i‑th prefix sum. This yields O(N) time and O(N) output space.
Brute Force Approach
For each position i, sum the first i elements by iterating from the start each time, resulting in a nested loop. This approach runs in O(N^2) time and is too slow for large N.
Verified Code Solutions
function solution(nums) { return nums.reduce((a, b) => a + b, 0); }class Solution { public: int solution(vector<int>& nums) { int sum = 0; for (int num : nums) { sum += num; } return sum; } };class Solution { public int solution(int[] nums) { int sum = 0; for (int num : nums) { sum += num; } return sum; } }def solution(nums): return sum(nums)function solution(nums) { return nums.reduce((a, b) => a + b, 0); }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.