Maximum Sum Obtained of Any Permutation - Leetcode
Problem link: Leetcode problem - maximum sum obtained..
Question:
We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.
Return the maximum total sum of all requests among all permutations of nums.
Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]] Output: 19 Explanation: One permutation of nums is [2,1,3,4,5] with the following result: requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8 requests[1] -> nums[0] + nums[1] = 2 + 1 = 3 Total sum: 8 + 3 = 11. A permutation with a higher total sum is [3,5,4,2,1] with the following result: requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11 requests[1] -> nums[0] + nums[1] = 3 + 5 = 8 Total sum: 11 + 8 = 19, which is the best that you can do.
Example 2:
Input: nums = [1,2,3,4,5,6], requests = [[0,1]] Output: 11 Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].
Example 3:
Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]] Output: 47 Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].
Constraints:
n == nums.length1 <= n <= 1050 <= nums[i] <= 1051 <= requests.length <= 105requests[i].length == 20 <= starti <= endi < n
Solution:
P.S. We will discuss 'Airplane seat trick' later.
class Solution { public: int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) { int MOD=(int)1e9 + 7; int nn=nums.size(); int nr=requests.size(); vector<int> nums_copy(nn,0); //in nums_copy array we are storing frequencies of request a particular index receives // for eg. if index 2 receives 5 request then nums_copy[2]=5; that here 5 indicate the demand //for index 2, which at later stage will be used to store higher number, so that final sum //(ans) will be maximum for(int i=0;i<nr;i++) { int from=requests[i][0]; int to=requests[i][1]; nums_copy[from] +=1; if(to!=nn-1) { nums_copy[to+1] -=1; } // AIRPLANE SEAT TRICK to count freq of req } for(int i=1;i<nn;i++) { nums_copy[i] +=nums_copy[i-1]; //also part of airplane seat trick //where final summation of +/- is done to get real freq } priority_queue<pair<int,int>> pq; // queue to contain (frequency:index) pairs in desc order wrt frequency so that we can get the index on which most request has been made, wherein we //will place highest number respectively for(int i=0;i<nn;i++) { pq.push(make_pair(nums_copy[i],i)); //making a pair to for max-heap of (freq,index) } sort(nums.begin(),nums.end()); // sorted so that we can get highest number on index with high frequencies int k=nn-1; while(!pq.empty()) { pair<int,int> p=pq.top(); // int freq=p.first; //freq will not be used from now as only purpose of frequency was to sort indexes in //descreasing order of request it received int index=p.second; nums_copy[index]=nums[k]; k--; pq.pop(); } // calculating presum for the final array with in-place technique, so that afterwards when sum //need to be found from one index to another we could do it in O(1) time for(int i=1;i<nn;i++) { nums_copy[i] +=nums_copy[i-1]%MOD; } int ans=0; //final sum value will be stored in this variable for(int i=0;i<nr;i++) { int from=requests[i][0]; int to=requests[i][1]; // using preSum calculated above to get sum in O(1) time if(from==0) { ans +=(nums_copy[to]%MOD); } else ans +=(nums_copy[to]-nums_copy[from-1])%MOD; ans %=MOD; } // as ans can be big number hence using MOD variable to get it inside int range return ans%MOD; } };
