Maximum Sum Obtained of Any Permutation solution and explanation
Google
9 more videos on this problem
Maximum Sum Obtained of Any Permutation | Leetcode 1589 | Line Sweep Concepts & Questions - 9 | MIKcodestorywithMIK · 26:26 · 3K views
Max Sum Obtained of Any Permutation | LeetCode 1589 | Explained and Java CodeNate Santti · 13:27 · 2K views
Maximum Sum Obtained of Any Permutation - A visual editorial | LC Biweekly 35 | Difference ArraysThe Algorithmic Eye · 8:35 · 1K views
1589. Maximum Sum Obtained of Any Permutation (Leetcode Medium)Programming Live with Larry · 22:31 · 526 views
【每日一题】1589. Maximum Sum Obtained of Any Permutation, 9/22/2020Huifeng Guan · 23:21 · 396 views
Leetcode 1589. Maximum Sum Obtained of Any Permutation (difference array)LetsCode · 10:29 · 299 views
Leetcode 1589. [Medium] Maximum Sum Obtained of Any PermutationFrancesco Manicardi · 6:03 · 142 views
LeetCode | Maximum Sum Obtained of Any Permutation | Coding Interview QuestionCode with Muggle · 14:59 · 127 views
Online Coding Interview of a college student | Maximum Sum Obtained of Any Permutation | LeetcodeCP Addict · 45:07 · 100 views
Leetcode 1589. Maximum Sum Obtained of Any Permutation (difference array)LetsCode · 8:53 · 53 views
The problem
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.length1 <= n <= 1050 <= nums[i] <= 1051 <= requests.length <= 105requests[i].length == 20 <= 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.
class Solution:
def maxSumRangeQuery(self, nums, requests):
MOD = 10**9 + 7
n = len(nums)
count = [0] * n
for start, end in requests:
count[start] += 1
if end + 1 < n:
count[end + 1] -= 1
for i in range(1, n):
count[i] += count[i - 1]
nums.sort()
count.sort()
return sum((a * b) % MOD for a, b in zip(nums, count)) % MODimport java.util.Arrays;
class Solution {
private static final int MOD = 1_000_000_007;
public int maxSumRangeQuery(int[] nums, int[][] requests) {
int n = nums.length;
int[] count = new int[n];
for (int[] req : requests) {
count[req[0]]++;
if (req[1] + 1 < n) {
count[req[1] + 1]--;
}
}
for (int i = 1; i < n; ++i) {
count[i] += count[i - 1];
}
Arrays.sort(count);
Arrays.sort(nums);
long result = 0;
for (int i = 0; i < n; ++i) {
result = (result + (long) nums[i] * count[i]) % MOD;
}
return (int) result;
}
}#include <vector>
#include <algorithm>
#define MOD 1000000007
class Solution {
public:
int maxSumRangeQuery(std::vector<int>& nums, std::vector<std::vector<int>>& requests) {
int n = nums.size();
std::vector<int> count(n);
for (const auto& req : requests) {
count[req[0]]++;
if (req[1] + 1 < n) {
count[req[1] + 1]--;
}
}
for (int i = 1; i < n; ++i) {
count[i] += count[i - 1];
}
std::sort(count.begin(), count.end(), std::greater<int>());
std::sort(nums.begin(), nums.end(), std::greater<int>());
long long result = 0;
for (int i = 0; i < n; ++i) {
result = (result + static_cast<long long>(nums[i]) * count[i]) % MOD;
}
return static_cast<int>(result);
}
};var maxSumRangeQuery = function(nums, requests) {
const MOD = 1e9 + 7;
const n = nums.length;
const count = new Array(n).fill(0);
for (let [start, end] of requests) {
count[start]++;
if (end + 1 < n) {
count[end + 1]--;
}
}
for (let i = 1; i < n; i++) {
count[i] += count[i - 1];
}
nums.sort((a, b) => a - b);
count.sort((a, b) => a - b);
let result = 0;
for (let i = 0; i < n; i++) {
result = (result + nums[i] * count[i]) % MOD;
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int cmpfunc(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}
int maxSumRangeQuery(int* nums, int numsSize, int** requests, int requestsSize, int* requestsColSize) {
int* count = (int*)calloc(numsSize, sizeof(int));
for (int i = 0; i < requestsSize; i++) {
count[requests[i][0]]++;
if (requests[i][1] < numsSize - 1) {
count[requests[i][1] + 1]--;
}
}
for (int i = 1; i < numsSize; i++) {
count[i] += count[i - 1];
}
qsort(count, numsSize, sizeof(int), cmpfunc);
qsort(nums, numsSize, sizeof(int), cmpfunc);
long long result = 0;
for (int i = 0; i < numsSize; i++) {
result = (result + (long long)nums[i] * count[i]) % MOD;
}
free(count);
return (int)result;
}using System;
public class Solution {
public int MaxSumRangeQuery(int[] nums, int[][] requests) {
const int MOD = 1000000007;
int n = nums.Length;
int[] count = new int[n];
foreach (var req in requests) {
count[req[0]]++;
if (req[1] + 1 < n) {
count[req[1] + 1]--;
}
}
for (int i = 1; i < n; i++) {
count[i] += count[i - 1];
}
Array.Sort(count);
Array.Sort(nums);
long result = 0;
for (int i = 0; i < n; i++) {
result = (result + (long)nums[i] * count[i]) % MOD;
}
return (int)result;
}
}In Python, list comprehensions and zip are used for concise expression of the final sum computation. The logic remains consistent with prior implementations.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n), the frequency count list.
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.
class Solution:
def maxSumRangeQuery(self, nums, requests):
MOD = 10**9 + 7
n = len(nums)
count = [0] * (n + 1)
for start, end in requests:
count[start] += 1
count[end + 1] -= 1
for i in range(1, n):
count[i] += count[i - 1]
nums.sort()
count = count[:-1]
count.sort()
return sum((a * b) % MOD for a, b in zip(nums, count)) % MODimport java.util.Arrays;
class Solution {
private static final int MOD = 1_000_000_007;
public int maxSumRangeQuery(int[] nums, int[][] requests) {
int n = nums.length;
int[] count = new int[n + 1];
for (int[] req : requests) {
count[req[0]]++;
count[req[1] + 1]--;
}
for (int i = 1; i < n; ++i) {
count[i] += count[i - 1];
}
Arrays.sort(count, 0, n);
Arrays.sort(nums);
long result = 0;
for (int i = 0; i < n; ++i) {
result = (result + (long) nums[i] * count[i]) % MOD;
}
return (int) result;
}
}#include <vector>
#include <algorithm>
#define MOD 1000000007
class Solution {
public:
int maxSumRangeQuery(std::vector<int>& nums, std::vector<std::vector<int>>& requests) {
int n = nums.size();
std::vector<int> count(n + 1);
for (const auto& req : requests) {
count[req[0]]++;
count[req[1] + 1]--;
}
for (int i = 1; i < n; ++i) {
count[i] += count[i - 1];
}
std::sort(count.begin(), count.end() - 1, std::greater<int>());
std::sort(nums.begin(), nums.end(), std::greater<int>());
long long result = 0;
for (int i = 0; i < n; ++i) {
result = (result + static_cast<long long>(nums[i]) * count[i]) % MOD;
}
return static_cast<int>(result);
}
};var maxSumRangeQuery = function(nums, requests) {
const MOD = 1e9 + 7;
const n = nums.length;
const count = new Array(n + 1).fill(0);
for (let [start, end] of requests) {
count[start]++;
count[end + 1]--;
}
for (let i = 1; i < n; i++) {
count[i] += count[i - 1];
}
nums.sort((a, b) => a - b);
count.sort((a, b) => a - b);
let result = 0;
for (let i = 0; i < n; i++) {
result = (result + nums[i] * count[i]) % MOD;
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int cmpfunc(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}
int maxSumRangeQuery(int* nums, int numsSize, int** requests, int requestsSize, int* requestsColSize) {
int* count = (int*)calloc(numsSize + 1, sizeof(int));
for (int i = 0; i < requestsSize; i++) {
count[requests[i][0]]++;
count[requests[i][1] + 1]--;
}
for (int i = 1; i < numsSize; i++) {
count[i] += count[i - 1];
}
qsort(count, numsSize, sizeof(int), cmpfunc);
qsort(nums, numsSize, sizeof(int), cmpfunc);
long long result = 0;
for (int i = 0; i < numsSize; i++) {
result = (result + (long long)nums[i] * count[i]) % MOD;
}
free(count);
return (int)result;
}using System;
public class Solution {
public int MaxSumRangeQuery(int[] nums, int[][] requests) {
const int MOD = 1000000007;
int n = nums.Length;
int[] count = new int[n + 1];
foreach (var req in requests) {
count[req[0]]++;
count[req[1] + 1]--;
}
for (int i = 1; i < n; i++) {
count[i] += count[i - 1];
}
Array.Sort(count, 0, n);
Array.Sort(nums);
long result = 0;
for (int i = 0; i < n; i++) {
result = (result + (long)nums[i] * count[i]) % MOD;
}
return (int)result;
}
}The refined prefix technique in Python discards the initial and final elements minimizing bounds and enhancing computational flow.
Time Complexity: O(n log n) because of sorting actions.
Space Complexity: O(n), following standard frequency handling with prefix sums.
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.
function maxSumRangeQuery(nums: number[], requests: number[][]): number {
const n = nums.length;
const d = new Array(n).fill(0);
for (const [l, r] of requests) {
d[l]++;
if (r + 1 < n) {
d[r + 1]--;
}
}
for (let i = 1; i < n; ++i) {
d[i] += d[i - 1];
}
nums.sort((a, b) => a - b);
d.sort((a, b) => a - b);
let ans = 0;
const mod = 10 ** 9 + 7;
for (let i = 0; i < n; ++i) {
ans = (ans + nums[i] * d[i]) % mod;
}
return ans;
}func maxSumRangeQuery(nums []int, requests [][]int) (ans int) {
n := len(nums)
d := make([]int, n)
for _, req := range requests {
l, r := req[0], req[1]
d[l]++
if r+1 < n {
d[r+1]--
}
}
for i := 1; i < n; i++ {
d[i] += d[i-1]
}
sort.Ints(nums)
sort.Ints(d)
const mod = 1e9 + 7
for i, a := range nums {
b := d[i]
ans = (ans + a*b) % mod
}
returnComplexity comparison
| Approach | Complexity |
|---|---|
| Frequency-Based Greedy Approach | Time Complexity: O(n log n) due to sorting. |
| Prefix Sum Optimization | Time Complexity: O(n log n) because of sorting actions. |
| Difference Array + Sorting + Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Range Summation | O(n * q) | O(1) | Useful only for understanding the problem or when constraints are very small |
| Frequency-Based Greedy with Sorting | O(n log n + q) | O(n) | General optimal solution; assign largest numbers to most frequently requested indices |
| Difference Array + Prefix Sum Optimization | O(n log n + q) | O(n) | Best when many range queries exist; processes each request in constant time |
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.