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^6The key idea behind #1480 Running Sum of 1d Array is understanding the concept of a prefix sum. Instead of recalculating the total for each position, we maintain a cumulative sum while traversing the array. At each index, the running sum is simply the sum of the current element and all previous elements.
You can iterate through the array once and keep a variable that stores the cumulative value. Each step updates the running total and records it as the result for that index. This approach avoids repeated calculations and ensures efficiency.
Another variation is updating the array in-place, where each element becomes the sum of itself and the previous element (e.g., nums[i] = nums[i] + nums[i-1]). This works because the previous index already stores the correct running total.
The algorithm processes each element exactly once, leading to a linear time complexity. Depending on whether a new array is used or the original array is modified, the space complexity can vary between constant and linear.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum with New Array | O(n) | O(n) |
| In-place Prefix Sum | O(n) | O(1) |
Knowledge Center
Use these hints if you're stuck. Try solving on your own first.
Think about how we can calculate the i-th number in the running sum from the (i-1)-th number.
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.
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.
1function runningSum(nums) {
2 let result = [];
3 let sum = 0;
4 for (let num of nums)
The JavaScript implementation employs a for...of loop to calculate the running sum by appending the current running total to the result array. The calculated running sums are logged to the console.
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.
Time Complexity: O(n)
Space Complexity: O(1) since only the input array is modified.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to compute cumulative totals efficiently and avoid repeated calculations. They are widely used in problems involving range queries, subarray sums, and dynamic programming optimizations.
While this exact problem may not frequently appear in FAANG interviews, the concept of prefix sums is very common. Understanding this pattern helps solve many range-sum, cumulative sum, and subarray problems.
A simple array is sufficient for this problem. You can either create a new array to store the running sums or modify the input array directly using the prefix sum technique.
The optimal approach uses the prefix sum technique. As you iterate through the array, maintain a cumulative sum and store it for each index. This allows the running sum to be computed in a single pass with O(n) time complexity.
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.