Vultr DocsLatest Content

Running Sum of 1d Array

Updated on 25 June, 2025
Running Sum of 1d Array header image

Problem Statement

In the given task, we work with an array, nums, consisting of integer values. We are required to compute the running sum of this array, where the running sum up to any index i is defined as the sum of all the elements from the start of the array up to that index i. This operation transforms the original array into a new array where each element at index i shows the cumulative sum of the array up to that point. The objective is to compute and return this transformed array representing the running sums.

Examples

Example 1

Input:

nums = [1,2,3,4]

Output:

[1,3,6,10]

Explanation:

Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2

Input:

nums = [1,1,1,1,1]

Output:

[1,2,3,4,5]

Explanation:

Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3

Input:

nums = [3,1,2,10,1]

Output:

[3,4,6,16,17]

Constraints

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

Approach and Intuition

Let's delve into understanding the approach and the intuition behind solving this problem, leveraging the given examples and considering the constraints applied.

  1. The idea is straightforward:

    • Starting with the first element, the running sum is the same as the element itself since there are no previous elements to add.
    • For each subsequent element at index i, the running sum is the sum of the current element and the running sum of the previous index (i-1).

  2. Here is an intuitive step-by-step breakdown using Example 1:

    • Start with the first element: nums[0] = 1. Thus, runningSum[0] = 1.
    • Move to the second element: nums[1] = 2. The running sum now is 1 (previous running sum) + 2 = 3, hence runningSum[1] = 3.
    • For the third element: nums[2] = 3. Add this to the previous running sum 3 + 3 = 6, so runningSum[2] = 6.
    • For the fourth element: nums[3] = 4. Add this to 6, resulting in 6 + 4 = 10, so runningSum[3] = 10.

  3. By following this method:

    • It becomes clear how the running sum for each index is built progressively from the sum computed up to the previous index.

  4. Constraints and Performance:

    • The array length constraint (1 <= nums.length <= 1000) ensures that our approach will perform efficiently since iterating through up to 1000 elements is computationally feasible.
    • Given the range limitation on array elements (-10^6 <= nums[i] <= 10^6), there won't be any issues of integer overflow in languages that support large integer computations like Python.

By using this cumulative addition strategy, we can efficiently calculate the running sum for the array, given the constraints ensure the approach remains efficient and practical.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    vector<int> cumulativeSum(vector<int> &data) {
        for (int index = 1; index < data.size(); index++) {
            data[index] += data[index - 1];
        }
        return data;
    }
};

The given problem requires calculating the running sum of a 1D array, where each position in the returned array should equal the sum of all previous elements in the input array up to that position. This function is implemented using C++.

  • Begin by initializing a class named Solution.
  • Define a public function within the class called cumulativeSum, which takes a reference to a vector of integers data.
  • Use a for loop to iterate through the vector starting from the second element.
  • In each iteration, update the current element by adding to it the value of the previous element. This accumulates the values.
  • After the loop completes, the function returns the modified vector data, which now contains the running sums.

This method is efficient for calculating the running sum as it directly modifies the input vector without using additional space, leading to an O(1) space complexity. The time complexity is O(n), where n is the number of elements in the input vector, since it processes each element a single time.

java 
class Solution {
public int[] cumulativeSum(int[] values) {
        for (int idx = 1; idx < values.length; idx++) {
            values[idx] += values[idx - 1];
        }
        return values;
    }
}

The provided Java method named cumulativeSum takes an array of integers as input and returns another array where each element at index idx represents the sum of all elements up to index idx from the original array. The solution manipulates the input array in-place to store the running sums, thereby optimizing space usage.

  • The method starts iterating from the second element of the array (idx = 1).
  • During each iteration, the current element (values[idx]) is updated by adding to it the previous element's value (values[idx - 1]).
  • This process alters the original array such that each element accumulates the sum of itself and all previous elements.
  • Finally, the updated array is returned.

This approach effectively calculates the running sum by iterating over the array once, making the time complexity O(n), where n is the number of elements in the array. This method uses no additional space for calculation, except for the input array itself, leading to a space complexity of O(1).

Comments

No comments yet.