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.
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; }}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.