LeetCode Problem 1589

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Prefix Sum

Solution

LeetCode 1589: Maximum Sum Obtained of Any Permutation

Problem Understanding

The problem gives us an integer array nums and a collection of range requests. Each request [start, end] asks for the sum of the subarray from index start to end, inclusive.

The key twist is that we are allowed to rearrange the elements of nums in any order before answering the requests. Our goal is to find the permutation of nums that produces the maximum possible total sum across all requests.

To understand what this means, imagine every request contributes some weight to each index. If an index appears in many requests, the value placed at that index will contribute repeatedly to the final result. Therefore, some positions in the array matter more than others.

For example, if index 2 is included in five different requests, while index 4 is included only once, then placing a large number at index 2 is much more valuable than placing it at index 4.

The input consists of:

• nums, the numbers we are allowed to rearrange.
• requests, a list of inclusive ranges [start, end].

The output is the maximum total request sum achievable by permuting nums.

Since the total can become very large, we must return the answer modulo 10^9 + 7.

The constraints reveal important information about the expected solution:

• n can be as large as 100,000
• requests.length can also be 100,000

These limits immediately rule out brute-force permutation generation because the number of permutations is n!, which becomes impossibly large even for moderate values of n.

The constraints also suggest that we need something close to O(n log n) or O(n).

Several edge cases are important to consider upfront. Some indices may never appear in any request, meaning their contribution count is zero. There may be only a single request covering a small portion of the array. Requests may heavily overlap, causing certain positions to appear many times. The problem guarantees valid ranges and at least one request, so we do not need to handle malformed input.

Approaches

Brute Force Approach

A naive way to solve this problem is to generate every possible permutation of nums.

For each permutation, we would compute the sum for every request and keep track of the maximum result encountered.

Suppose nums = [1,2,3]. We would test:

• [1,2,3]
• [1,3,2]
• [2,1,3]
• [2,3,1]
• [3,1,2]
• [3,2,1]

For each arrangement, we evaluate all request ranges and compute the total sum.

This approach is correct because it explicitly checks every possible ordering, guaranteeing that the maximum is found.

However, it is computationally infeasible.

There are n! permutations, and for each permutation we may process up to 10^5 requests.

Even for n = 20, 20! is astronomically large. Since n can be 100,000, brute force is completely impossible.

Key Insight

Instead of thinking about requests individually, we should think about how many times each index is used.

Each index contributes to the final answer as many times as it appears in requests.

Suppose index frequencies are:

Index	Usage Count
0	1
1	3
2	5
3	2

If we assign values optimally, we should place:

• the largest number at frequency 5
• the second largest at frequency 3
• and so on

This works because of a greedy pairing principle:

To maximize a weighted sum, pair the largest values with the largest multipliers.

The remaining challenge becomes efficiently computing how many times each index appears in all requests.

A naive counting approach would iterate through every request range and increment each position, but that could become O(n × requests).

Instead, we use a difference array + prefix sum technique:

For request [start, end]:

• increment frequency[start]
• decrement frequency[end + 1]

After processing all requests, taking a prefix sum reconstructs the actual frequency count for every index.

This reduces frequency computation to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × m × n)	O(n)	Tries every permutation and evaluates all requests
Optimal	O(n log n + m)	O(n)	Uses difference array, prefix sums, sorting, and greedy matching

Where:

• n = len(nums)
• m = len(requests)

Algorithm Walkthrough

Optimal Algorithm

1. Create a frequency array of size n + 1, initialized to zero.

We use a difference array so range updates become efficient. 2. Process every request [start, end].

Increment frequency[start] by 1 because coverage begins there.

If end + 1 is within bounds, decrement frequency[end + 1] by 1 because coverage stops after end. 3. Convert the difference array into actual frequencies using prefix sums.

Each index now stores how many requests include that position. 4. Remove the extra slot from the difference array.

We only need the first n positions. 5. Sort nums in ascending order.

