Running Sum of 1d Array
EasyPrompt
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^6
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly follows the definition of a running sum. For each element at index i in the output array, we calculate the sum of all elements from the beginning of the input array up to index i by iterating from the start every time.
Algorithm
- Create a new integer array
resultof the same size asnums. - Loop through the input array
numswith indexifrom0tonums.length - 1. - Inside the loop, initialize a variable
currentSumto0. - Start a nested loop with index
jfrom0toi. - Add
nums[j]tocurrentSum. - After the inner loop, assign
currentSumtoresult[i]. - After the outer loop finishes, return the
resultarray.
Walkthrough
We initialize a new result array, runningSum, with the same size as the input nums. We then iterate through nums from i = 0 to n-1. In each iteration, we use another nested loop that runs from j = 0 to i to sum up the elements nums[0] through nums[i]. This sum is then stored in runningSum[i]. This process is repeated for all indices, resulting in redundant calculations as we re-calculate sums for previous elements in every step.
class Solution { public int[] runningSum(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = 0; j <= i; j++) { currentSum += nums[j]; } result[i] = currentSum; } return result; }}Complexity
Time
O(n^2), where n is the number of elements in the input array. The nested loops result in a quadratic number of operations. For each element `i`, we perform `i+1` additions.
Space
O(n), where n is the number of elements. We create a new array of size `n` to store the results. If the output array is not considered extra space, it would be O(1).
Trade-offs
Pros
Simple to understand and implement directly from the problem definition.
Cons
Highly inefficient due to redundant calculations.
Will be very slow for large input arrays, potentially leading to a 'Time Limit Exceeded' error in competitive programming platforms.
A more efficient approach is to realize that the running sum at index i is simply the running sum at index i-1 plus the current element nums[i]. This avoids the need for nested loops and repeated calculations.
Algorithm
- Create a new integer array
resultof the same size asnums. - Set
result[0] = nums[0]. - Loop through the input array
numswith indexifrom1tonums.length - 1. - Calculate
result[i] = result[i-1] + nums[i]. - After the loop, return the
resultarray.
Walkthrough
We can compute the running sum in a single pass. We create a new array, result, to store the running sums. The first element of the result array is the same as the first element of the input array (result[0] = nums[0]). Then, we iterate from the second element (i = 1) to the end of the array. For each element, we calculate its running sum using the formula result[i] = result[i-1] + nums[i]. This way, each running sum is calculated in constant time using the previously computed value.
class Solution { public int[] runningSum(int[] nums) { int n = nums.length; int[] result = new int[n]; result[0] = nums[0]; for (int i = 1; i < n; i++) { result[i] = result[i-1] + nums[i]; } return result; }}Complexity
Time
O(n), where n is the number of elements in the array. We iterate through the array only once.
Space
O(n), as we use an additional array of size `n` to store the running sum.
Trade-offs
Pros
Much more efficient than the brute-force approach with a linear time complexity.
Still conceptually simple and easy to follow.
Cons
Uses extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
This is the most optimal approach in terms of space complexity. Instead of creating a new array for the results, we can modify the input array itself to store the running sum. This is possible because once we calculate the running sum for an index, the original value at that index is no longer needed for subsequent calculations.
Algorithm
- Loop through the input array
numswith indexifrom1tonums.length - 1. - Update the current element by adding the previous element's value:
nums[i] = nums[i] + nums[i-1]. - After the loop, the
numsarray itself contains the running sums. Returnnums.
Walkthrough
We can optimize the previous approach by eliminating the need for a separate result array. We can use the input array nums to store the running sum. We start our iteration from the second element (index 1). For each index i, we update the element nums[i] by adding the value of the previous element nums[i-1] to it. Since nums[i-1] already holds the running sum up to that point, nums[i] + nums[i-1] gives the new running sum at index i. After the loop completes, the input array nums is transformed into the running sum array.
class Solution { public int[] runningSum(int[] nums) { for (int i = 1; i < nums.length; i++) { // The current element becomes the sum of itself and the previous element // which is already the running sum up to that point. nums[i] += nums[i - 1]; } return nums; }}Complexity
Time
O(n), where n is the number of elements in the array. We perform a single pass through the array.
Space
O(1), as we modify the array in-place and do not use any additional space that scales with the input size. The space for the output is reused from the input.
Trade-offs
Pros
Most efficient in terms of both time and space.
No extra memory allocation is needed.
Cons
Modifies the original input array, which might not be desirable in all situations. If the original array is needed later, a copy must be made first.
Solutions
Solution
public class Solution { public int[] RunningSum(int[] nums) { for (int i = 1; i < nums.Length; ++i) { nums[i] += nums[i - 1]; } return nums; }}class Solution {public int[] runningSum(int[] nums) { for (int i = 1; i < nums.length; ++i) { nums[i] += nums[i - 1]; } return nums; }}class Solution {public: vector<int> runningSum(vector<int> &nums) { for (int i = 1; i < nums.size(); ++i) nums[i] += nums[i - 1]; return nums; }};class Solution: def runningSum(self, nums: List[int] ) -> List[int]: return list(accumulate(nums))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.