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 < nProblem Overview: You are given an array nums and several range requests. Each request adds the sum of elements between two indices. You can permute nums in any order. The goal is to arrange the numbers so the total sum contributed by all requests is maximized.
The key observation: some indices appear in more requests than others. If an index participates in many ranges, placing a larger number there increases the total contribution. The entire problem becomes matching the largest numbers with the most frequently requested indices.
Approach 1: Frequency-Based Greedy Approach (O(n log n) time, O(n) space)
Count how many times each index appears across all requests. Instead of updating every element in every range, use a difference array: increment at l and decrement at r + 1. A single prefix pass converts this into the exact frequency for each index. Now you know how many times each position contributes to the final sum.
Sort the frequency array and sort nums. Pair the largest numbers with the highest frequencies and multiply them to compute the contribution. This greedy pairing works because assigning bigger values to indices used more often maximizes the weighted sum. Sorting dominates the runtime, giving O(n log n) time and O(n) space.
This technique combines ideas from array manipulation, greedy assignment, and sorting. The greedy step is optimal because both sequences are monotonic after sorting.
Approach 2: Prefix Sum Optimization (O(n log n + q) time, O(n) space)
Range requests are processed efficiently using a difference array and a prefix sum. Each request performs only two operations: diff[l]++ and diff[r+1]--. After processing all requests, compute the prefix sum to obtain the exact frequency each index is included in.
Once frequencies are known, the rest mirrors the greedy strategy: sort both arrays and accumulate nums[i] * freq[i]. Many implementations also apply a modulo operation (1e9 + 7) during accumulation to avoid overflow. This version scales well even when the number of requests is large because each request is handled in constant time.
Recommended for interviews: The frequency-based greedy solution with a difference array is the expected approach. A brute-force solution that sums every range shows basic understanding but runs in O(n * q) and fails large constraints. Using prefix sums to compute index frequencies and sorting to greedily assign values demonstrates strong algorithmic intuition.
The idea is to compute how many times each index in the nums array is requested. Once we have the frequency of being requested for each index, we should sort both the frequency array and the nums array. This allows us to place the largest numbers in the most requested positions, thus maximizing the sum.
This solution calculates the frequency of each position in the nums array being requested using a difference array technique. After sorting both the nums array and the frequency array, they are multiplied element-wise to obtain the maximum sum.
Time Complexity: O(n log n) due to sorting operations.
Space Complexity: O(n) for the frequency array.
This approach builds upon the frequency-based greedy solution by using prefix sums for more efficient frequency computation. While still using sorting of nums and frequency, the prefix sum optimization minimizes repetitive operations.
This solution still uses the prefix sum array method as a more efficient frequency calculator. Incremental adjustments are made, optimized through prefix accumulation.
Time Complexity: O(n log n) primarily from sorting.
Space Complexity: O(n) given the extra prefix count array.
| Approach | Complexity |
|---|---|
| Frequency-Based Greedy Approach | Time Complexity: O(n log n) due to sorting operations. |
| Prefix Sum Optimization | Time Complexity: O(n log n) primarily from sorting. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Range Summation | O(n * q) | O(1) | Useful only for understanding the problem or when constraints are very small |
| Frequency-Based Greedy with Sorting | O(n log n + q) | O(n) | General optimal solution; assign largest numbers to most frequently requested indices |
| Difference Array + Prefix Sum Optimization | O(n log n + q) | O(n) | Best when many range queries exist; processes each request in constant time |
Max Sum Obtained of Any Permutation | LeetCode 1589 | Explained and Java Code • Nate Santti • 2,271 views views
Watch 9 more video solutions →Practice Maximum Sum Obtained of Any Permutation with our built-in code editor and test cases.
Practice on FleetCode