Problem Description

You are given an array of integers nums and an array of requests. Each request requests[i] = [start_i, end_i] asks for the sum of elements from index start_i to end_i (inclusive) in the nums array. Both indices are 0-indexed.

Your task is to rearrange the elements in nums in any order (find a permutation) such that when you calculate the sum for each request and add all these sums together, you get the maximum possible total sum.

For example, if nums = [1, 2, 3] and requests = [[0, 1], [1, 2]]:

• Request [0, 1] calculates nums[0] + nums[1]
• Request [1, 2] calculates nums[1] + nums[2]
• The total sum would be (nums[0] + nums[1]) + (nums[1] + nums[2])

Notice that nums[1] appears in both requests, so it contributes twice to the total sum. To maximize the result, you'd want to place the largest available number at index 1.

The key insight is that indices that appear in more requests should be assigned larger values from nums to maximize the total sum. The solution uses a difference array to count how many times each index appears across all requests, then pairs the most frequently requested indices with the largest values in nums.

Return the maximum total sum modulo 10^9 + 7.

Intuition

The core observation is that each index in the array contributes to the total sum based on how many requests include it. If an index appears in multiple requests, its value gets added multiple times to the final result.

Think of it this way: if index i appears in 5 different requests, then nums[i] will be added 5 times to our total sum. If another index j appears in only 1 request, then nums[j] contributes only once.

This leads to a greedy strategy: we should assign the largest values from nums to the indices that appear most frequently in requests. By pairing high-frequency indices with large values, we maximize the contribution to the total sum.

To count how many times each index appears across all requests, we can use a difference array technique. For each request [l, r], all indices from l to r appear once. Instead of incrementing each index individually (which would be inefficient), we mark +1 at the start position l and -1 at position r+1. After processing all requests, a prefix sum gives us the frequency count for each index.

Once we have the frequency counts and sort both the nums array and frequency array in ascending order, we can pair them up: the smallest frequency with the smallest value, the second smallest frequency with the second smallest value, and so on. This ensures that the indices with highest frequencies get the largest values, maximizing our total sum.

The final answer is the sum of nums[i] * frequency[i] for all indices, taken modulo 10^9 + 7.

Learn more about Greedy, Prefix Sum and Sorting patterns.

Solution Approach

The implementation follows these key steps:

Step 1: Build the Difference Array

We create a difference array d of size n (same as nums) initialized with zeros. For each request [l, r]:

• Increment d[l] by 1 (marking the start of the range)
• Decrement d[r + 1] by 1 if r + 1 < n (marking the end of the range)

d = [0] * n
for l, r in requests:
    d[l] += 1
    if r + 1 < n:
        d[r + 1] -= 1

Step 2: Convert Difference Array to Frequency Counts

Apply prefix sum to transform the difference array into actual frequency counts. After this step, d[i] represents how many times index i appears across all requests.

for i in range(1, n):
    d[i] += d[i - 1]

Step 3: Sort Both Arrays

Sort both nums and the frequency array d in ascending order. This prepares them for optimal pairing.

nums.sort()
d.sort()

Step 4: Calculate Maximum Sum

Pair up the sorted arrays element by element. The smallest frequency gets paired with the smallest value, ensuring the largest frequencies get the largest values. Multiply each pair and sum them up.

return sum(a * b for a, b in zip(nums, d)) % mod

The time complexity is O(n log n + m) where n is the length of nums and m is the number of requests. The sorting operations dominate the complexity. The space complexity is O(n) for the difference array.

The modulo operation 10^9 + 7 is applied at the end to prevent integer overflow and meet the problem's requirements.

Example Walkthrough

Let's walk through a concrete example to understand the solution approach.

Given:

• nums = [3, 5, 1, 2]
• requests = [[0, 2], [1, 3], [1, 1]]

Step 1: Build the Difference Array

We start with a difference array d = [0, 0, 0, 0] (same size as nums).

Processing each request:

• Request [0, 2]: Mark start at index 0 and end after index 2

  • d[0] += 1 → d = [1, 0, 0, 0]
  • d[3] -= 1 → d = [1, 0, 0, -1]

• Request [1, 3]: Mark start at index 1 and end after index 3

  • d[1] += 1 → d = [1, 1, 0, -1]
  • Since 3 + 1 = 4 is out of bounds, we skip the decrement

• Request [1, 1]: Mark start at index 1 and end after index 1

  • d[1] += 1 → d = [1, 2, 0, -1]
  • d[2] -= 1 → d = [1, 2, -1, -1]

