Solution: Running Sum of 1d Array

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

---

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

---

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

---

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

Comments

[mahdi]

Thanks for this one