We want to pair large numbers with large frequencies. 6. Sort the frequency array.

This ensures the most frequently used positions receive the largest values. 7. Multiply corresponding elements.

For each index:

contribution = nums[i] * frequency[i]

Add the contribution to the answer. 8. Return the result modulo 10^9 + 7.

Why it works

The algorithm works because the final answer can be rewritten as a weighted sum:

$$\text{total} = \sum (\text{value at index} \times \text{usage count})$$

Each index contributes independently based on how many requests include it.

By the rearrangement inequality, the maximum possible weighted sum occurs when both sequences are sorted in the same order, meaning the largest numbers are paired with the largest frequencies.

The difference array correctly computes request coverage counts in linear time, ensuring the algorithm remains efficient.

Python Solution

from typing import List

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        frequency = [0] * (n + 1)

        # Build difference array
        for start, end in requests:
            frequency[start] += 1
            if end + 1 < len(frequency):
                frequency[end + 1] -= 1

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

        frequency = frequency[:n]

        nums.sort()
        frequency.sort()

        total_sum = 0

        for value, count in zip(nums, frequency):
            total_sum = (total_sum + value * count) % MOD

        return total_sum

The implementation begins by creating a difference array called frequency. Instead of incrementing every index inside a request range, we only update the boundaries. This transforms expensive range updates into constant-time operations.

After processing all requests, we reconstruct the true frequency counts using a prefix sum. At this point, frequency[i] tells us exactly how many requests include index i.

We then sort both nums and frequency. This greedy step is the core optimization. Since frequently requested indices contribute more to the final sum, we pair them with larger values.

Finally, we compute the weighted sum while applying modulo arithmetic to avoid overflow and satisfy the problem requirements.

Go Solution

package main

import "sort"

func maxSumRangeQuery(nums []int, requests [][]int) int {
	const MOD = 1000000007
	n := len(nums)

	frequency := make([]int, n+1)

	// Build difference array
	for _, request := range requests {
		start, end := request[0], request[1]

		frequency[start]++

		if end+1 < len(frequency) {
			frequency[end+1]--
		}
	}

	// Prefix sum to get actual frequencies
	for i := 1; i < n; i++ {
		frequency[i] += frequency[i-1]
	}

	frequency = frequency[:n]

	sort.Ints(nums)
	sort.Ints(frequency)

	var totalSum int64

	for i := 0; i < n; i++ {
		totalSum += int64(nums[i]) * int64(frequency[i])
		totalSum %= MOD
	}

	return int(totalSum)
}

The Go implementation closely mirrors the Python version, but there are a few language-specific details worth noting.

Go uses int64 for totalSum to avoid overflow during multiplication because values can become quite large before modulo reduction.

Slices are used for the frequency array, and we explicitly trim the extra element using:

frequency = frequency[:n]

Sorting is performed using sort.Ints, which sorts slices in ascending order.

Worked Examples

Example 1

Input

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

Step 1: Build Difference Array

Request	Operation
[1,3]	freq[1] += 1, freq[4] -= 1
[0,1]	freq[0] += 1, freq[2] -= 1

Result:

Index	Value
0	1
1	1
2	-1
3	0
4	-1
5	0

Step 2: Prefix Sum

Index	Frequency
0	1
1	2
2	1
3	1
4	0

Step 3: Sort

Sorted nums	Sorted frequency
[1,2,3,4,5]	[0,1,1,1,2]

Step 4: Compute Result

Value	Frequency	Contribution
1	0	0
2	1	2
3	1	3
4	1	4
5	2	10

Total:

0 + 2 + 3 + 4 + 10 = 19

Answer:

19

Example 2

Input

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

Difference Array

Index	Value
0	1
1	0
2	-1

Prefix Frequencies

[1,1,0,0,0,0]

Sorting

nums       = [1,2,3,4,5,6]
frequency  = [0,0,0,0,1,1]

Contributions

Value	Frequency	Contribution
1	0	0
2	0	0
3	0	0
4	0	0
5	1	5
6	1	6

