Watch 10 video solutions for Maximum Sum Obtained of Any Permutation, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Nate Santti has 2,271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |