Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
Example 1:
Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Example 2:
Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Example 3:
Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]
Constraints:
1 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6Problem Overview: You receive an integer array nums. For each index i, compute the cumulative sum from index 0 to i. The result array stores these progressive totals, commonly called a running sum or prefix sum. This pattern appears frequently in problems involving cumulative totals, range queries, and sliding windows.
Approach 1: Iterative Accumulation (O(n) time, O(n) space)
Create a new result array and build the running sum while iterating through the input. Start with result[0] = nums[0]. For each next index, compute result[i] = result[i-1] + nums[i]. Each step reuses the previous prefix value instead of recomputing the entire sum. The algorithm performs a single linear pass over the array, making it efficient and straightforward. This version is useful when you must preserve the original input array or when the problem explicitly requires a separate output structure.
Approach 2: In-Place Modification (O(n) time, O(1) space)
The running sum can also be computed directly inside the input array. Iterate from index 1 to the end and update each element as nums[i] += nums[i-1]. Because nums[i-1] already stores the cumulative total up to the previous index, adding it produces the correct running sum. This approach leverages the idea behind prefix sums while minimizing extra memory usage. Only one traversal is required, and the array gradually transforms into the prefix array.
This in-place strategy is common in interview settings when memory optimization matters. It avoids allocating additional arrays and keeps the implementation extremely compact. The only tradeoff is that the original input values are overwritten.
Recommended for interviews: Interviewers expect the prefix-sum insight quickly. Demonstrating the iterative accumulation approach first shows you understand the cumulative relationship between elements. Then optimizing to the in-place version signals awareness of space complexity and memory tradeoffs. Both run in O(n) time, but the in-place method achieves O(1) auxiliary space, which is typically considered the optimal solution.
The running sum technique forms the foundation for more advanced prefix sum problems such as range sum queries, subarray sum detection, and difference arrays. Mastering this pattern makes many seemingly complex array problems easier to reason about.
This approach involves iterating through the array nums and calculating the running sum iteratively. Use an accumulator variable to keep the sum of elements encountered so far, and place this running sum into the result array.
This C program uses a function runningSum which takes the original array nums, its size, and an array returnArr to store the running sums. An accumulator sum keeps track of the cumulative total as we iterate over the array.
Time Complexity: O(n) where n is the number of elements in the array.
Space Complexity: O(1) since we're modifying the array in place.
For the in-place approach, iterate through the array nums, and update each position directly to the running sum. This method reduces space usage by avoiding the creation of a separate result array.
In this C solution, the running sum is calculated in place by iterating over the array starting from the second element. Each element is updated as the sum of itself and its predecessor.
Time Complexity: O(n)
Space Complexity: O(1) since only the input array is modified.
We directly traverse the array. For the current element nums[i], we add it with the prefix sum nums[i-1] to get the prefix sum nums[i] of the current element.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Accumulation | Time Complexity: O(n) where n is the number of elements in the array. |
| In-Place Modification | Time Complexity: O(n) |
| Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Accumulation (Extra Array) | O(n) | O(n) | When the original array must remain unchanged or when returning a separate result array |
| In-Place Modification | O(n) | O(1) | Best for interviews and memory-constrained scenarios where modifying the input array is allowed |
Running Sum of 1d Array | LeetCode 1480 | C++, Java, Python • Knowledge Center • 25,014 views views
Watch 9 more video solutions →Practice Running Sum of 1d Array with our built-in code editor and test cases.
Practice on FleetCode