Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Running Sum of 1d Array (easy)

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

Given a one-dimensional array of integers, create a new array that represents the running sum of the original array.

The running sum at position i in the new array is calculated as the sum of all the numbers in the original array from the 0th index up to the i-th index (inclusive). Formally, the resulting array should be computed as follows: result[i] = sum(nums[0] + nums[1] + ... + nums[i]) for each i from 0 to the length of the array minus one.

Examples

Example 1

  • Input: [2, 3, 5, 1, 6]
  • Expected Output: [2, 5, 10, 11, 17]
  • Justification:
    • For i=0: 2
    • For i=1: 2 + 3 = 5
    • For i=2: 2 + 3 + 5 = 10
    • For i=3: 2 + 3 + 5 + 1 = 11
    • For i=4: 2 + 3 + 5 + 1 + 6 = 17

Example 2

  • Input: [1, 1, 1, 1, 1]
  • Expected Output: [1, 2, 3, 4, 5]
  • Justification: Each element is simply the sum of all preceding elements plus the current element.

Example 3

  • Input: [-1, 2, -3, 4, -5]
  • Expected Output: [-1, 1, -2, 2, -3]
  • Justification: Negative numbers are also summed up in the same manner as positive ones.

Constraints:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

Solution

The slow way is to start again at every index. For index 3 you add nums[0] + nums[1] + nums[2] + nums[3]. For index 4 you add five numbers. Each index costs more than the one before it, so the total work grows as N squared.

The repeated work is the problem. When you build the answer for index 3, you add up everything before index 3. You already did that one step earlier, for index 2. Nothing changed in between.

So keep the earlier answer instead of building it again. The running sum at index i is the running sum at index i - 1 plus nums[i]. That is one addition per index, no matter how far along you are.

Index 0 is the only special case. Nothing comes before it, so result[0] is just nums[0].

Image

This idea has a name. A prefix sum is an array where each entry holds the total of everything up to that position. The array you are asked to return is exactly that, which makes this the plainest prefix sum question in the chapter.

Step-by-step Algorithm

  1. Create a result array with the same length as nums.
  2. Set result[0] to nums[0], because nothing comes before index 0.
  3. For each index i from 1 to the end, set result[i] to result[i - 1] + nums[i].
  4. Return result.

The code also checks for a missing or empty input before anything else. The constraints promise at least one element, so that check can never fire here. It is there so the function stays safe if you copy it into code that makes no such promise.

Algorithm Walkthrough

mediaLink

The first element has nothing before it, so result[0] is just 2

1 of 6

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Single pass through the array: The algorithm uses a single loop to traverse the input array nums. For each element, it calculates the running sum by adding the current element to the sum of the previous elements. This loop runs for each element in the array, so it takes O(N) time, where N is the length of the input array.

Overall time complexity: O(N), where N is the number of elements in the input array.

Space Complexity

  • Output array: The algorithm creates a new array result to store the running sum. This array has the same length as the input array, so the space complexity for the result array is O(N), where N is the number of elements in the input array.

  • Additional variables: The algorithm uses a few extra variables (i), which take constant space, O(1).

Overall space complexity: O(1) extra space, plus the O(N) output array. The result array is the answer we return, so we do not count it as extra space.

rcreddyn

rcreddyn

· 2 months ago

Is the check for empty array or null necessary as contraints state the minimum size of the array is 1?

Show 1 reply
E

ethanedge

· 3 months ago

The solution states:

  • Check for Edge Cases:
    • If the input array is null or has no elements, return an empty array since there's nothing to process.

However, the question states:

Constraints:

  • 1 <= nums.length <= 1000

Which could be confusing to some as it's contradictory.

Show 2 replies
Aravind Badiger

Aravind Badiger

· 2 years ago

Whether we consider a returning result variable or replace elements in the original array the space complexity is O(1)

Show 2 replies
Rafael Scarduelli

Rafael Scarduelli

· 3 years ago

This happens on line 4 when trying to get nums[0].

Show 1 reply

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity