Maximize Greatness of an Array

Problem Description

You are given a 0-indexed integer array nums. You are allowed to permute nums into a new array perm of your choosing. We define the greatness of nums as the number of indices 0 <= i < nums.length for which perm[i] > nums[i]. Return the maximum possible greatness you can achieve after permuting nums.

Key Insights

• The objective is to create a permutation of the array that maximizes the count where elements in the new array are greater than the corresponding elements in the original array.
• By sorting both the original array and the permutation, we can effectively pair the smallest available elements in the permutation with the elements of nums.
• Using a two-pointer approach allows us to efficiently determine how many elements can be paired to satisfy the condition.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(n) - for storing the sorted array.

Solution

To solve this problem, we can use the following approach:

1. Sort the original array nums.
2. Create a new array (perm) which will also be a permutation of nums (can be the same sorted array).
3. Use two pointers: one for iterating through the sorted nums and another for iterating through the sorted perm.
4. Whenever perm[j] > nums[i], it indicates a successful pairing where the greatness can be incremented. Move both pointers forward.
5. If perm[j] <= nums[i], just move the pointer for perm to find a larger value.
6. Count the number of successful pairings to determine the maximum greatness.

Code Solutions