Skip to main content
Talentd

Maximum Sum Obtained of Any Permutation - Solution & Explanation

MediumArrayGreedySortingPrefix Sum20 min readAsked at: PayPal, Google
Practice this problem

Problem Statement

We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.

Return the maximum total sum of all requests among all permutations of nums.

Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.

Example 2:

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].

Example 3:

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i] <= 105
  • 1 <= requests.length <= 105
  • requests[i].length == 2
  • 0 <= starti <= endi < n

Approach Overview

Problem Overview: You are given an array nums and several range requests. Each request adds the sum of elements between two indices. You can permute nums in any order. The goal is to arrange the numbers so the total sum contributed by all requests is maximized.

The key observation: some indices appear in more requests than others. If an index participates in many ranges, placing a larger number there increases the total contribution. The entire problem becomes matching the largest numbers with the most frequently requested indices.

Approach 1: Frequency-Based Greedy Approach (O(n log n) time, O(n) space)

Count how many times each index appears across all requests. Instead of updating every element in every range, use a difference array: increment at l and decrement at r + 1. A single prefix pass converts this into the exact frequency for each index. Now you know how many times each position contributes to the final sum.

Sort the frequency array and sort nums. Pair the largest numbers with the highest frequencies and multiply them to compute the contribution. This greedy pairing works because assigning bigger values to indices used more often maximizes the weighted sum. Sorting dominates the runtime, giving O(n log n) time and O(n) space.

This technique combines ideas from array manipulation, greedy assignment, and sorting. The greedy step is optimal because both sequences are monotonic after sorting.

Approach 2: Prefix Sum Optimization (O(n log n + q) time, O(n) space)

Range requests are processed efficiently using a difference array and a prefix sum. Each request performs only two operations: diff[l]++ and diff[r+1]--. After processing all requests, compute the prefix sum to obtain the exact frequency each index is included in.

Once frequencies are known, the rest mirrors the greedy strategy: sort both arrays and accumulate nums[i] * freq[i]. Many implementations also apply a modulo operation (1e9 + 7) during accumulation to avoid overflow. This version scales well even when the number of requests is large because each request is handled in constant time.

Recommended for interviews: The frequency-based greedy solution with a difference array is the expected approach. A brute-force solution that sums every range shows basic understanding but runs in O(n * q) and fails large constraints. Using prefix sums to compute index frequencies and sorting to greedily assign values demonstrates strong algorithmic intuition.

Approach 1: Frequency-Based Greedy Approach

The idea is to compute how many times each index in the nums array is requested. Once we have the frequency of being requested for each index, we should sort both the frequency array and the nums array. This allows us to place the largest numbers in the most requested positions, thus maximizing the sum.

This solution calculates the frequency of each position in the nums array being requested using a difference array technique. After sorting both the nums array and the frequency array, they are multiplied element-wise to obtain the maximum sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting operations.
Space Complexity: O(n) for the frequency array.

Try this approach in the editor →

Approach 2: Prefix Sum Optimization

This approach builds upon the frequency-based greedy solution by using prefix sums for more efficient frequency computation. While still using sorting of nums and frequency, the prefix sum optimization minimizes repetitive operations.

This solution still uses the prefix sum array method as a more efficient frequency calculator. Incremental adjustments are made, optimized through prefix accumulation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) primarily from sorting.
Space Complexity: O(n) given the extra prefix count array.

Try this approach in the editor →

Approach 3: Difference Array + Sorting + Greedy

We observe that for a query operation, it returns the sum of all elements in the query interval [l, r]. The problem requires the maximum sum of the results of all query operations, which means we need to accumulate the results of all query operations to maximize the sum. Therefore, if an index i appears more frequently in the query operations, we should assign a larger value to index i to maximize the sum of the results of all query operations.

Therefore, we can use the idea of a difference array to count the number of times each index appears in the query operations, then sort these counts in ascending order, and also sort the array nums in ascending order. This ensures that the more frequently an index i appears in the query operations, the larger the value nums[i] corresponding to that index will be. Next, we only need to multiply the values nums[i] corresponding to these indices by the number of times they appear in the query operations, and then sum them up to get the maximum sum of the results of all query operations.

Time complexity O(n times log n), space complexity O(n). Where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Frequency-Based Greedy Approach

Time Complexity: O(n log n) due to sorting operations.
Space Complexity: O(n) for the frequency array.

Prefix Sum Optimization

Time Complexity: O(n log n) primarily from sorting.
Space Complexity: O(n) given the extra prefix count array.

Difference Array + Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Range SummationO(n * q)O(1)Useful only for understanding the problem or when constraints are very small
Frequency-Based Greedy with SortingO(n log n + q)O(n)General optimal solution; assign largest numbers to most frequently requested indices
Difference Array + Prefix Sum OptimizationO(n log n + q)O(n)Best when many range queries exist; processes each request in constant time

Video Solution

Maximum Sum Obtained of Any Permutation | Leetcode 1589 | Line Sweep Concepts & Questions - 9 | MIK • codestorywithMIK • 3,083 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Sum Obtained of Any Permutation easy or hard?
Maximum Sum Obtained of Any Permutation is classified as a Medium problem. The challenge is recognizing that the order of nums can be rearranged and that the optimal strategy is to assign larger numbers to indices used in more requests using a greedy sorting approach.
Maximum Sum Obtained of Any Permutation Python/Java solution
Most implementations follow the same pattern: build a difference array from the requests, compute prefix sums to get index frequencies, sort both nums and the frequency array, and sum the products modulo 1e9+7. The algorithm is identical across Python, Java, C++, and other languages.
How to solve Maximum Sum Obtained of Any Permutation in O(n)?
The frequency calculation part can be done in O(n + q) using a difference array and prefix sum. However, the final greedy step requires sorting the frequencies and the numbers, which adds O(n log n) time. Because of this sorting step, the overall optimal complexity remains O(n log n + q).
What is the best approach for Maximum Sum Obtained of Any Permutation?
The optimal approach counts how many times each index is included in the requests using a difference array and prefix sum. After computing these frequencies, sort both the frequency array and nums, then pair the largest numbers with the highest frequencies. This greedy assignment maximizes the weighted contribution of each index and runs in O(n log n + q) time.
Is Maximum Sum Obtained of Any Permutation asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving range frequency counting and greedy assignment. Variations of this idea appear in interviews at companies like Amazon, Google, and Meta, especially when testing knowledge of prefix sums, difference arrays, and sorting-based greedy optimization.
What data structure is used in Maximum Sum Obtained of Any Permutation?
The main structures are arrays along with a difference array technique. A prefix sum pass converts range updates into frequency counts for each index. After that, sorting is used to match the largest values with the most frequent indices for maximum contribution.
What is the time complexity of Maximum Sum Obtained of Any Permutation?
The optimal solution runs in O(n log n + q) time. Processing requests with a difference array takes O(q), computing the prefix sum takes O(n), and sorting both the frequencies and nums takes O(n log n). Space complexity is O(n) for storing the frequency counts.

Ready to solve this problem?

Practice Maximum Sum Obtained of Any Permutation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays