Leetcode: Range Sum of Sorted Subarray

This question was asked at Google. 

It goes as follows: 

You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array then sort them in non-decreasing order with (n)(n + 1)/2 numbers. We want to see the range of all the subarray sums. The constraint is that all of the numbers of positive numbers less than 100 with an array size of less than 1,000.

The questions are "Compute all sums and save it an array" and then go from Left to right index. 

So, let's go over it. Say 1_000_000_007 is a modulo. We create a array of size (n (n + 1) / 2) and then computing all the sums. 

For min heap, instead of generating all the sums at once, we can generate sums one by one from the smallest to the largest. 

For initialization, we will put every single element into then heap. Each time, we pop smallest subarray and extend it into one more element and put it back into the heap, and store the prefix sum and next index instead of the entire array in this way. This only works for non-negative elements, though, so adding a number and subtracting it back again will do the job. 

struct Entry {

    int sum;

    int i;

    bool operator<const(Entry &e) const {

        return sum > e.sum; //this is how we're going to organize the Priority Queue, with the least elements popped first. 

    }

};

class Solution {

public:

    int rangeSum(Vector<int>& nums, int n, int left, int right) {

        contexpr int kMod = 1e9 + 7;

        priority_queue<Entry> q; //sort by e.sum in descending order. 

        for(int i = 0; i < n; ++i) 

            q.push({nums[i], i}); //base case, push arbitrary numbers inside of the queue.

        long ans = 0;

        for(int j = 1, j <= right; ++j) { //for all the elements inside of the "vector" array

            const auto e = std::move(q.top()); //top of the queue

            q.pop(); //pop the top of the queue. 

            if(j >= left) ans += e.sum; //add the sum to the answer

            if(e.i + 1 < n) {

                q.push({e.sum + nums[e.i + 1] , e.i + 1}) //extend the sum by one more element

            }

        }

        return ans % kMod;

    }

};