You are given an integer array nums. You may rearrange the elements of nums to form another array perm of the same length.
Define the greatness of perm as the number of indices i such that perm[i] > nums[i]. Return the maximum possible greatness over all rearrangements perm of nums.
Constraints:
Input: nums = [1, 3, 5, 2, 1, 3]-List[int]
Output: 4-int
Explanation: Sorting gives [1, 1, 2, 3, 3, 5], and two pointers greedily match a larger number to each base number when possible. One optimal rearrangement is perm = [2, 5, 3, 3, 1, 1], which, compared against the original nums = [1, 3, 5, 2, 1, 3], wins at indices 0, 1, 3, and 4, giving a greatness of 4.
Input: nums = [1, 1, 1]-List[int]
Output: 0-int
Explanation: All values are equal, so no matter how you rearrange, perm[i] > nums[i] is never true.
Input: nums = [1, 2, 3, 4]-List[int]
Output: 3-int
Explanation: An optimal rearrangement is perm = [2, 3, 4, 1]. Compared with the original, 2 > 1, 3 > 2, and 4 > 3 succeed while 1 > 4 fails, so the maximum greatness is 3 (you can’t get 4 because the largest element cannot be beaten).
Input: nums = [2, 2, 2, 3, 3]-List[int]
Output: 2-int
Explanation: Only the 3s can beat 2s. Placing the two 3s into positions where nums[i] = 2 yields exactly 2 indices with perm[i] > nums[i], and any remaining placements are 2 vs 2 or 2 vs 3, which do not increase greatness.
Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem: