#1589

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Sum Obtained of Any Permutation

Maximize the total sum of requests on nums by greedily assigning larger numbers to most frequently requested indices.

Problem Statement

You are given an array of integers nums and an array of requests where each request is represented as [starti, endi]. Each request asks for the sum of nums[starti] + nums[starti+1] + ... + nums[endi]. Both starti and endi are 0-indexed.

Your task is to return the maximum total sum of all requests achievable by any permutation of nums. Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]

Output: 19

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

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

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

Solution Approach

Compute index frequencies

Initialize an array freq of size n to zero. For each request [starti, endi], increment freq[starti] by 1 and decrement freq[endi+1] by 1 if endi+1<n. Convert freq to prefix sum to count how many times each index is requested.

Greedy pairing

Sort nums in descending order and sort the frequency array in descending order. Pair the largest numbers with the highest frequency indices to maximize the contribution to the total sum.

Calculate total sum and modulo

Iterate over nums and the sorted frequency array, multiplying corresponding values and accumulating the sum. Return the final sum modulo 10^9+7 to avoid integer overflow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m + n log n) where n is the length of nums and m is the number of requests due to prefix sum computation and sorting. Space complexity is O(n) for the frequency array.

What Interviewers Usually Probe

Recognizes index frequency counting as critical for greedy maximization
Considers sorting both nums and frequency array for optimal assignment
Ensures modular arithmetic is applied for large sums

Common Pitfalls or Variants

Common pitfalls

Ignoring prefix sum optimization and using nested loops over requests
Assigning numbers without sorting by frequency leading to suboptimal sums
Forgetting to apply modulo 10^9+7 causing overflow

Follow-up variants

Minimize sum instead of maximize using similar frequency logic
Requests may overlap non-contiguously, testing frequency accumulation
Allow negative numbers in nums requiring careful pairing

FAQ

What is the key pattern in Maximum Sum Obtained of Any Permutation?

The key pattern is greedy choice guided by index frequency counting, pairing largest numbers with the most requested indices.

Why do we use prefix sums in this problem?

Prefix sums efficiently calculate how many times each index is requested across overlapping intervals, avoiding nested loops.

Can nums contain zeros or large numbers?

Yes, nums elements can be zero or up to 10^5, which is why sorting and modular arithmetic are necessary.

Is sorting both nums and frequency array required?

Yes, sorting ensures the largest numbers are assigned to the most frequently requested indices for maximum total sum.

How does GhostInterview handle large outputs?

It applies modulo 10^9+7 automatically and highlights the correct greedy pairing to prevent overflow while maximizing sum.

terminal

Solution

Solution 1: Difference Array + Sorting + Greedy

We observe that for a query operation, it returns the sum of all elements in the query interval $[l, r]$. The problem requires the maximum sum of the results of all query operations, which means we need to accumulate the results of all query operations to maximize the sum. Therefore, if an index $i$ appears more frequently in the query operations, we should assign a larger value to index $i$ to maximize the sum of the results of all query operations.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        d = [0] * n
        for l, r in requests:
            d[l] += 1
            if r + 1 < n:
                d[r + 1] -= 1
        for i in range(1, n):
            d[i] += d[i - 1]
        nums.sort()
        d.sort()
        mod = 10**9 + 7
        return sum(a * b for a, b in zip(nums, d)) % mod

Continue Practicing

#1838 frequency of the most frequent element #2171 removing minimum number of magic beans #2234 maximum total beauty of the gardens