Naive Solution

The most straightforward approach is to iterate through the input array nums. For each index i, calculate the sum of elements from nums[0] to nums[i]. Store this sum in the runningSum array at the corresponding index i.

Code

def runningSum_naive(nums):
    n = len(nums)
    running_sum = [0] * n
    for i in range(n):
        current_sum = 0
        for j in range(i + 1):
            current_sum += nums[j]
        running_sum[i] = current_sum
    return running_sum

Time Complexity

The outer loop runs n times, and the inner loop runs up to i+1 times in each iteration of the outer loop. Thus, the time complexity is O(n^2).

Space Complexity

We use an additional array running_sum of size n to store the running sums. Therefore, the space complexity is O(n).

Optimal Solution

We can optimize the above approach by realizing that the running sum at index i can be computed using the running sum at index i-1. Specifically, runningSum[i] = runningSum[i-1] + nums[i]. This avoids the inner loop in the naive approach.

Code

def runningSum_optimal(nums):
    n = len(nums)
    running_sum = [0] * n
    running_sum[0] = nums[0]
    for i in range(1, n):
        running_sum[i] = running_sum[i-1] + nums[i]
    return running_sum

Time Complexity

We iterate through the array nums once. The time complexity is O(n).

Space Complexity

We use an additional array running_sum of size n to store the running sums. Therefore, the space complexity is O(n).

In-Place Solution

It's possible to avoid using extra space. We can modify the original nums array to store the running sum.

Code

def runningSum_in_place(nums):
    for i in range(1, len(nums)):
        nums[i] += nums[i-1]
    return nums

Time Complexity

We iterate through the array nums once. The time complexity is O(n).

Space Complexity

We modify the input array in-place. Therefore, the space complexity is O(1).

Edge Cases

• Empty array: If the input array is empty, the function should return an empty array.
• Single element array: If the input array contains only one element, the function should return an array containing that element.
• Array with positive and negative numbers: The function should correctly handle arrays containing both positive and negative numbers, as well as zero.