Maximize Strict Wins by Permuting the Same Multiset
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Rearrange the entries of nums into a permutation perm of those entries. Its greatness is the number of indices i with perm[i]>nums[i]. Return the maximum greatness; do not return a witnessing permutation.
```cpp
class Solution {
public:
int maximizeGreatness(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [2,2,3,4]
Output: 2
Explanation: The permutation [3,4,2,2] wins at the first two positions. Only two entries exceed 2, so three wins are impossible.
```
**Example 2:**
```text
Input: nums = [7,7,7]
Output: 0
Explanation: Every rearranged value equals the value it would need to beat.
```
### Constraints
- `1 <= nums.length <= 100000`.
- `0 <= nums[i] <= 10^9`.
### Clarifying Questions
- Can new values be introduced? No; use a permutation of the same occurrences.
- Does equality count as a win? No; the new value must be strictly greater.
- Is the original array used for comparison? Yes.
- Is a permutation returned? No; return only the maximum win count.
```hint Check the boundary
Check an array whose entries are all equal.
```
Overview: Permute an array’s existing values to maximize the number of positions whose new value is strictly greater than the original value.