Cumulative Sum Editorial

Practice Problem Link: Cumulative Sum | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array, return its cumulative sum.

Naive Approach

Here, we can just iterate over the array and calculate the sum of all elements from the beginning till that index. The calculated sum for each index denotes the cumulative sum for that index.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Implementation

C++

vector<int> getCumulativeSum(vector<int> &arr) {
   vector<int> cumulativeSum;
   for(int i = 0; i < arr.size(); i++) {
       int prefixSum = 0;
       for (int j = 0; j <= i; j++) {
           prefixSum += arr[j];
       }
       cumulativeSum.push_back(prefixSum);
   }
   return cumulativeSum;
}

Java

class Solution {
   int[] getCumulativeSum (int[] arr) {
       int prefixSum[] = new int[arr.length];
       for(int i = 0; i < arr.length; i++) {
           int prefix = 0;
           for(int j = 0; j <= i; j++) {
               prefix += arr[j];
           }
           prefixSum[i] = prefix;
       }
       return prefixSum;
   }
}

Python3

class Solution:
    def getCumulativeSum(self, arr: List[int]) -> List[int]:
        n = len(arr)
        cumulativeSum = [0] * n
        for i in range(n):
            prefixSum = 0
            for j in range(i + 1):
                prefixSum += arr[j]
            cumulativeSum[i] = prefixSum
        return cumulativeSum

Optimal Approach

Try to think about what is inefficient here.

We are calculating the prefix sum for the same set of indices multiple times. Is there a way to use the result of the previous prefix sum in the sum of the next prefix sum?

Observe that the result of the (i + 1)^th prefix sum is equal to the result of the i^th prefix sum + the current element in the array.

We can avoid recalculating the whole prefix sum at each index. We can just use the value of the prefix sum from the previous iteration and add the current array element to it.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

vector<int> getCumulativeSum(vector<int> &arr) {
   vector<int> cumulativeSum(n);
   cumulativeSum[0] = arr[0];
   for (int i = 1; i < arr.size(); i++) {
       cumulativeSum[i] = cumulativeSum[i - 1] + arr[i];
   }
   return cumulativeSum;
}

Java

class Solution {
   int[] getCumulativeSum (int[] arr) {
       int prefixSum[] = new int[arr.length];
       prefixSum[0] = arr[0];
       for(int i = 1; i < arr.length; i++) {
           prefixSum[i] = prefixSum[i - 1] + arr[i];
       }
       return prefixSum;
   }
}

Python3

class Solution:
    def getCumulativeSum(self, arr: List[int]) -> List[int]:
        n = len(arr)
        cumulativeSum = [arr[0]] * n
        for i in range(1, n):
            cumulativeSum[i] = cumulativeSum[i - 1] + arr[i]
        return cumulativeSum