Total:

11

Example 3

Input

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

Difference Array Updates

Request	Update
[0,2]	+1 at 0, -1 at 3
[1,3]	+1 at 1, -1 at 4
[1,1]	+1 at 1, -1 at 2

Prefix Frequencies

[1,3,2,1,0,0]

Sorting

nums       = [1,2,3,4,5,10]
frequency  = [0,0,1,1,2,3]

Contributions

Value	Frequency	Contribution
1	0	0
2	0	0
3	1	3
4	1	4
5	2	10
10	3	30

Total:

47

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m)	Prefix sum is linear, sorting dominates
Space	O(n)	Frequency array stores coverage counts

Where:

• n = len(nums)
• m = len(requests)

The difference array construction takes O(m) because every request updates only two positions. The prefix sum reconstruction takes O(n).

The dominant cost comes from sorting both nums and frequency, each requiring O(n log n) time.

Since all auxiliary storage comes from the frequency array, extra space remains linear.

Test Cases

solution = Solution()

# Example 1
assert solution.maxSumRangeQuery(
    [1, 2, 3, 4, 5],
    [[1, 3], [0, 1]]
) == 19  # standard overlapping ranges

# Example 2
assert solution.maxSumRangeQuery(
    [1, 2, 3, 4, 5, 6],
    [[0, 1]]
) == 11  # single request

# Example 3
assert solution.maxSumRangeQuery(
    [1, 2, 3, 4, 5, 10],
    [[0, 2], [1, 3], [1, 1]]
) == 47  # overlapping requests

# Single element array
assert solution.maxSumRangeQuery(
    [7],
    [[0, 0]]
) == 7  # minimum n

# No overlap between requests
assert solution.maxSumRangeQuery(
    [1, 2, 3, 4],
    [[0, 0], [3, 3]]
) == 7  # largest values should go to used positions

# Full range request
assert solution.maxSumRangeQuery(
    [1, 2, 3, 4],
    [[0, 3]]
) == 10  # every index equally weighted

# Heavy overlap
assert solution.maxSumRangeQuery(
    [1, 2, 3, 4, 5],
    [[0, 4], [0, 4], [0, 4]]
) == 45  # all positions used equally

# Unused indices exist
assert solution.maxSumRangeQuery(
    [1, 2, 100, 200],
    [[0, 0]]
) == 200  # largest number assigned to used index

# Large values stress test
assert solution.maxSumRangeQuery(
    [100000] * 5,
    [[0, 4], [0, 4]]
) == 1000000  # modulo handling

Test Summary

Test	Why
Example 1	Validates overlapping requests
Example 2	Tests single request behavior
Example 3	Verifies uneven frequency distribution
Single element	Minimum constraint case
No overlap	Ensures optimal reassignment
Full range	All indices equally weighted
Heavy overlap	Repeated full coverage
Unused indices	Confirms zero-frequency handling
Large values	Verifies arithmetic robustness

Edge Cases

Indices That Never Appear in Requests

Some positions may never be included in any request. Their frequency becomes zero.

This can easily cause mistakes if frequencies are not computed correctly. A buggy implementation might accidentally assign large numbers to unused indices.

Our solution handles this naturally because frequencies are sorted. Zero-frequency positions appear at the front, meaning the smallest values are assigned there while larger numbers are reserved for useful positions.

Large Overlapping Requests

Many requests may overlap heavily on a small set of indices.

A naive implementation that increments every index inside every range would become too slow and could exceed time limits.

The difference array avoids this issue entirely. Each request performs only two constant-time updates regardless of range size, making the solution scalable to 100,000 requests.

Very Large Sums

Since both nums[i] and request counts can become large, the total sum may exceed normal integer ranges.

This is particularly important in Go, where integer overflow can occur more easily depending on architecture.

Our implementation applies modulo arithmetic throughout accumulation and uses int64 in Go to safely store intermediate products before taking the modulo.