Leetcode 1589. Maximum Sum Obtained of Any Permutation
Problem Statement
You are given two arrays: nums
(an array of integers), and requests
(an array of index ranges). The goal is to find a permutation of the nums
array that will translate the sum of the requests
to the maximum value possible.
A request
is composed of two indices: start
and end
(0-indexed). The sum for a particular request
is calculated by adding all the integers from the start
index to the end
index in the nums
array.
After calculating the total sum of all the sums from each request
, your task is to check for a possible permutation of the nums
array that can maximize this total sum.
Due to the potentially large size of the maximum total sum, you are required to return the total sum modulo 1,000,000,007.
Explaining Through an Example
For instance, let's look at a case where nums = [1,2,3,4,5,6]
and requests = [[0,1]]
.
In a permutation of nums
array: [6,5,4,3,2,1]
, the requests
sums as [6 + 5] = [11]
.
Total Sum = 11
Hence, for the given request
, the maximum total sum with a permutation of nums
is 11.
Solution Approach
A greedy approach is used in solving the problem. The sum in requests that is frequently asked is paired with the largest number.
To obtain the requests count:
- Create an array
count
that is filled with zeroes. Each index in thecount
array represents an index in thenums
array, and the value stored at a particular index represents the number of requests received. - For each
request
inrequests
, increment thestart
index and decrement theend + 1
index in thecount
array. This is to track the number of requests received in a certain range of indices. - Add up in
count
array from left to right to make every position to be the number that we sum on this position.
The final step is to calculate the maximum total sum:
- Sort both
nums
andcount
arrays in ascending order. Pairing small numbers with small counts and large numbers with large counts will bring the maximum total sum. - Finally, calculate the sum of the product of
nums[i]
andcount[i]
for every indexi
in thenums
array modulo 1,000,000,007.
Python Solution
1 2python 3from typing import List 4 5class Solution: 6 def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int: 7 mod = 10**9 + 7 8 n = len(nums) 9 count = [0] * (n + 1) 10 for st, ed in requests: 11 count[st] += 1 12 count[ed + 1] -= 1 13 for i in range(1, n + 1): 14 count[i] += count[i - 1] 15 # remove unused space 16 count.pop() 17 count.sort() 18 nums.sort() 19 return sum(a * b for a, b in zip(nums, count)) % mod
Java Solution
1 2java 3import java.util.*; 4 5class Solution { 6 public int maxSumRangeQuery(int[] nums, int[][] requests) { 7 int mod = 1000000007; 8 int n = nums.length; 9 int[] count = new int[n + 1]; 10 for (int[] req : requests) { 11 count[req[0]]++; 12 if (req[1] + 1 < n) { 13 count[req[1] + 1]--; 14 } 15 } 16 for (int i = 1; i <= n; i++) { 17 count[i] += count[i - 1]; 18 } 19 // remove unused space 20 count = Arrays.copyOf(count, n); 21 Arrays.sort(nums); 22 Arrays.sort(count); 23 long res = 0; 24 for (int i = 0; i < n; i++) { 25 res = (res + 1L * nums[i] * count[i]) % mod; 26 } 27 return (int) res; 28 } 29}
JavaScript Solution
1 2javascript 3var maxSumRangeQuery = function(nums, requests) { 4 let mod = 1e9 + 7; 5 let n = nums.length; 6 let count = new Array(n + 1).fill(0); 7 for (let req of requests) { 8 count[req[0]]++; 9 if (req[1] + 1 < n) { 10 count[req[1] + 1]--; 11 } 12 } 13 for (let i = 1; i <= n; i++) { 14 count[i] += count[i - 1]; 15 } 16 // remove unused space 17 count = count.slice(0, n); 18 nums.sort((a, b) => a - b); 19 count.sort((a, b) => a - b); 20 let res = 0; 21 for (let i = 0; i < n; i++) { 22 res = (res + BigInt(nums[i]) * BigInt(count[i])) % BigInt(mod); 23 } 24 return Number(res); 25};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& req) { 6 7 int mod = 1000000007; 8 int n = nums.size(); 9 vector<int> count(n + 1,0); 10 for(auto r : req){ 11 count[r[0]]++; 12 if(r[1]+1 < n) 13 count[r[1]+1]--; 14 } 15 for(int i=1; i<=n; i++) 16 count[i] += count[i - 1]; 17 18 19 count = {count.begin(), count.begin() + n}; 20 sort(count.begin(), count.end()); 21 sort(nums.begin(), nums.end()); 22 23 long ans = 0; 24 for (int i = 0; i < n; i++){ 25 ans = (ans + 1L*nums[i]*count[i])%mod; 26 } 27 return ans; 28 } 29};
C# Solution
1 2csharp 3public class Solution { 4 public int MaxSumRangeQuery(int[] nums, int[][] requests) { 5 int mod = 1000000007; 6 int n = nums.Length; 7 int[] count = new int[n + 1]; 8 foreach (var req in requests) { 9 count[req[0]]++; 10 if (req[1] + 1 < n) { 11 count[req[1] + 1]--; 12 } 13 } 14 for (int i = 1; i <= n; i++) { 15 count[i] += count[i - 1]; 16 } 17 // remove unused space 18 Array.Resize(ref count, n); 19 Array.Sort(nums); 20 Array.Sort(count); 21 long res = 0; 22 for (int i = 0; i < n; i++) { 23 res = (res + 1L * nums[i] * count[i]) % mod; 24 } 25 return (int) res; 26 } 27}
Explanation of the Solutions
The problem is a bit tricky since even though we are given the requests
array, we do not have a definite request
order. Each request
alters the array nums
, but these alterations should not affect the sum of other requests
. All the solutions provided above have a similar thought process: count the frequency of the indices which asked in requests and assign the largest value to the highest frequency index to increase the total sum.
In Python, Java, JavaScript, C#, and C++:
- We first initialize an array
count
with all elements as0
. This array will be later used to track the times an index is requested. - Then we loop over the
requests
and for each pair of indices inrequests
, increment thestart
index and ifend + 1
index exists, decrement it. This operation is often known as prefix sum which creates an array that representing the frequency count for each index. - After creating the
count
array, we sort bothnums
andcount
arrays. Sorting helps us allocate the smallest number to the least frequented index and the largest number to the most frequented index thus maximizing the sum. - Finally, calculate the total sum by multiplying each element in
nums
andcount
and take a modulus operation to prevent potential overflow.
All the solutions share the same idea but implemented in different programming languages. They all have a time complexity of approximately O(nlogn) due to sorting operation and a space complexity of O(n).
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.