DEV Community

loading...
Cover image for Solution: Running Sum of 1d Array

Solution: Running Sum of 1d Array

seanpgallivan profile image seanpgallivan ・3 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #1480 (Easy): Running Sum of 1d Array


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.


Examples:

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

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

While this is not a terribly challenging problem, it's a good introduction to the concept of a prefix sum array. Prefix sum arrays have many uses in more complex algorithms and can sometimes help reduce the time complexity of a advanced solution by an order of magnitude.

In a prefix sum array, we will create a duplicate array which contains the running sum of the elements 0 to i of our original array (nums) for each index i of our prefix sum array (ans). (Note: We can lower the space complexity by using an in-place approach with nums directly and mutating it into its own prefix sum array, if there is no compelling reason to avoid modifying a function argument.)

Since we'll need to build on a previous running total, we should start our iteration at i = 1 and copy over the first element from nums to ans. Then we just iterate through nums and add each element (nums[i]) to the previous running total (ans[i-1]) to create the new running total (ans[i]).

When we're done, we can return ans.

  • Time Complexity: O(N) where N is the length of nums
  • Space Complexity: O(N) for our running sum array
    • or O(1) with an in-place approach

Javascript Code:


(Jump to: Problem Description || Solution Idea)

var runningSum = function(nums) {
    let ans = new Array(nums.length)
    ans[0] = nums[0]
    for (let i = 1; i < nums.length; i++)
        ans[i] = ans[i-1] + nums[i]
    return ans
};
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        ans = [0] * len(nums)
        ans[0] = nums[0]
        for i in range(1, len(nums)):
            ans[i] = ans[i-1] + nums[i]
        return ans
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

class Solution {
    public int[] runningSum(int[] nums) {
    int[] ans = new int[nums.length];
    ans[0] = nums[0];
    for (int i = 1; i < nums.length; i++)
        ans[i] = ans[i-1] + nums[i];
    return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> ans(nums.size());
        ans[0] = nums[0];
        for (int i = 1; i < nums.size(); i++)
            ans[i] = ans[i-1] + nums[i];
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide