Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Solution: Running Sum of 1d Array (easy)
Table of Contents

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

To find a solution of this problem, we can employ a straightforward approach. Starting from the first element of the input array, we can traverse through each element, cumulatively summing up the values as we proceed and placing the running total at the corresponding index in the resulting array.

Image

Initially, the first element of the output array is the same as the input array since there are no preceding elements to add. From the second element onwards, every element in the output array is the sum of the current element in the input array and the previous element in the output array. This is because the previous element in the output array already contains the cumulative sum of all the previous elements in the input array.

Step-by-step Algorithm

  • Check for Edge Cases:

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

  • Initialize the Result Array:

    • Create an array of the same length as nums to store the running sum.
    • Set the first element of result equal to the first element of nums since the first element remains unchanged.

  • Compute the Running Sum:

    • Iterate through the array starting from index 1.
    • For each index, update the value in the result array by adding the previous sum to the current element.

  • Return the Running Sum Array:

    • After processing all elements, return the result array, which now contains the cumulative sum at each index.

Algorithm Walkthrough

Image

Initialization

  • Input: [2, 3, 5, 1, 6]
  • Create a result array with five elements.
  • Set the first element of result to 2.
  • Result after initialization: [2, _, _, _, _]

Step-by-Step Computation

  • Iteration 1 (i = 1)

    • Add the previous sum (2) to the current element (3).
    • Update result[1] to 5.
    • Result: [2, 5, _, _, _]

  • Iteration 2 (i = 2)

    • Add the previous sum (5) to the current element (5).
    • Update result[2] to 10.
    • Result: [2, 5, 10, _, _]

  • Iteration 3 (i = 3)

    • Add the previous sum (10) to the current element (1).
    • Update result[3] to 11.
    • Result: [2, 5, 10, 11, _]

  • Iteration 4 (i = 4)

    • Add the previous sum (11) to the current element (6).
    • Update result[4] to 17.
    • Result: [2, 5, 10, 11, 17]

Final Output

  • Running Sum Array: [2, 5, 10, 11, 17]
  • This array represents the cumulative sum at each step.

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(N), where N is the number of elements in the input array.

Mark as Completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity