Maximum Sum Obtained of Any Permutation

Medium
1355.

Maximum Sum Obtained of Any Permutation

Maximum Sum Obtained of Any Permutation is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Microsoft interviews.

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.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= requests.length <= 10^5
  • requests[i].length == 2
  • 0 <= start <= end < n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[][]} requests
 * @return {number}
 */
var maxSumRangeQuery = function(nums, requests) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= requests.length <= 10^5
  • requests[i].length == 2
  • 0 <= start <= end < n

Hints for Maximum Sum Obtained of Any Permutation

  1. Hint 1

    The total is the sum over positions of (value placed there) × (number of requests covering that position).

  2. 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.

  3. 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

  1. Build a difference array: for each request [s, e], add 1 at s and subtract 1 at e + 1.
  2. Take prefix sums to get freq[i] for every index.
  3. Sort freq and sort nums.
  4. Sum freq[i] * nums[i] over all i, reducing modulo 10^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)) % MOD

Java

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