1589. Maximum Sum Obtained of Any Permutation

Problem Description

In this problem, we have an array nums of integers and an array of requests. Each request is represented by a pair [start, end], which corresponds to a sum operation of the elements from nums[start] up to nums[end], inclusive. The goal is to calculate the maximum possible sum of all these individual request sums when we are allowed to permute nums. Since the result could be very large, it is asked to return the sum modulo 10^9 + 7, which is a common way to handle large numbers in programming problems to avoid integer overflow.

Intuition

To find the maximum total sum of all requests, we need to understand that the frequency of each element being requested affects the total sum. If an element is included in many requests, we want to assign a larger value from nums to that position to maximize the sum. Conversely, if an element is rarely requested or not at all, it should be assigned a smaller value.

The crux of the solution lies in the following insights:

Count the frequency of each index being requested: We can achieve this by using a "difference array" technique. In this approach, for each request [start, end], we increment d[start] and decrement d[end + 1]. After that, a prefix sum pass over the d array gives us the number of times each index is included in the range of the requests.
Sort both the nums and the frequency array d: By sorting the frequency array, we have a non-decreasing order of frequencies. Sorting nums also arranges the values in non-decreasing order. The intuition here is that we want to assign the highest values to the most frequently requested indices.
Calculate the maximum sum: We pair each number from nums with the corresponding frequency from d (after sorting both arrays), multiply them together, and accumulate the result to get the total sum. This works because both arrays are sorted, so the largest numbers are paired with the highest frequencies, ensuring the maximum total sum.

Finally, we take the calculated sum modulo 10^9 + 7 to prevent overflow and return this value as the result.

Learn more about Greedy, Prefix Sum and Sorting patterns.

Solution Approach

Here is the step-by-step breakdown of implementing the solution:

Initialization of the difference array: We initialize an array d of zeros with the same length as nums. This array will help us keep track of how many times each index in nums is requested.
Populate the difference array: For each request [l, r] in requests, increment d[l] by 1 and decrement d[r + 1] by 1 (being careful not to go out of bounds). This is the difference array technique where d[l] represents the change at index l, and d[r + 1] represents the change just after index r.
Calculate frequencies through prefix sums: We convert the difference array into a frequency array by calculating the prefix sum. In essence, for i in range(1, n): d[i] += d[i - 1] converts the difference array into a frequency array, which tells us how many times each index is involved in a request after summing up the contributions from d[0] up to d[i].
Sort the arrays: We sort both nums and the frequency array d in non-decreasing order using nums.sort() and d.sort(). By sorting these arrays, we ensure that the largest numbers in nums are lined up with the indices that occur most frequently in the requests.
Calculate the total sum: We calculate the total sum using sum(a * b for a, b in zip(nums, d)). Here, we multiply each number in nums with its corresponding frequency in d and accumulate the sum. Since both arrays are sorted, the highest frequency gets paired with the largest number, which is critical for maximizing the total sum.
Return the result modulo 10^9 + 7: To avoid overflow issues and comply with the problem constraints, we take the sum modulo 10**9 + 7, which we defined earlier as mod, and return this result.

The space complexity of the solution is O(n) due to the additional array d, and the time complexity is O(n log n) because we sort the arrays, which is the most time-consuming part of the algorithm.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution approach with a small example.

Suppose our nums array is [3, 5, 7, 9] and our requests array is [[0, 1], [1, 3], [0, 2]].

Step 1: Initialization of the difference array

We start with an array d of the same length as nums, plus one for the technique to work (length of nums plus one). Here d = [0, 0, 0, 0, 0].

Step 2: Populate the difference array

We go through each request and update our difference array d accordingly:

For the request [0, 1], we increment d[0] and decrement d[2]: d = [1, 0, -1, 0, 0].
For the request [1, 3], we increment d[1] and decrement d[4]: d = [1, 1, -1, 0, -1].
For the request [0, 2], we increment d[0] and decrement d[3]: d = [2, 1, -1, -1, -1].

Step 3: Calculate frequencies through prefix sums

Now we convert the difference array to a frequency array:

d = [2, 1, -1, -1, -1] becomes d = [2, 3, 2, 1, 0] after calculating prefix sums.

Step 4: Sort the arrays

We sort nums (it is already sorted) and we sort d: nums = [3, 5, 7, 9] and d = [0, 1, 2, 2, 3].

Step 5: Calculate the total sum

We calculate the sum by multiplying each element in nums by its corresponding frequency in d in their respective sorted orders:

sum = 3*0 + 5*1 + 7*2 + 9*2 = 0 + 5 + 14 + 18 = 37

Step 6: Return the result modulo 10^9 + 7

Finally, we take our sum 37 modulo 10^9 + 7. Since 37 is much less than 10^9 + 7, our final result is 37.

Therefore, the maximum possible sum of all request sums given the permutation of nums is 37.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
5        # Get the length of the nums array.
6        length_of_nums = len(nums)
7      
8        # Initialize a difference array with the same length as nums.
9        difference_array = [0] * length_of_nums
10      
11        # Iterate over each request to populate the difference array.
12        for start, end in requests:
13            # Increment the start index to indicate a new range starts at this index.
14            difference_array[start] += 1
15          
16            # Decrement the element after the end index to indicate the range ends at this index.
17            if end + 1 < length_of_nums:
18                difference_array[end + 1] -= 1
19      
20        # Calculate the prefix sum of the difference array to get the actual frequency array.
21        for i in range(1, length_of_nums):
22            difference_array[i] += difference_array[i - 1]
23      
24        # Sort both the nums array and the frequency array in non-decreasing order.
25        nums.sort()
26        difference_array.sort()
27      
28        # Initialize the modulus to avoid overflow issues with very large integers.
29        modulus = 10**9 + 7
30      
31        # Calculate the total sum by summing the product of corresponding elements 
32        # from the sorted nums array and the sorted frequency array.
33        total_sum = sum(num * frequency for num, frequency in zip(nums, difference_array))
34      
35        # Return the total sum modulo to ensure the result fits within the required range.
36        return total_sum % modulus
37

