Maximum Sum Obtained of Any Permutation

Med

#1461Time: O(m * n + n log n), where `n` is the length of `nums` and `m` is the number of requests. The `O(m * n)` part comes from iterating through all requests and updating frequencies. `O(n log n)` is for sorting. Given the constraints, this is too slow.Space: O(n) to store the frequency array.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

We have an array of integers, nums, and an array of requests where requests[i] = [start_i, end_i]. The i^th request asks for the sum of nums[start_i] + nums[start_i + 1] + ... + nums[end_i - 1] + nums[end_i]. Both start_i and end_i 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 10⁹ + 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.length
1 <= n <= 10⁵
0 <= nums[i] <= 10⁵
1 <= requests.length <= 10⁵
requests[i].length == 2
0 <= start_i <= end_i < n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of counting how many times each index is requested. It iterates through each request and, for each request, iterates through all the indices it covers, incrementing a counter for each index. This count array represents the "importance" of each index. To maximize the total sum, we pair the largest numbers from nums with the indices that are requested most frequently.

Algorithm

Create an integer array freq of size n (length of nums), initialized to all zeros.
Iterate through each request in the requests array.
For each request = [start, end], iterate from i = start to end and increment freq[i].
Sort the nums array in ascending order.
Sort the freq array in ascending order.
Initialize a variable maxSum to 0.
Iterate from i = 0 to n-1. In each iteration, add the product of nums[i] and freq[i] to maxSum. Apply modulo 10^9 + 7 at each addition to prevent overflow.
Return maxSum.

Walkthrough

The core idea is that to maximize the sum Σ(count[i] * nums_permuted[i]), we must assign the largest values from nums to the indices i with the highest count[i].

First, we need to determine the frequency count[i] for each index i, which is the number of requests that include this index. We can create a frequency array, freq, of the same size as nums. We iterate through every request [start, end]. For each request, we loop from start to end and increment freq[j] for each index j in this range.

After calculating all frequencies, we sort both the nums array and the freq array in non-decreasing order. The maximum total sum is then the sum of the products of the corresponding elements from the sorted arrays: sum(sorted_nums[i] * sorted_freq[i]). Since the result can be large, we perform the summation modulo 10^9 + 7.

