Running Sum of 1d Array
Last Updated: March 29, 2026
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 known as a prefix sum, one of the most fundamental building blocks in algorithm design.
The first element stays the same (it's just 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. Notice that each running sum value builds on the previous one. If you already know the running sum up to index i - 1, the running sum at index i is just runningSum[i - 1] + nums[i]. That observation is the key to solving this efficiently.
Key Constraints:
1 <= nums.length <= 1000→ With at most 1000 elements, even an O(n^2) approach runs comfortably under time limits. An O(n) solution is trivial to achieve.-10^6 <= nums[i] <= 10^6→ Values can be negative. The running sum can grow as large as 10^9 in magnitude (1000 elements times 10^6 each), which fits within a 32-bit integer.
Approach 1: Brute Force (Recompute Each Sum)
Intuition
The most straightforward way: for each index i, sum up all elements from 0 to i. This directly follows the definition of running sum without trying to be clever about it. For each position, start a fresh summation from the beginning of the array.
This is what most people would write if they're just translating the problem statement into code without thinking about redundancy.
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
Input:
For each index, we sum all elements from 0 to i:
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.
This approach works but recomputes the same sums repeatedly. What if we built each running sum incrementally from the previous one instead of starting from scratch?
Approach 2: Prefix Sum (New Array)
Intuition
The brute force recomputes the same sums over and over. But there's a simple relationship staring at us: runningSum[i] = runningSum[i - 1] + nums[i]. Each running sum is just the previous running sum plus the current element.
So instead of nested loops, we can do a single pass. Keep a running total, add each element to it, and that's the answer for that position. This is the prefix sum technique, and it's one of those patterns that shows up constantly in more complex problems.
The running sum at index i is defined as the sum of elements from 0 to i. If we expand that: sum(0..i) = sum(0..i-1) + nums[i]. So the running sum at any position is just the previous running sum plus the current element. This recurrence lets us compute each value in O(1) using the value we already computed, turning an O(n^2) process into O(n).
This is the prefix sum technique. It's deceptively simple here, but the same idea powers range sum queries, subarray sum problems, and even 2D cumulative sums in more advanced settings.
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 is optimal in time, but uses O(n) extra space for the result array. Can we compute the running sum in-place by modifying the input array directly?
Approach 3: In-Place Prefix Sum (Optimal)
Intuition
If modifying the input array is acceptable, we can skip creating a new array entirely. Just iterate from index 1 and add the previous element to the current one. After the loop, nums itself holds the running sum.
This is the cleanest version of the solution. One loop, one line of logic, no extra space.
It's the same recurrence as Approach 2: runningSum[i] = runningSum[i-1] + nums[i]. The difference is that we store the result directly in the input array. After processing index i - 1, nums[i - 1] already holds runningSum[i - 1]. So when we execute nums[i] += nums[i - 1], we're computing original_nums[i] + runningSum[i - 1], which is exactly runningSum[i].
The order matters. We go left to right, and each position is updated exactly once. By the time we read nums[i - 1], it's already been converted to the running sum, which is exactly what we need.
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.