# Maximize Greatness of an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-greatness-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/maximize-greatness-of-an-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce), [BlackRock](https://scaleengineer.com/companies/blackrock), [Twilio](https://scaleengineer.com/companies/twilio), [WeRide](https://scaleengineer.com/companies/weride)
---
## Problem
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` be 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`.

**Example 1:**

**Input:** nums = [1,3,5,2,1,3,1]
**Output:** 4
**Explanation:** One of the optimal rearrangements is perm = [2,5,1,3,3,1,1].
At indices = 0, 1, 3, and 4, perm[i] > nums[i]. Hence, we return 4.

**Example 2:**

**Input:** nums = [1,2,3,4]
**Output:** 3
**Explanation:** We can prove the optimal perm is [2,3,4,1].
At indices = 0, 1, and 2, perm[i] > nums[i]. Hence, we return 3.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 109`

# Approaches
## Sorting with a Two-Pointer Greedy Approach
A greedy approach can be formulated by first sorting the array. Once the array `nums` is sorted, the problem becomes finding the maximum number of pairs `(nums[i], nums[j])` such that `nums[j] > nums[i]` where each index is used at most once. To maximize this count, for each element `nums[i]`, we should greedily pick the smallest available element `nums[j]` that is larger than `nums[i]`. This strategy saves larger numbers for later elements which are themselves larger and thus harder to find a greater partner for. This greedy choice can be implemented efficiently using a two-pointer technique on the sorted array.
**Time:** O(N log N), dominated by the initial sorting of the array. The two-pointer scan that follows is O(N). · **Space:** O(log N) to O(N), depending on the sorting algorithm's space requirements. In Java, `Arrays.sort` for primitives uses a variant of Quicksort, which requires `O(log N)` space on average for the recursion stack.
**Pros:** The logic is relatively straightforward and easy to understand.; The implementation is simple and concise.; It correctly solves the problem by making locally optimal choices that lead to a global optimum.
**Cons:** The time complexity is dominated by the sorting step, which is `O(N log N)`. This can be slower than a linear time solution if one exists.
### Explanation
First, we sort the input array `nums`. This allows us to consider elements in increasing order. The core idea is to match elements from the first part of the sorted array with elements from the second part.

We use two pointers, `i` and `j`. The pointer `i` represents an element `nums[i]` for which we are trying to find a greater element in the permutation. The pointer `j` scans the array for an available element `nums[j]` to serve as that greater element.

We initialize `greatness = 0`, `i = 0`, and `j = 1`. We iterate through the array with `j`. If `nums[j]` is greater than `nums[i]`, we have found a successful pairing. We increment `greatness`, and since we've used `nums[i]` and `nums[j]`, we advance both pointers. If `nums[j]` is not greater than `nums[i]`, we can't use `nums[j]` for `nums[i]`. Since the array is sorted, we need to look further for a larger element, so we only advance `j`.

This process correctly counts the maximum number of such pairs, which corresponds to the maximum greatness.

```java
import java.util.Arrays;

class Solution {
    public int maximizeGreatness(int[] nums) {
        Arrays.sort(nums);
        int greatness = 0;
        int i = 0; // Pointer for the element that needs a greater partner
        
        // j is the pointer for the potential greater element in the permutation
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] > nums[i]) {
                greatness++;
                i++; // Move to the next element to find a partner for
            }
        }
        return greatness;
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. Initialize a `greatness` counter to 0.
3. Use two pointers, `i` (the slow pointer) starting at index 0, and `j` (the fast pointer) starting at index 1.
4. Iterate with the `j` pointer from 1 to the end of the array.
5. At each step, compare `nums[j]` with `nums[i]`.
6. If `nums[j] > nums[i]`, it means we've found a number `nums[j]` that can be used in the permutation to be greater than `nums[i]`. We increment `greatness` and also increment `i` to signify that we have found a match for `nums[i]` and are now looking for a match for the next element.
7. If `nums[j] <= nums[i]`, `nums[j]` cannot be a greater partner for `nums[i]`. We only increment `j` to find a larger candidate, while `i` remains unchanged.
8. Continue until `j` traverses the entire array.
9. The final `greatness` count is the answer.

## Optimal Solution by Frequency Counting
A more efficient approach avoids sorting and instead relies on a key insight about the problem's constraints. The maximum greatness is limited by the frequency of the most common element. If an element `x` appears `k` times, these `k` instances of `x` cannot be used to make each other 'great' (since `x` is not greater than `x`). This creates a bottleneck. It can be proven that the number of elements that cannot be made great is equal to the frequency of the most common element. Therefore, the maximum greatness is `n - max_freq`, where `n` is the total number of elements and `max_freq` is the highest frequency of any single element.
**Time:** O(N), as we only need to iterate through the array once to populate the frequency map and find the maximum frequency. · **Space:** O(K), where `K` is the number of unique elements in `nums`. This is for storing the frequency map. In the worst case, where all elements are unique, the space complexity is O(N).
**Pros:** Extremely efficient with a linear time complexity of O(N).; Avoids the O(N log N) cost of sorting, making it significantly faster for large inputs.
**Cons:** Requires extra space for the frequency map, which can be up to O(N) in the worst case (all elements are unique).; The underlying logic is less intuitive than the sorting approach and relies on a key insight about permutations.
### Explanation
This optimal solution is based on a combinatorial argument. Let the most frequent element in `nums` be `x`, and its frequency be `k`. These `k` elements must be assigned a value from the permutation `perm` at their respective indices. To achieve greatness for these positions, `perm[i]` must be strictly greater than `x`. The `k` instances of `x` in the `perm` array cannot be used for this purpose.

Consider a permutation `perm` formed by a cyclic shift of the sorted version of `nums` by `k` positions. This construction shows that a greatness of `n - k` is always achievable. It can also be argued that it's impossible to achieve a greatness of more than `n - k`, as the `k` instances of the most frequent element act as a bottleneck.

Thus, the problem reduces to finding the frequency of the most common element. We can do this in a single pass through the array using a hash map to store frequencies.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maximizeGreatness(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        int maxFreq = 0;
        for (int num : nums) {
            int newCount = counts.getOrDefault(num, 0) + 1;
            counts.put(num, newCount);
            if (newCount > maxFreq) {
                maxFreq = newCount;
            }
        }
        return nums.length - maxFreq;
    }
}
```
### Algorithm
1. Create a frequency map (e.g., a `HashMap`) to store the counts of each unique number in the `nums` array.
2. Iterate through the `nums` array once.
3. For each number, update its count in the frequency map.
4. While populating the map, keep track of the highest frequency encountered so far (`maxFreq`).
5. After the loop, `maxFreq` will hold the frequency of the most common element in the array.
6. The maximum possible greatness is the total number of elements minus this maximum frequency: `nums.length - maxFreq`.

# Solutions
### Java

```java
class Solution {
public
  int maximizeGreatness(int[] nums) {
    Arrays.sort(nums);
    int i = 0;
    for (int x : nums) {
      if (x > nums[i]) {
        ++i;
      }
    }
    return i;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximizeGreatness(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int i = 0;
    for (int x : nums) {
      i += x > nums[i];
    }
    return i;
  }
};

```

### Python

```python
class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int: nums . sort() i = 0 for x in nums: i += x > nums[i] return i

```