Solution: Running Sum of 1d Array
Tags: algorithms, javascript, java, python
Published: 2021-05-03 09:32:36

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/running-sum-of-1d-array/discuss/1189005).*

---

#### [Leetcode Problem #1480 (*Easy*): Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```