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 the count array represents an index in the nums array, and the value stored at a particular index represents the number of requests received.
• For each request in requests, increment the start index and decrement the end + 1 index in the count 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 and count 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] and count[i] for every index i in the nums 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 as 0. 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 in requests, increment the start index and if end + 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 both nums and count 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 and count 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).