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

Task (problem instructions)

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.