Problem Description

You are given an integer array nums of length n, and an array requests where each request is a pair of indices [start, end] (inclusive). For each request, you can pick any subarray of nums from index start to end and sum up its elements. You are allowed to permute nums in any order you like before processing the requests, but you must use the same permutation for all requests. Your goal is to maximize the total sum obtained from all requests.

Constraints:

• Each element in nums must be used exactly once in the permutation.
• You cannot reuse or duplicate elements.
• There is at least one valid solution.
• The answer can be large, so return it modulo 10^9 + 7.

Thought Process

The brute-force approach would be to try every possible permutation of nums, sum the values for all requests, and pick the maximum. However, with up to 10⁵ elements, this is computationally impossible.

Instead, let's consider: for each index in nums, how many times is it included in the sum across all requests? If we could assign the largest numbers to the indices that are included most often, we'd maximize the sum. This shifts our thinking from permutations to frequency matching.

Solution Approach

To solve the problem efficiently, we use the following steps:

1. Count Frequencies: For each index in nums, count how many requests include it.
   • We use a difference array to efficiently update frequencies for all ranges in requests in O(n) time.
2. Sort for Maximum Pairing:
   • Sort the frequencies in descending order (most requested indices first).
   • Sort nums in descending order (largest elements first).
   • Pair the largest numbers with the most-requested indices.
3. Calculate the Sum:
   • Multiply each sorted number by its corresponding frequency.
   • Add up all products and take the result modulo 10⁹+7.

We use a difference array for efficient range updates because it allows us to increment all frequencies in a range in O(1) time per request.

Example Walkthrough

Let's say nums = [1,2,3,4,5] and requests = [[1,3],[0,1]].

1. Step 1: Count Frequencies
   • Initialize freq = [0, 0, 0, 0, 0]
   • For request [1,3]: freq[1] +=1, freq[4] -=1
   • For request [0,1]: freq[0] +=1, freq[2] -=1
   • freq after updates: [1,1, -1,0,-1]
   • Take prefix sum: [1,2,1,1,0]
   • So, index 0 is requested 1x, index 1 is 2x, index 2 is 1x, index 3 is 1x, index 4 is 0x.
2. Step 2: Sort and Pair
   • freq: [2,1,1,1,0] (sorted descending, drop index info)
   • nums: [5,4,3,2,1] (sorted descending)
   • Pair: 5*2 + 4*1 + 3*1 + 2*1 + 1*0 = 10 + 4 + 3 + 2 + 0 = 19
3. Step 3: Return Result
   • Return 19

Time and Space Complexity

• Brute-force:
  • Time: O(n!) for all permutations (impractical for n > 8).
  • Space: O(n) for each permutation.
• Optimized Approach:
  • Time: O(n log n + m), where n is the length of nums and m is the number of requests.
  • Space: O(n) for the frequency and difference arrays.
  • Sorting dominates the runtime (O(n log n)).

Summary

The key insight is to match the largest numbers to the most-requested indices using frequency analysis and sorting. By leveraging a difference array for efficient range frequency computation, and sorting both the frequencies and nums, we achieve an optimal solution in O(n log n) time. This approach elegantly transforms a permutation problem into a pairing problem, unlocking both efficiency and clarity.

Code Implementation

class Solution:
    def maxSumRangeQuery(self, nums, requests):
        n = len(nums)
        freq = [0] * (n + 1)
        for start, end in requests:
            freq[start] += 1
            if end + 1 <= n - 1:
                freq[end + 1] -= 1
        # Prefix sum to get the real frequencies
        for i in range(1, n):
            freq[i] += freq[i - 1]
        freq = freq[:n]
        nums.sort(reverse=True)
        freq.sort(reverse=True)
        mod = 10 ** 9 + 7
        return sum(a * b for a, b in zip(nums, freq)) % mod
      

class Solution {
public:
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
        int n = nums.size();
        vector<int> freq(n + 1, 0);
        for (auto& req : requests) {
            freq[req[0]] += 1;
            if (req[1] + 1 < n) freq[req[1] + 1] -= 1;
        }
        for (int i = 1; i < n; ++i) {
            freq[i] += freq[i - 1];
        }
        freq.pop_back();
        sort(nums.rbegin(), nums.rend());
        sort(freq.rbegin(), freq.rend());
        long long res = 0, mod = 1e9 + 7;
        for (int i = 0; i < n; ++i) {
            res = (res + (long long)nums[i] * freq[i]) % mod;
        }
        return (int)res;
    }
};
      

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int[] freq = new int[n + 1];
        for (int[] req : requests) {
            freq[req[0]] += 1;
            if (req[1] + 1 < n) freq[req[1] + 1] -= 1;
        }
        for (int i = 1; i < n; ++i) {
            freq[i] += freq[i - 1];
        }
        int[] realFreq = new int[n];
        System.arraycopy(freq, 0, realFreq, 0, n);
        Arrays.sort(nums);
        Arrays.sort(realFreq);
        long res = 0, mod = 1_000_000_007;
        for (int i = 0; i < n; ++i) {
            res = (res + (long) nums[n - 1 - i] * realFreq[n - 1 - i]) % mod;
        }
        return (int) res;
    }
}
      

var maxSumRangeQuery = function(nums, requests) {
    const n = nums.length;
    const freq = new Array(n + 1).fill(0);
    for (let [start, end] of requests) {
        freq[start] += 1;
        if (end + 1 < n) freq[end + 1] -= 1;
    }
    for (let i = 1; i < n; ++i) {
        freq[i] += freq[i - 1];
    }
    freq.length = n;
    nums.sort((a, b) => b - a);
    freq.sort((a, b) => b - a);
    let res = 0, mod = 1e9 + 7;
    for (let i = 0; i < n; ++i) {
        res = (res + nums[i] * freq[i]) % mod;
    }
    return res;
};