Jobs

Interviews

Discussions

Running Sum of 1d Array

Easy

Running Sum of 1d Array

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers?
Is the input array guaranteed to be valid, or should I handle cases like null or empty arrays?
Should the output array be a new array, or can I modify the input array in place?
Are the elements in the array integers, or can they be floating-point numbers?

Brute Force Solution

Approach

We need to find a running total for a list of numbers. The simplest way is to calculate each running total individually by summing all the preceding numbers in the list each time.

Here's how the algorithm would work step-by-step:

For the first number in the list, the running total is just that number itself.
For the second number, we add the first number to the second number to get its running total.
For the third number, we add the first number, the second number, and the third number together.
We continue this process for each number in the list, always adding up all the numbers from the beginning of the list up to the current number.
The running total for each number becomes a new list of running totals.

Code Implementation

def running_sum_brute_force(numbers):
    running_totals = []

    # Iterate through the input list to calculate running sums
    for current_index in range(len(numbers)):

        current_running_total = 0

        # Calculate the sum from the beginning to current index
        for previous_index in range(current_index + 1):
            current_running_total += numbers[previous_index]

        # Append current running total to the result
        running_totals.append(current_running_total)

    return running_totals

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element at index i, it calculates the running sum by iterating from the beginning of the array up to index i, performing i additions. Therefore, for the first element 1 addition is performed, for the second 2 additions and so on, until the nth element where n additions are performed. This results in a total of 1 + 2 + ... + n additions, which is equivalent to n(n+1)/2. This simplifies to O(n²).

Space Complexity

O(N) – The plain English explanation details creating a 'new list of running totals'. This implies the creation of a new array or list to store these running totals. The size of this new list will be the same as the input list, which we denote as N. Therefore, the auxiliary space required is proportional to the size of the input, N, leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to efficiently calculate the running sum of a sequence of numbers. Instead of recalculating the sum each time, we reuse the previous calculation. This incremental approach significantly speeds up the process.

Here's how the algorithm would work step-by-step:

Start with the first number in the sequence.
The initial running sum is simply that first number itself.
Move to the second number.
Add the current number to the previous running sum to get the new running sum.
Store this new running sum.
Repeat the previous two steps for each remaining number in the sequence.
Each new running sum is calculated by adding the current number to the *previous* running sum, avoiding redundant calculations.

Code Implementation

def runningSum(numbers):
    running_sums = [0] * len(numbers)

    # The first element is the initial running sum.
    running_sums[0] = numbers[0]

    for index in range(1, len(numbers)):
        # Accumulate the sum using the previous running sum
        running_sums[index] = running_sums[index - 1] + numbers[index]

    return running_sums

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. In each iteration, it performs a constant-time addition operation to update the running sum. Since the number of operations grows linearly with the size of the input array, the time complexity is O(n).

Space Complexity

O(1) – The algorithm modifies the input array in-place to store the running sum. It does not create any auxiliary data structures like new arrays, lists, or hash maps. Therefore, the space used is constant, regardless of the input size N, where N is the number of elements in the input array. The only extra memory used is for a few temporary variables during the addition operation, which occupies constant space.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array immediately to avoid processing invalid input.
Array with a single element	Return the input array itself, as the running sum of a single element is the element itself.
Array with large numbers that may cause integer overflow	Use a data type with a larger range (e.g., long) to store the running sum to prevent potential overflow.
Array with a large number of elements (scalability)	The iterative approach inherently has O(n) time complexity and O(1) space complexity (excluding the input), scaling efficiently.
Array with all elements being zero	The running sum will also be an array of zeros, which is a valid result.
Array containing negative numbers	The solution should correctly handle negative numbers by subtracting them from the running sum.
Array containing a mix of positive, negative, and zero values	The algorithm will correctly calculate cumulative sum regardless of sign of the individual numbers.
Extreme boundary values for array elements (Integer.MAX_VALUE/MIN_VALUE)	Be cautious of potential integer overflow when adding to the running sum and use a larger datatype if needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers?
Is the input array guaranteed to be valid, or should I handle cases like null or empty arrays?
Should the output array be a new array, or can I modify the input array in place?
Are the elements in the array integers, or can they be floating-point numbers?

Brute Force Solution

Approach

We need to find a running total for a list of numbers. The simplest way is to calculate each running total individually by summing all the preceding numbers in the list each time.

Here's how the algorithm would work step-by-step:

For the first number in the list, the running total is just that number itself.
For the second number, we add the first number to the second number to get its running total.
For the third number, we add the first number, the second number, and the third number together.
We continue this process for each number in the list, always adding up all the numbers from the beginning of the list up to the current number.
The running total for each number becomes a new list of running totals.

Code Implementation

def running_sum_brute_force(numbers):
    running_totals = []

    # Iterate through the input list to calculate running sums
    for current_index in range(len(numbers)):

        current_running_total = 0

        # Calculate the sum from the beginning to current index
        for previous_index in range(current_index + 1):
            current_running_total += numbers[previous_index]

        # Append current running total to the result
        running_totals.append(current_running_total)

    return running_totals

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the sequence.
The initial running sum is simply that first number itself.
Move to the second number.
Add the current number to the previous running sum to get the new running sum.
Store this new running sum.
Repeat the previous two steps for each remaining number in the sequence.
Each new running sum is calculated by adding the current number to the *previous* running sum, avoiding redundant calculations.

Code Implementation

def runningSum(numbers):
    running_sums = [0] * len(numbers)

    # The first element is the initial running sum.
    running_sums[0] = numbers[0]

    for index in range(1, len(numbers)):
        # Accumulate the sum using the previous running sum
        running_sums[index] = running_sums[index - 1] + numbers[index]

    return running_sums

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array immediately to avoid processing invalid input.
Array with a single element	Return the input array itself, as the running sum of a single element is the element itself.
Array with large numbers that may cause integer overflow	Use a data type with a larger range (e.g., long) to store the running sum to prevent potential overflow.
Array with a large number of elements (scalability)	The iterative approach inherently has O(n) time complexity and O(1) space complexity (excluding the input), scaling efficiently.
Array with all elements being zero	The running sum will also be an array of zeros, which is a valid result.
Array containing negative numbers	The solution should correctly handle negative numbers by subtracting them from the running sum.
Array containing a mix of positive, negative, and zero values	The algorithm will correctly calculate cumulative sum regardless of sign of the individual numbers.
Extreme boundary values for array elements (Integer.MAX_VALUE/MIN_VALUE)	Be cautious of potential integer overflow when adding to the running sum and use a larger datatype if needed.