Running Sum of 1D Array

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 tim@timwheeler.com with any questions and if you enjoyed this post make sure to comment and subscribe below! 👇