We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum Obtained of Any Permutation

Number: 1695

Difficulty: Medium

Paid? No

Companies: PayPal

Problem Description

We have an array of integers, nums, and an array of requests where each request is given by [start, end]. The request asks for the sum of nums from index start to index end (inclusive). Our goal is to maximize the total sum of the results from all requests by permuting nums optimally. Since the result can be very large, return the answer modulo 10^9 + 7.

Key Insights

  • Use a difference array to efficiently compute how many requests include each index.
  • Apply a prefix sum on the difference array to obtain the frequency (weight) for each index.
  • Sorting both nums and the frequency array helps to pair larger numbers with higher frequencies—this greedy strategy maximizes the overall sum.
  • Calculate the total as the dot product of the sorted lists, applying modulo arithmetic.

Space and Time Complexity

Time Complexity: O(n log n + r) where n is the length of nums and r is the number of requests.
Space Complexity: O(n) for the frequency array.

Solution

We start by initializing a frequency array of length n+1 with zeros. For each request [start, end], we use the difference array technique: increment frequency[start] and, if applicable, decrement frequency[end+1]. We then compute the prefix sum over the frequency array to determine the count of requests that include each index. By sorting both the frequency array (ignoring the extra element after prefix summing) and the nums array, we can pair the largest numbers with the most requested positions. The final answer is computed as the sum of the products of the corresponding elements from these sorted arrays, modulo 10^9+7.

Code Solutions

# Function to compute maximum sum obtained of any permutation
def max_sum_range_query(nums, requests):
    MOD = 10**9 + 7  # Modulus value
    n = len(nums)
    
    # Initialize frequency array with an extra element for difference array technique
    freq = [0] * (n + 1)
    
    # For each request, mark the start and one past the end positions in the difference array
    for start, end in requests:
        freq[start] += 1
        if end + 1 < n:
            freq[end + 1] -= 1
    
    # Convert the difference array to the actual frequency array using a prefix sum
    for i in range(1, n):
        freq[i] += freq[i - 1]
    
    # Only take the first n elements relevant to nums
    freq = freq[:n]
    
    # Sort both the frequency array and nums array
    nums.sort()
    freq.sort()
    
    # Calculate the dot product of the sorted arrays mod MOD
    result = 0
    for i in range(n):
        result = (result + nums[i] * freq[i]) % MOD
    
    return result

# Example usage
print(max_sum_range_query([1,2,3,4,5], [[1,3],[0,1]]))  # Expected Output: 19
← Back to All Questions