Scale Engineer

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
GreedyPrefix Sum
Algorithms
Sorting
Data structures
Array
Companies
PayPal

Prompt

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.length
  • 1 <= n <= 105
  • 0 <= nums[i] <= 105
  • 1 <= requests.length <= 105
  • requests[i].length == 2
  • 0 <= starti <= endi < 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.

import java.util.Arrays; class Solution {    public int maxSumRangeQuery(int[] nums, int[][] requests) {        int n = nums.length;        int[] freq = new int[n];                // Step 1: Calculate frequency for each index (Brute-force)        for (int[] req : requests) {            int start = req[0];            int end = req[1];            for (int i = start; i <= end; i++) {                freq[i]++;            }        }                // Step 2: Sort both nums and freq arrays        Arrays.sort(nums);        Arrays.sort(freq);                // Step 3: Calculate the maximum total sum        long totalSum = 0;        int mod = 1_000_000_007;                for (int i = 0; i < n; i++) {            totalSum = (totalSum + (long)nums[i] * freq[i]) % mod;        }                return (int)totalSum;    }}

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.

Solutions

class Solution {public  int maxSumRangeQuery(int[] nums, int[][] requests) {    int n = nums.length;    int[] d = new int[n];    for (var req : requests) {      int l = req[0], r = req[1];      d[l]++;      if (r + 1 < n) {        d[r + 1]--;      }    }    for (int i = 1; i < n; ++i) {      d[i] += d[i - 1];    }    Arrays.sort(nums);    Arrays.sort(d);    final int mod = (int)1 e9 + 7;    long ans = 0;    for (int i = 0; i < n; ++i) {      ans = (ans + 1L * nums[i] * d[i]) % mod;    }    return (int)ans;  }}

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 →

Next problem