Maximum Sum Obtained of Any Permutation — Problem & Solution
Maximum Sum Obtained of Any Permutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Sum Obtained of Any Permutation is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Prefix Sum
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and a list of requests, where requests[i] = [start, end] asks for the sum nums[start] + nums[start + 1] + … + nums[end] (both ends inclusive, 0-indexed).
You may first rearrange nums into any permutation you like. Return the largest possible total of all request sums. Since it can be very large, return it modulo 10^9 + 7.
Example 1
Input: nums = [3,1,4,2,5], requests = [[0,2],[1,3]]
Output: 23
Explanation: Indices 1 and 2 are requested twice, indices 0 and 3 once, index 4 never. Placing 5 and 4 at indices 1–2 and 3 and 2 at indices 0 and 3 gives 2·(5 + 4) + 3 + 2 = 23.
Example 2
Input: nums = [7,1,6,2], requests = [[0,3]]
Output: 16
Explanation: Every index is covered once, so the order does not matter.
Example 3
Input: nums = [10,0,10,0], requests = [[1,2],[2,3],[2,2]]
Output: 40
Explanation: Index 2 is covered three times and index 1 or 3 once, so the two 10s go to index 2 and one of those.
Constraints
n == nums.length1 <= n <= 10^50 <= nums[i] <= 10^51 <= requests.length <= 10^5requests[i].length == 20 <= start <= end < n
Hints for Maximum Sum Obtained of Any Permutation
Hint 1
The total is the sum over positions of (value placed there) × (number of requests covering that position).
Hint 2
Compute how many requests cover each index. Doing it request by request is too slow — mark each range's start and one-past-end in a difference array and take prefix sums.
Hint 3
To maximise a sum of products, pair the largest value with the largest coverage count, the second largest with the second largest, and so on: sort both lists and multiply element-wise.
How to solve Maximum Sum Obtained of Any Permutation
Each index i contributes value × freq[i], where freq[i] is how many requests cover it. Once the frequencies are known, the best permutation simply matches large values with large frequencies.
Approach
- Build a difference array: for each request
[s, e], add 1 atsand subtract 1 ate + 1. - Take prefix sums to get
freq[i]for every index. - Sort
freqand sortnums. - Sum
freq[i] * nums[i]over alli, reducing modulo10^9 + 7.
Why it works
By the rearrangement inequality, for two sequences the sum of products is largest when both are sorted in the same order: if a larger value sat on a smaller frequency while a smaller value sat on a larger one, swapping them changes the total by (a - b)(f - g) >= 0. Repeating such swaps reaches the sorted pairing without ever decreasing the total.
Complexity
- Time —
O(n log n + m) - Space —
O(n)
Pitfalls
- Counting coverage by looping over each range is O(n · m) — up to 10^10 steps.
- A single product reaches 10^10 — multiply in 64-bit before reducing.
- Take the modulus only at the end of each addition; the maximum must be found on the true values, which the sorted pairing guarantees.
Reference solution
Python
from typing import List
def maxSumRangeQuery(nums: List[int], requests: List[List[int]]) -> int:
MOD = 10 ** 9 + 7
n = len(nums)
freq = [0] * (n + 1)
for s, e in requests:
freq[s] += 1
freq[e + 1] -= 1
for i in range(1, n):
freq[i] += freq[i - 1]
f = sorted(freq[:n])
v = sorted(nums)
return sum(a * b for a, b in zip(f, v)) % MODJava
public static int maxSumRangeQuery(int[] nums, int[][] requests) {
final long MOD = 1000000007L;
int n = nums.length;
int[] freq = new int[n + 1];
for (int[] r : requests) {
freq[r[0]]++;
freq[r[1] + 1]--;
}
for (int i = 1; i < n; i++) freq[i] += freq[i - 1];
int[] f = Arrays.copyOf(freq, n);
int[] v = nums.clone();
Arrays.sort(f);
Arrays.sort(v);
long ans = 0;
for (int i = 0; i < n; i++) ans = (ans + (long) f[i] * v[i]) % MOD;
return (int) ans;
}C++
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
const long long MOD = 1000000007LL;
int n = nums.size();
vector<int> freq(n + 1, 0);
for (auto& r : requests) {
freq[r[0]]++;
freq[r[1] + 1]--;
}
for (int i = 1; i < n; i++) freq[i] += freq[i - 1];
vector<int> f(freq.begin(), freq.begin() + n);
vector<int> v(nums.begin(), nums.end());
sort(f.begin(), f.end());
sort(v.begin(), v.end());
long long ans = 0;
for (int i = 0; i < n; i++) ans = (ans + (long long) f[i] * v[i]) % MOD;
return (int) ans;
}JavaScript
var maxSumRangeQuery = function(nums, requests) {
var MOD = 1000000007;
var n = nums.length;
var freq = new Array(n + 1).fill(0);
for (var i = 0; i < requests.length; i++) {
freq[requests[i][0]]++;
freq[requests[i][1] + 1]--;
}
for (var i = 1; i < n; i++) freq[i] += freq[i - 1];
var f = freq.slice(0, n).sort(function(a, b) { return a - b; });
var v = nums.slice().sort(function(a, b) { return a - b; });
var ans = 0;
for (var i = 0; i < n; i++) ans = (ans + f[i] * v[i]) % MOD;
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms