Solution For Running Sum Of 1d Array
Problem Statement:
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:
Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained by adding previous elements. [1, 1+2, 1+2+3, 1+2+3+4].
Solution:
In this problem, we are given an array nums and we are supposed to find the running sum of the array where the running sum is defined as the sum of all the elements from the beginning of the array up to that element.
We can solve this problem by using a simple method. We first create a new array of the same length as the input array and initialize it with 0. Then we iterate through the input array and add the previous element to the current element. This will give us the running sum. Finally we return the resultant array.
Here’s the algorithm:
- Initialize a new array res of the same length as the input array with all elements set to 0.
- Initialize a variable sum to 0.
- Iterate through the input array nums.
- For each element i of nums, add it to sum and assign the value of sum to res[i].
- Return the resultant array res.
Here’s the python code:
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
res = [0]*len(nums)
sum = 0
for i in range(len(nums)):
sum += nums[i]
res[i] = sum
return res
This solution has a time complexity of O(n) as we iterate through the input array only once and a space complexity of O(n) as we create a new array of the same length as the input array.
Step by Step Implementation For Running Sum Of 1d Array
public int[] runningSum(int[] nums) { // create an empty array to store the running sum int[] runningSum = new int[nums.length]; // initialize the running sum to be the first element in the input array runningSum[0] = nums[0]; // iterate through the input array, starting at the second element for (int i = 1; i < nums.length; i++) { // the running sum at index i is equal to the sum of all elements up to and including index i runningSum[i] = runningSum[i - 1] + nums[i]; } return runningSum; }
def runningSum(nums): # create an empty list to store the running sum running_sum = [] # iterate over the input list for i in range(len(nums)): # if it's the first element, simply append it # to the list if i == 0: running_sum.append(nums[i]) # for the remaining elements, calculate the sum # by adding the current element to the previous sum else: running_sum.append(nums[i] + running_sum[i-1]) # return the running sum return running_sum
/** * @param {number[]} nums * @return {number[]} */ var runningSum = function(nums) { // create a variable to store the running sum let sum = 0; // create a new array to store the running sum let runningSum = []; // iterate through the nums array for(let i = 0; i < nums.length; i++) { // add the current number to the sum sum += nums[i]; // push the sum to the runningSum array runningSum.push(sum); } // return the runningSum array return runningSum; };
vectorrunningSum(vector & nums) { int sum = 0; vector res; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; res.push_back(sum); } return res; }
public int[] RunningSum(int[] nums) { // create an empty array to store the running sum int[] runningSum = new int[nums.Length]; // set the first element of the running sum array to the first element of the input array runningSum[0] = nums[0]; // loop through the input array, starting at the second element for (int i = 1; i < nums.Length; i++) { // set the value of the current element in the running sum array // to the value of the previous element in the running sum array, plus the value of the current element in the input array runningSum[i] = runningSum[i-1] + nums[i]; } return runningSum; }