Positive Cumulative Sum Editorial

Practice Problem Link:  Positive Cumulative Sum | Practice Problem

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

Problem Statement

The cumulative sum of an array at index i is defined as the sum of all elements of the array from index 0 to index i. The positive cumulative sum of an array is a list of only those cumulative sums which are positive. Given an array, return its positive 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. Store only those cumulative sums in a vector which have a positive value.

Analysis 

• Time Complexity : O(n²) // due to 2 nested loops
• Space Complexity : O(n)

Implementation 

C++

vector<int> getPositiveCumulativeSum(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);
   }
   vector<int> positiveCumulativeSum;
   for(auto x: cumulativeSum) {
       if(x > 0) {
           positiveCumulativeSum.push_back(x);
       }
   }
   return positiveCumulativeSum;
}

Java

class Solution {
   List<Integer> getPositiveCumulativeSum (int[] arr) {
       List<Integer> prefixSum = new ArrayList<Integer>();  
            for (int i = 0; i < arr.length; i++) {
               int prefix = 0;
               for (int j = 0; j <= i; j++) {
                   prefix += arr[j];
               }
               if(prefix > 0) {
                   prefixSum.add(prefix);
               }
            }
       return prefixSum;
   }
}

Optimal Approach

Whether the current prefix sum is positive or negative is easy to check, the main bottleneck is calculating the sums for each of the prefixes. Try to think about what we are doing inefficiently. We are calculating each prefix sum again and again. Is there a way to use the result of the previous prefix sum in the sum of the next prefix sum?

Here’s the key to solving this problem. The result of the (i + 1)th prefix is equal to the result of the ith prefix + current element in the array. So we don't need to recalculate the whole prefix sum, again and again, just use the value of the prefix sum from the previous iteration along with the current array element.

Now, only push those elements in a list, which are positive, and return it.

Analysis 

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

Implementation

C++

vector<int> getPositiveCumulativeSum(vector<int> &arr) {
   vector<int> prefix(arr.size());
   prefix[0] = arr[0];
   for (int i = 1; i < arr.size(); i++) {
       prefix[i] = prefix[i - 1] + arr[i];
   }
   vector<int> positivePrefix;
   for (int i = 0; i < arr.size(); i++) {
       if(prefix[i] > 0) {
           positivePrefix.push_back(prefix[i]);
       }
   }
   return positivePrefix;
}

Java

class Solution {
   List<Integer> getPositiveCumulativeSum (int[] arr) {
       List<Integer> positivePrefixSum = new ArrayList<Integer>();  
       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];
       }
       for (int i = 0; i < prefixSum.length; i++) {
           if(prefixSum[i] > 0) {
               positivePrefixSum.add(prefixSum[i]);
           }
       }
       return positivePrefixSum;
   }
}