Watch 10 video solutions for Running Sum of 1d Array, a easy level problem involving Array, Prefix Sum. This walkthrough by Knowledge Center has 25,014 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |