# Running Sum of 1D Array

Learn how to solve the LeetCode algorithm 'Running Sum of 1D Array' in four simple steps.

For this Leetcode problem we write an algorithm that accepts an input of an integer array `nums`, and output an integer array which contains the elements from `nums`, but with each item updated to reflect the running sum.

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 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`

## Psuedo-code

The title, description, and the supporting inputs & outputs of this algorithm show us that we essentially need to create a tally or counter of some sort that increments by the value of each item we iterate through in the provided `nums` array. Then, for every item in the `nums` array, we must update it to reflect the running sum at the given point, and then return an array of the same length, but with all of the values updated accordingly.

Our psuedo-code should be rather cut and dry, like so:

``````// create a variable to keep track of the running sum/tally
// create a new int[] array to store our updated values
// iterate through the nums array
// for every iteration, increment the running sum
// then update the value of the current index to be the running sum

// return the array of running sums
``````

## Solving the Algorithm

Now that we've walked through our psuedo-code, let's solve the problem in code, starting with the stub class we're provided:

### 1. Initialize `runningSum` variable and `runningSums` array

By initializing a `runningSum` variable, we will then be able to maintain some sort of reference or pointer to the current tally of values we've iterated to at any given point. This will allow us to set the values accordingly in the `runningSums` array which will be the return value from our function.

``````class Solution {
public int[] runningSum(int[] nums) {
// 1. variable to keep track of running sum\
int runningSum = 0;
// and array to keep track of updated values
int[] runningSums = new int[nums.length];

}
}
``````

### 2. Iterate through `sums` array

Creating a loop to iterate through the `nums` input array allows us to do some computation on every element of the array in order to generate the correct values to be used in the `runningSums` output array.

``````class Solution {
public int[] runningSum(int[] nums) {
// 1. variable to keep track of running sum\
int runningSum = 0;
// and array to keep track of updated values
int[] runningSums = new int[nums.length];

// 2. iterate through nums array
for (int i = 0; i < nums.length; i++) {
// do some magic
}
}
}
``````

### 3. Increment `runningSums` with each pass

As we iterate through each index of `nums`, we must first increment the value of `runningSums` so that it reflects the current tally. Afterwards, we will update the corresponding index of `runningSums` to reflect the `runningSum` for this given iteration in the loop.

``````class Solution {
public int[] runningSum(int[] nums) {
// 1. variable to keep track of running sum\
int runningSum = 0;
// and array to keep track of updated values
int[] runningSums = new int[nums.length];

// 2. iterate through nums array
for (int i = 0; i < nums.length; i++) {
// 3. increment runningSum by the value of
// the current index in nums array
runningSum = runningSum + nums[i];
// then add the value to our runningSums array
runningSums[i] = runningSum;
}
}
}
``````

### 4. Return the `runningSums` array

Last but not least, we must return the `runningSums` array from our function after we have generated the proper values.

``````class Solution {
public int[] runningSum(int[] nums) {
// 1. variable to keep track of running sum\
int runningSum = 0;
// and array to keep track of updated values
int[] runningSums = new int[nums.length];

// 2. iterate through nums array
for (int i = 0; i < nums.length; i++) {
// 3. increment runningSum by the value of
// the current index in nums array
runningSum = runningSum + nums[i];
// then add the value to our runningSums array
runningSums[i] = runningSum;
}
// 4. return runningSums array
return runningSums;
}
}
``````

## Recap and Live Example

This LeetCode problem helps us exercise some fundamental skills that will be used throughout many algorithms that we solve going forward.

View the REPL for this problem here:
https://repl.it/@TimWheeler/RunningSumOf1DArray

Shoot me an email at `[email protected]` with any questions and if you enjoyed this post make sure to comment and subscribe below! 👇

Help us improve our content