1class Solution {
2    public int maxSumRangeQuery(int[] nums, int[][] requests) {
3        // Define the length of the nums array.
4        int length = nums.length;
5      
6        // Create an array to keep track of the number of times each index is included in the ranges.
7        int[] frequency = new int[length];
8      
9        // Iterate over all the requests to calculate the frequency of each index.
10        for (int[] request : requests) {
11            int start = request[0], end = request[1];
12            frequency[start]++;
13            // Decrease the count for the index right after the end of this range
14            if (end + 1 < length) {
15                frequency[end + 1]--;
16            }
17        }
18      
19        // Convert the frequency array to a prefix sum array to get how many times each index is requested.
20        for (int i = 1; i < length; ++i) {
21            frequency[i] += frequency[i - 1];
22        }
23      
24        // Sort both the nums array and the frequency array.
25        Arrays.sort(nums);
26        Arrays.sort(frequency);
27      
28        // Modulo value to be used for not to exceed integer limits during the calculation.
29        final int mod = (int) 1e9 + 7;
30      
31        // Variable to store the result of the maximum sum.
32        long maxSum = 0;
33      
34        // Compute the maximum sum by pairing the largest numbers with the highest frequencies.
35        for (int i = 0; i < length; ++i) {
36            maxSum = (maxSum + (long) nums[i] * frequency[i]) % mod;
37        }
38      
39        // Return the maximum sum as an integer.
40        return (int) maxSum;
41    }
42}
43

1#include <vector>  // Required for using the std::vector
2#include <algorithm>  // Required for using the std::sort algorithm
3#include <cstring>  // Required for using the memset function
4
5class Solution {
6public:
7    int maxSumRangeQuery(std::vector<int>& nums, std::vector<std::vector<int>>& requests) {
8        int n = nums.size();
9      
10        // Array to keep track of frequency of indices being requested
11        std::vector<int> frequency(n, 0);
12      
13        // Increment start index and decrement just past the end index for each request
14        for(const auto& req : requests) {
15            int start = req[0], end = req[1];
16            frequency[start]++;
17            if (end + 1 < n) {
18                frequency[end + 1]--;
19            }
20        }
21      
22        // Convert frequency values into prefix sum to get the total count for each index
23        for (int i = 1; i < n; ++i) {
24            frequency[i] += frequency[i - 1];
25        }
26      
27        // Sort the input array and frequency array
28        std::sort(nums.begin(), nums.end());
29        std::sort(frequency.begin(), frequency.end());
30      
31        long long totalSum = 0;
32        const int MOD = 1e9 + 7; // Modulo value for result
33
34        // Compute the maximum sum of all ranges
35        for (int i = 0; i < n; ++i) {
36            totalSum = (totalSum + 1LL * nums[i] * frequency[i]) % MOD;
37        }
38      
39        // Casting to int as the Problem statement expects an int return type
40        return static_cast<int>(totalSum);
41    }
42};
43

1function maxSumRangeQuery(nums: number[], requests: number[][]): number {
2    const lengthOfNums = nums.length; // total number of elements in nums
3    const frequency = new Array(lengthOfNums).fill(0); // array to keep track of frequency of each index
4  
5    // Loop through each request to build the frequency array
6    for (const [start, end] of requests) {
7        frequency[start]++;
8        if (end + 1 < lengthOfNums) {
9            frequency[end + 1]--;
10        }
11    }
12  
13    // Convert frequency array to prefix sum array
14    for (let i = 1; i < lengthOfNums; ++i) {
15        frequency[i] += frequency[i - 1];
16    }
17  
18    // Sort the arrays to maximize the sum
19    nums.sort((a, b) => a - b);
20    frequency.sort((a, b) => a - b);
21  
22    let answer = 0; // variable to store the final answer
23    const modulo = 10 ** 9 + 7; // use modulo to avoid overflow
24  
25    // Calculate the maximum sum of all range queries
26    for (let i = 0; i < lengthOfNums; ++i) {
27        answer = (answer + nums[i] * frequency[i]) % modulo;
28    }
29  
30    return answer; // return the final answer
31}
32

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down as follows:

Initializing the array d: It is created with n zeros, where n is the length of nums. This operation takes O(n) time.
Populating the d array with the frequency of each index being requested: The for loop runs for each request, and each request updates two elements in d. The number of requests is the length of requests, let's say m. Hence, this step would take O(m) time.
Prefix sum of d array: This for loop iterates n-1 times, updating the d array with the cumulative frequency. This step takes O(n) time.
Sorting nums and d: Sorting an array of n elements takes O(n log n) time. Since both nums and d are sorted, this step takes 2 * O(n log n) time, which simplifies to O(n log n).
Calculating the sum product of nums and d: The zip operation iterates through both arrays once, so this takes O(n) time.

The most time-consuming operation here is the sorting step. Therefore, the overall time complexity of the algorithm is O(n log n) due to the sorting of nums and d.

Space Complexity

The space complexity of the code can be analyzed as follows:

Additional array d: This array is of size n, taking up O(n) space.
Sorting nums and d: In Python, the sort method sorts the array in place, so no additional space is needed for this step beyond the input arrays.
Temporary variables used for calculations and the sum operation (mod, loop variables, etc.) take O(1) space.

Therefore, the additional space used by the algorithm is for the d array, which gives us a space complexity of O(n).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

I don't know