Leetcode 1589. Maximum Sum Obtained of Any Permutation

Problem statement

https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/

Solution

Use differences trick to calculate how many times we need to take each index. Then sort both nums and acc and evaluate sums.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def maxSumRangeQuery(self, nums, Q):
        n = len(nums)
        diff = [0] * (n + 1)
        for x, y in Q:
            diff[x] += 1
            diff[y + 1] -= 1
            
        acc = list(accumulate(diff))[:-1]
        return sum(x*y for x, y in zip(sorted(acc), sorted(nums))) % (10**9 + 7)