algoadvance

You’re given an array of numbers called nums. You need to return an array that consists of the running sums of the nums array.

The running sum at position i is the sum of all elements from the start of the array up to the i-th element.

For example, if the array nums is [1, 2, 3, 4], the running sum array would be [1, 3, 6, 10].

Clarifying Questions

1. Input Constraints:
   • What is the range of the length of nums?
   • What are the possible values of the elements in nums? Are they all integers?
2. Edge Cases:
   • What if nums is an empty array? Should we return an empty array as well?
   • Is nums always guaranteed to have at least one element?
3. Output:
   • Is it acceptable to modify the input array nums in-place, or should a new array be returned?

Strategy

1. Initialize a Result Array:
   • Start with an empty result array.
2. Iterate through the Input Array:
   • Maintain a running sum that starts at 0.
   • For each element in the array, add it to the running sum and append the running sum to the result array.
3. Return the Result Array:
   • After the loop completes, the result array should contain the running sums.

Code

def runningSum(nums):
    result = []
    running_sum = 0
    
    for num in nums:
        running_sum += num
        result.append(running_sum)
        
    return result

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of the input array nums. This is because we are iterating through the array once.
• Space Complexity: (O(n)), since we are creating a new result array of the same length as nums.

Example

nums = [1, 2, 3, 4]
print(runningSum(nums))  # Output: [1, 3, 6, 10]

nums = [1, 1, 1, 1, 1]
print(runningSum(nums))  # Output: [1, 2, 3, 4, 5]

nums = [3, 1, 2, 10, 1]
print(runningSum(nums))  # Output: [3, 4, 6, 16, 17]

In these examples, the function runningSum correctly computes the running sums and returns the expected arrays.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?