Maximize Array Value After Rearrangement

Given an array arr of n integers. Your task is to write a program to find the maximum value of ∑arr[i]*i, where i = 0, 1, 2,., n-1. You are allowed to rearrange the elements of the array.

Note: Since the output could be large, print the answer modulo 10⁹+7.

Examples :

Input : arr[] = [5, 3, 2, 4, 1]
Output : 40
Explanation: If we arrange the array as 1 2 3 4 5 then we can see that the minimum index will multiply with minimum number and maximum index will multiply with maximum number. So, 1*0 + 2*1 + 3*2 + 4*3 + 5*4 = 0+2+6+12+20 = 40 mod(109+7) = 40
​

Input : arr[] = [1, 2, 3]
Output : 8

Expected Time Complexity: O(nlog(n)).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ arr.size ≤ 10⁵
1 ≤ arr_i ≤ 10⁵

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int Maximize(vector<int>& values) {
        const int MODULO = 1e9 + 7;  // Modulo value
        sort(values.begin(), values.end());  // Sort the vector in ascending order
        int size = values.size();
        long long result = 0;  // Use long long to handle large numbers
        
        // Compute the result by iterating through the sorted values
        for (int index = 0; index < size; ++index) {
            result = (result + static_cast<long long>(values[index]) * index) % MODULO;
        }
        
        return static_cast<int>(result);  // Return the result as an integer
    }
};

class Solution:
    def Maximize(self, values):
        MODULO = 10**9 + 7  # Modulo value
        values.sort()  # Sort the list in ascending order
        size = len(values)
        result = 0  # Initialize the result
        
        # Compute the result by iterating through the sorted values
        for index in range(size):
            result = (result + values[index] * index) % MODULO
        
        return result  # Return the result as an integer

Time Complexity

• Sorting:

  The algorithm sorts the vector, which has a time complexity of \( O(n \log n) \), where \( n \) is the number of elements in the vector.

• Iteration:

  After sorting, the algorithm iterates through the vector once to compute the result, which has a time complexity of \( O(n) \).

• Total Time Complexity:

  Combining both operations, the overall time complexity is \( O(n \log n) \), dominated by the sorting step.

Space Complexity

• Vector Storage:

  The space complexity is dominated by the storage of the input vector, which requires \( O(n) \) space.

• Additional Space:

  The algorithm uses a constant amount of extra space for variables such as `result`, `index`, and constants. Thus, the additional space complexity is \( O(1) \).

• Overall Space Complexity:

  Considering both the storage for the input vector and the constant additional space, the overall space complexity is \( O(n) \).