Step 2: Convert to Frequency Counts via Prefix Sum

Apply prefix sum to get actual frequencies:

• d[0] = 1 (stays the same)
• d[1] = d[0] + d[1] = 1 + 2 = 3
• d[2] = d[1] + d[2] = 3 + (-1) = 2
• d[3] = d[2] + d[3] = 2 + (-1) = 1

Result: d = [1, 3, 2, 1]

This means:

• Index 0 appears in 1 request
• Index 1 appears in 3 requests
• Index 2 appears in 2 requests
• Index 3 appears in 1 request

Step 3: Sort Both Arrays

• Sort nums: [1, 2, 3, 5]
• Sort d: [1, 1, 2, 3]

Step 4: Calculate Maximum Sum

Pair up sorted arrays (smallest with smallest, largest with largest):

• 1 × 1 = 1
• 2 × 1 = 2
• 3 × 2 = 6
• 5 × 3 = 15

Total sum = 1 + 2 + 6 + 15 = 24

Verification: The optimal arrangement would place values as: nums = [2, 5, 3, 1]

• Request [0, 2]: sum = 2 + 5 + 3 = 10
• Request [1, 3]: sum = 5 + 3 + 1 = 9
• Request [1, 1]: sum = 5

Total = 10 + 9 + 5 = 24 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the array nums.

The time complexity is dominated by the sorting operations:

• Building the difference array d with requests takes O(m) time, where m is the number of requests
• Computing the prefix sum of the difference array takes O(n) time
• Sorting nums takes O(n × log n) time
• Sorting the frequency array d takes O(n × log n) time
• Computing the final sum with zip takes O(n) time

Since O(n × log n) is the largest term, the overall time complexity is O(n × log n).

Space Complexity: O(n), where n is the length of the array nums.

The space complexity comes from:

• The difference array d of size n, which requires O(n) space
• The sorting operations on nums and d may use O(n) additional space depending on the implementation (Python's Timsort uses up to O(n) auxiliary space)
• The zip operation creates an iterator which uses O(1) space

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo Operation

Pitfall: The sum can become extremely large, potentially exceeding integer limits. Forgetting to apply the modulo operation can lead to incorrect results or overflow issues.

Wrong approach:

# Missing modulo operation
return sum(num * freq for num, freq in zip(nums, frequency))

Correct approach:

MOD = 10**9 + 7
return sum(num * freq for num, freq in zip(nums, frequency)) % MOD

2. Incorrect Difference Array Boundary Handling

Pitfall: When building the difference array, it's crucial to check if right + 1 is within bounds before decrementing. Blindly accessing frequency[right + 1] can cause an IndexError.

Wrong approach:

for left, right in requests:
    frequency[left] += 1
    frequency[right + 1] -= 1  # IndexError when right == n-1

Correct approach:

for left, right in requests:
    frequency[left] += 1
    if right + 1 < n:  # Boundary check
        frequency[right + 1] -= 1

3. Misunderstanding the Difference Array Technique

Pitfall: Some might try to increment every index in the range directly, which is inefficient and defeats the purpose of using a difference array.

Wrong approach (O(n*m) complexity):

frequency = [0] * n
for left, right in requests:
    for i in range(left, right + 1):
        frequency[i] += 1  # Inefficient

Correct approach (O(m) for updates):

frequency = [0] * n
for left, right in requests:
    frequency[left] += 1
    if right + 1 < n:
        frequency[right + 1] -= 1
# Then apply prefix sum once

4. Forgetting to Convert Difference Array to Actual Frequencies

Pitfall: After marking the boundaries in the difference array, you must apply prefix sum to get the actual frequency counts. Skipping this step will give incorrect frequencies.

Wrong approach:

# Build difference array
for left, right in requests:
    frequency[left] += 1
    if right + 1 < n:
        frequency[right + 1] -= 1

# Forgot to apply prefix sum!
nums.sort()
frequency.sort()  # This sorts the difference array, not frequencies

Correct approach:

# Build difference array
for left, right in requests:
    frequency[left] += 1
    if right + 1 < n:
        frequency[right + 1] -= 1

# Convert to actual frequencies
for i in range(1, n):
    frequency[i] += frequency[i - 1]

nums.sort()
frequency.sort()

5. Modifying Original Input Array

Pitfall: Sorting nums in-place modifies the original array, which might not be desired in some contexts or could affect test cases if the array is reused.

Solution if preserving original is needed:

nums_copy = nums.copy()  # Create a copy
nums_copy.sort()
# Use nums_copy for calculation