1import java.util.Arrays;2 3class Solution {4    public int maxSumRangeQuery(int[] nums, int[][] requests) {5        int n = nums.length;6        int[] freq = new int[n];7        8        // Step 1: Calculate frequency for each index (Brute-force)9        for (int[] req : requests) {10            int start = req[0];11            int end = req[1];12            for (int i = start; i <= end; i++) {13                freq[i]++;14            }15        }16        17        // Step 2: Sort both nums and freq arrays18        Arrays.sort(nums);19        Arrays.sort(freq);20        21        // Step 3: Calculate the maximum total sum22        long totalSum = 0;23        int mod = 1_000_000_007;24        25        for (int i = 0; i < n; i++) {26            totalSum = (totalSum + (long)nums[i] * freq[i]) % mod;27        }28        29        return (int)totalSum;30    }31}

Complexity

Time

O(m * n + n log n), where `n` is the length of `nums` and `m` is the number of requests. The `O(m * n)` part comes from iterating through all requests and updating frequencies. `O(n log n)` is for sorting. Given the constraints, this is too slow.

Space

O(n) to store the frequency array.

Trade-offs

Pros

Simple to understand and implement.
Correctly identifies the core greedy strategy of pairing large numbers with high-frequency indices.

Cons

The frequency calculation step is very slow.
Time complexity is dominated by the nested loops, making it infeasible for large inputs. It will result in a "Time Limit Exceeded" (TLE) error on competitive programming platforms.

This approach improves upon the brute-force method by calculating the index frequencies more efficiently. Instead of iterating through each range for every request, it uses a technique similar to a difference array or a line sweep algorithm. This reduces the time to calculate all frequencies from O(m * n) to O(n + m). The rest of the logic, which involves sorting and pairing, remains the same.

Algorithm

Create an integer array freq of size n, initialized to all zeros. This array will first be used as a difference array.
Iterate through each request = [start, end] in requests.
For each request, increment freq[start] by 1.
If end + 1 < n, decrement freq[end + 1] by 1.
After processing all requests, convert the difference array into the actual frequency array by computing its prefix sum. Iterate from i = 1 to n-1 and update freq[i] = freq[i] + freq[i-1].
Sort the nums array in ascending order.
Sort the freq array in ascending order.
Initialize a variable maxSum to 0.
Iterate from i = 0 to n-1, adding the product of nums[i] and freq[i] to maxSum. Apply modulo 10^9 + 7 at each step.
Return maxSum.

Walkthrough

The bottleneck in the previous approach is calculating the frequency array. We can optimize this part significantly. The problem of adding 1 to all elements in multiple ranges [start, end] can be solved efficiently. We can create an array, let's call it freq, of size n.

For each request [start, end], we increment freq[start] by 1 and, if end + 1 is within bounds, we decrement freq[end + 1] by 1. The freq[i] now represents the net change in frequency count at index i.

After processing all requests, we can compute the actual frequency for each index by taking the prefix sum of this array. That is, freq[i] = freq[i-1] + freq[i] (after the initial marking phase). This process computes the frequency array in O(n + m) time.

Once the freq array is computed, the rest of the algorithm is identical to the first approach: sort nums and freq, then compute the dot product.

1import java.util.Arrays;2 3class Solution {4    public int maxSumRangeQuery(int[] nums, int[][] requests) {5        int n = nums.length;6        int[] freq = new int[n];7        8        // Step 1: Efficiently calculate frequency using difference array concept9        for (int[] req : requests) {10            freq[req[0]]++;11            if (req[1] + 1 < n) {12                freq[req[1] + 1]--;13            }14        }15        16        // Step 2: Compute prefix sums to get the actual frequencies17        for (int i = 1; i < n; i++) {18            freq[i] += freq[i - 1];19        }20        21        // Step 3: Sort both nums and freq arrays22        Arrays.sort(nums);23        Arrays.sort(freq);24        25        // Step 4: Calculate the maximum total sum26        long totalSum = 0;27        int mod = 1_000_000_007;28        29        for (int i = 0; i < n; i++) {30            totalSum = (totalSum + (long)nums[i] * freq[i]) % mod;31        }32        33        return (int)totalSum;34    }35}

Complexity

Time

O(m + n + n log n). `O(m + n)` for frequency calculation (processing requests and computing prefix sums). `O(n log n)` for sorting both arrays. The overall complexity is dominated by sorting for large `n`.

Space

O(n) to store the frequency array.

Trade-offs

Pros

Highly efficient frequency calculation.
The overall time complexity is dominated by sorting, which is much better than the brute-force approach.
This solution is efficient enough to pass within the given constraints.

Cons

The difference array technique might be slightly less intuitive for beginners compared to the direct simulation.

Solutions

Solution

1class Solution {2public3  int maxSumRangeQuery(int[] nums, int[][] requests) {4    int n = nums.length;5    int[] d = new int[n];6    for (var req : requests) {7      int l = req[0], r = req[1];8      d[l]++;9      if (r + 1 < n) {10        d[r + 1]--;11      }12    }13    for (int i = 1; i < n; ++i) {14      d[i] += d[i - 1];15    }16    Arrays.sort(nums);17    Arrays.sort(d);18    final int mod = (int)1 e9 + 7;19    long ans = 0;20    for (int i = 0; i < n; ++i) {21      ans = (ans + 1L * nums[i] * d[i]) % mod;22    }23    return (int)ans;24  }25}

1class Solution {2public:3  int maxSumRangeQuery(vector<int> &nums, vector<vector<int>> &requests) {4    int n = nums.size();5    int d[n];6    memset(d, 0, sizeof(d));7    for (auto &req : requests) {8      int l = req[0], r = req[1];9      d[l]++;10      if (r + 1 < n) {11        d[r + 1]--;12      }13    }14    for (int i = 1; i < n; ++i) {15      d[i] += d[i - 1];16    }17    sort(nums.begin(), nums.end());18    sort(d, d + n);19    long long ans = 0;20    const int mod = 1e9 + 7;21    for (int i = 0; i < n; ++i) {22      ans = (ans + 1LL * nums[i] * d[i]) % mod;23    }24    return ans;25  }26};

1class Solution:2    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int: n = len(nums) d = [0] * n for l, r in requests: d[l] += 1 if r + 1 < n: d[r + 1] -= 1 for i in range(1, n): d[i] += d[i - 1] nums . sort() d . sort() mod = 10 ** 9 + 7 return sum(a * b for a, b in zip(nums, d)) % mod

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem