Leetcode 1480. Running Sum of 1d Array (Typescript)

Today we will be going over Leetcode 1480 - Running Sum of 1d Array. Our problem is a bit unique in that it really is just an introduction to the concept of using prefix sums. As such, this will be a relatively short post. But it will serve as the basis for a lot of problems we will see in the future. Prefix sums are a very common concept in competitive programming and algorithms in general. The prefix sum technique is the idea to take a list of numbers, and transform it such that each number in the list it the cumulate sum of itself and all the previous numbers in the list. This is a unique property that can help us make certain problems that would normally take O(n^2) time take O(n) time. Thats a big difference!

Problem Statement and Analysis

With that light introduction done let's take a look at the problem statement:

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.

From this description we can see we are taking in some array nums and transforming in a way such that each index will now be the sum of itself and all the previous numbers in the array. So for example, if we have an array like:

[1, 2, 3, 4];

The running sum would be:

[1, 3, 6, 10];

We can accomplish this using a simple for loop and simple addition of the current index value and the value we calculated in the previous index. The only caveat is that we need to make sure that when we look "backwards" we don't inadvertently go out of bounds. This is easily solved by simply starting our loop at index 1 and setting the initial value of the running sum to the first index of the array's value.

Solution

function runningSum(nums: number[]): number[] {
  const runningSum = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    runningSum[i] = nums[i] + runningSum[i - 1];
  }

  return runningSum;
}

(Note: I am using a new array and not updating the original array. You could simplify this and just directly update the original array. Always read the requirements of the problem you are solving to see whether keeping a copy of the original array is useful or not.)

Time and Space Complexity Analysis

This is going to be the shortest time and space complexity analysis I have ever done. 😂 A single for loop has time complexity O(n). Now for space complexity because I created a new array that matches the length of the data it's actually O(n). However of course if you modify the nums passed in the function arguments then the space complexity becomes O(1). But again depending on the requirements of the problem you solve that may or may not be practical.

Thanks and best of luck on your coding journey!