Connect with us

LeetCode 1480: Running Sum of 1D Array Solution in Python

Presenting an in-place algorithm to compute the running sum of an array with O(n) time complexity, directly modifying the input array.

Published

on

The LeetCode 1480 problem, titled “Running Sum of 1d Array,” requires the implementation of a function that computes the running sum of a 1-dimensional array. For an input array `nums`, the task is to return an array where the ith element is the sum of the first `i+1` elements of `nums`. The input `nums` is an array of integers, and the problem guarantees that the length of `nums` is at least 1, ensuring that there is always at least one element to compute the running sum for.

``````class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
for i in range(1, len(nums), 1):
# Update values in-place
nums[i] = nums[i-1] + nums[i]

return nums``````

Solution Logic

My Python solution for the LeetCode 1480 problem, “Running Sum of 1d Array,” employs an in-place algorithm to compute the running sum of the input array `nums`. The solution is defined within a Python class `Solution`, with a method `runningSum` that takes the input array `nums` and returns an array of the same length, where each element at index `i` represents the sum of the elements from index `0` to `i` of the input array.

Iteration through the Array

The loop starts from `i = 1` to the end of the array. This is because the running sum for the first element (at index `0`) is the element itself, and there’s no need to modify it. The loop increments `i` by `1` each time to ensure that each element is visited exactly once.

In-Place Update

Inside the loop, the current element at `nums[i]` is updated to be the sum of itself and the previous element, `nums[i-1]`. This allows for the computation of the running sum by continuously adding the current element’s value to the sum accumulated up to the previous element. The update is done in-place, meaning the original array `nums` is modified directly without the need for additional space for another array. This approach improves space efficiency, which matters when dealing with data structures and algorithms.

After the loop completes, the original array `nums` has been transformed such that each element now represents the running sum up to that index. The modified array is then returned as the final result.

The presented Python solution to LeetCode’s Running Sum of 1D Array problem is efficient in terms of space complexity, as it requires no extra space beyond the input array, which means O(1) auxiliary space complexity. The time complexity of my Python solution is O(n), where n is the length of the input array, since each element is visited and updated exactly once.