Domain 2MediumMEDIUM

Maximum Sum Obtained of Any Permutation

LeetCode problem 1589: Maximum Sum Obtained of Any Permutation (medium).

Domain: medium•Updated: 2026-09-18
#Greedy

Problem Breakdown

We are given an array of numbers nums and a set of range requests. Each request specifies a subarray [start, end]. We need to permute (rearrange) nums such that when we sum up the values for every requested range across all permutations, the total is maximized.

Key Inputs:

  • nums: List of integers representing available numbers.
  • requests: List of [start, end] pairs defining ranges to be summed.

Output:

  • The maximum possible sum modulo 109+710^9 + 7.

Implicit Constraints & Edge Cases:

  • Overlap Handling: Ranges overlap significantly; a single index in the array might contribute to multiple request sums. We need to count how many times each position is “requested”.
  • Overflow: The problem explicitly asks for modulo arithmetic because the sum can exceed standard integer limits (though Python handles large integers automatically, we must return the result mod 109+710^9 + 7).
  • Permutation Logic: We are not limited to a specific permutation; we choose the optimal one. This implies sorting logic based on frequency of usage rather than fixed positions.

Intuition

A brute-force approach would try every possible permutation of nums (N!N! complexity), calculate the sum for each, and find the maximum. Given N≤105N \le 10^5, this is computationally impossible (Time Limit Exceeded).

Key Insight: The total score is essentially a dot product between two vectors:

  1. The Values (nums): We can rearrange these freely. To maximize the sum, we want larger numbers to be multiplied by larger weights.
  2. The Frequencies (Weights): Each index ii in nums contributes its value to a request every time that index falls within [start, end]. Let’s call this frequency count for index ii, denoted as count[i].

According to the rearrangement inequality, ∑xiyπ(i)\sum x_i y_{\pi(i)} is maximized when both sequences are sorted in the same order. Therefore:

  1. We calculate how many times each position 0…N−10 \dots N-1 appears across all requests (the weights).
  2. We sort nums descending to get our largest values first.
  3. We sort the frequency counts of positions descending so that the most requested indices receive the largest numbers from nums.

Optimization: Calculating frequencies naively for each request takes O(K⋅N)O(K \cdot N) where KK is number of requests. To optimize this to O(N+K)O(N + K), we use a Difference Array (Sweep Line) technique. We increment at start and decrement after end, then compute prefix sums to get the actual frequency for each index in linear time.

Approach

  1. Initialize a difference array of size N+2N+2 with zeros. This handles boundary conditions cleanly.
  2. Iterate through each request [l, r]:
    • Increment diff[l] by 1 (start of range).
    • Decrement diff[r + 1] by 1 (end of range exclusive for prefix sum logic).
  3. Compute the actual frequency count array using a running prefix sum over the difference array. Store these counts in a list, ignoring indices that don’t exist or are out of bounds if any (though constraints ensure valid ranges).
  4. Sort nums in descending order.
  5. Sort the calculated frequencies (counts) in ascending order to match with sorted numbers? Actually, we want largest number ×\times largest count. So sort both lists such that they align: Largest Number matches Largest Count. We can just reverse one or ensure consistent sorting direction (e.g., both descending). Let’s sort nums desc and counts asc then iterate backwards to match large with large? Or simply sort counts desc as well.
    • Sort nums: Descending (v1≥v2…v_1 \ge v_2 \dots)
    • Sort counts: Ascending or Descending? If we want vmax×cmaxv_{max} \times c_{max}, both should be sorted same way (e.g., descending). Let’s sort counts ascending and iterate from end to start for pairing. Or just sort counts descending too. Sorting counts descending is cleaner: pair index 0 of nums with index 0 of counts.
  6. Compute the dot product ∑nums[i]×counts[i]\sum nums[i] \times counts[i] modulo 109+710^9 + 7.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N+K)O(N \log N + K).
    • Difference array updates: O(K)O(K) where KK is number of requests.
    • Prefix sum calculation: O(N)O(N).
    • Sorting nums: O(Nlog⁡N)O(N \log N).
    • Sorting counts (derived from prefix sums): O(Nlog⁡N)O(N \log N).
    • Dot product loop: O(N)O(N).
  • Space Complexity: O(N)O(N) for the difference array and frequency count list.

Solution

class Solution:
    def maximumSum(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # Difference array to track request frequencies efficiently
        diff = [0] * (n + 2) 
        
        for start, end in requests:
            diff[start] += 1
            diff[end + 1] -= 1
            
        counts = []
        current_freq = 0
        
        # Compute actual frequency count using prefix sum logic on difference array
        for i in range(n):
            current_freq += diff[i]
            counts.append(current_freq)
            
        # Sort nums descending to match largest numbers with highest frequencies
        nums.sort(reverse=True)
        
        # We need the counts sorted corresponding to nums. 
        # Since we want max(nums[0]) * max(counts), sort counts ascending and iterate backwards?
        # Or just sort both same way (descending). Let's sort counts descending too for direct pairing.
        counts.sort(reverse=True)
        
        total_sum = 0
        
        for i in range(n):
            val = nums[i]
            freq = counts[i]
            
            if val > 0: # Optimization to skip zeros, though not strictly necessary given constraints
                term = (val * freq) % MOD
            
            total_sum = (total_sum + term) % MOD
            
        return int(total_sum)

Edge Cases Handled

  • Zero Frequencies: Indices covered by no requests will have a count of 0. The algorithm naturally handles this as nums[i] multiplied by 0 contributes nothing to the sum, which is correct (we place smallest numbers there).
  • Single Element Array: If N=1N=1, loops run once, logic holds without modification.
  • Large Inputs (N≤105N \le 10^5): The difference array and sorting approach scale linearly-logarithmically, fitting within time limits for FAANG constraints (typically ~2 seconds).
  • Modulo Arithmetic: Python handles large integers automatically during intermediate multiplication steps; the modulo is applied at each addition step to ensure compliance with return type requirements and prevent excessive memory usage if numbers grew astronomically in other languages.