1480. Running Sum of 1d Array

Problem Description

Given an array nums, we need to calculate the running sum of the array where runningSum[i] = sum(nums[0]...nums[i]). The function should return this running sum array.

Approach: Prefix Sum

The most efficient approach to solve this problem is by using the concept of prefix sums. A prefix sum at index i is the sum of all elements from index 0 up to i. We can calculate the running sum iteratively. The solution avoids redundant calculations by building upon the previously calculated prefix sum.

Time Complexity Analysis

The algorithm iterates through the input array once. Therefore, the time complexity is O(n), where n is the length of the input array nums.

Space Complexity Analysis

The algorithm modifies the input array in-place. It doesn't use any extra space proportional to the input size. Thus, the space complexity is O(1) (constant space).

Code Implementation

Here are the implementations in several programming languages:

Python

from itertools import accumulate
 
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        return list(accumulate(nums))

This Python solution leverages the accumulate function from the itertools library, providing a concise and efficient way to compute the running sum.

Java

class Solution {
    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

The Java code iterates through the array, starting from the second element. Each element is updated by adding the previous element's value.

C++

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

The C++ implementation mirrors the Java solution, using iterators to traverse the vector.

Go

func runningSum(nums []int) []int {
	for i := 1; i < len(nums); i++ {
		nums[i] += nums[i-1]
	}
	return nums
}

The Go code is similar to the Java and C++ versions, performing the in-place running sum calculation.

Javascript

const runningSum = (nums) => {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
};

The Javascript solution follows the same iterative approach as the other languages.

TypeScript

function runningSum(nums: number[]): number[] {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

The TypeScript code is functionally equivalent to the Javascript implementation.

C#

public class Solution {
    public int[] RunningSum(int[] nums) {
        for (int i = 1; i < nums.Length; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

The C# code is structurally similar to the Java code, utilizing a for loop to compute the running sum.

PHP

<?php
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function runningSum($nums) {
        for ($i = 1; $i < count($nums); $i++) {
            $nums[$i] += $nums[$i - 1];
        }
        return $nums;
    }
}
?>

The PHP code also uses a for loop to compute the running sum iteratively.

All these implementations achieve the same result with optimal time and space complexity. The choice of language depends on the specific project requirements and preferences.