Running Sum of 1d Array
Understanding the Problem
We're given an array and need to produce a new array where each element at index i is the sum of all elements from index 0 through i in the original array. This is also called a prefix sum, a building block that appears in range-sum queries, subarray-sum problems, and 2D cumulative sums.
The first element stays the same, since it is the sum of itself. The second element is the sum of the first two, the third is the sum of the first three, and so on. Each running sum value builds on the previous one: once the running sum up to index i - 1 is known, the running sum at index i equals runningSum[i - 1] + nums[i]. That recurrence is what makes an efficient solution possible.
Key Constraints:
1 <= nums.length <= 1000→ With at most 1000 elements, even an O(n^2) approach stays well under typical time limits, so correctness matters more than shaving constants here.-10^6 <= nums[i] <= 10^6→ Values can be negative. The running sum can reach 10^9 in magnitude (1000 elements times 10^6 each), which still fits within a signed 32-bit integer (max about 2.1 x 10^9), sointdoes not overflow.
Approach 1: Brute Force (Recompute Each Sum)
Intuition
For each index i, sum the elements from 0 to i. This follows the definition of running sum directly: every output position starts a fresh summation from the beginning of the array. It does redundant work, recomputing overlapping prefixes, but it is a correct baseline to improve on.
Algorithm
- Create a result array of the same length as
nums. - For each index
ifrom0ton - 1: - Initialize a sum to 0.
- For each index
jfrom0toi, addnums[j]to the sum. - Set
result[i]to this sum. - Return the result array.
Example Walkthrough
Take nums = [1, 2, 3, 4]. For each output index i, the inner loop re-adds every element from 0 to i, so the same early values are summed again at each step.
Code
- Time Complexity: O(n^2). For each of the n elements, we sum up to n elements. The total work is 1 + 2 + 3 + ... + n = n(n+1)/2, which is O(n^2).
- Space Complexity: O(n). We create a result array of size n.
The brute force recomputes overlapping prefixes. The next approach reuses the previous result instead of summing from scratch each time.
Approach 2: Prefix Sum (New Array)
Intuition
The running sum at index i is the sum of elements from 0 to i, which expands to sum(0..i) = sum(0..i-1) + nums[i]. So each running sum equals the previous running sum plus the current element. That recurrence replaces the inner loop with a single addition.
We can compute the whole array in one pass. Keep a running total, add each element to it, and write that total to the corresponding output position. Because each value reuses the one already computed, the O(n^2) work collapses to O(n).
Algorithm
- Create a result array of the same length as
nums. - Set
result[0] = nums[0](the first element has no previous sum to build on). - For each index
ifrom1ton - 1: - Set
result[i] = result[i - 1] + nums[i]. - Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n). We make a single pass through the array, doing O(1) work at each index.
- Space Complexity: O(n). We allocate a result array of size n.
This approach runs in optimal time but uses O(n) extra space for the result array. If we are allowed to modify the input, we can drop that extra array and write the running sum back into nums itself.
Approach 3: In-Place Prefix Sum (Optimal)
Intuition
When modifying the input array is acceptable, the result array is unnecessary. Iterate from index 1 and add the previous element to the current one. After the loop, nums holds the running sum, with no extra allocation.
Writing into the input array is safe only because of the left-to-right order. The loop maintains an invariant: before processing index i, every position 0 through i - 1 already holds its final running sum. When we run nums[i] += nums[i - 1], nums[i] still holds the original input value and nums[i - 1] already holds runningSum[i - 1], so the result is original_nums[i] + runningSum[i - 1] = runningSum[i]. Each position is read once after it is finalized and written once, so no value is overwritten before it is needed.
Algorithm
- For each index
ifrom1ton - 1: - Add
nums[i - 1]tonums[i]. - Return
nums.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the array with O(1) work per element.
- Space Complexity: O(1). No additional data structures. We modify the input array in place.