## DEV Community is a community of 642,334 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # Solution: Running Sum of 1d Array seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・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.

#### 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…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 = nums
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 =  * len(nums)
ans = nums
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 = nums;
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 = nums;
for (int i = 1; i < nums.size(); i++)
ans[i] = ans[i-1] + nums[i];
return ans;
}
};
``````