##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2592.html

# 2592. Maximize Greatness of an Array

## 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 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

## Solutions

Solution 1: Greedy

We can sort the array $nums$ first.

Then we define a pointer $i$ pointing to the first element of the array $nums$. We traverse the array $nums$, and for each element $x$ we encounter, if $x$ is greater than $nums[i]$, then we move the pointer $i$ to the right.

Finally, we return the value of the pointer $i$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$, where $n$ is the length of the array $nums$.

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

• 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;
}
};

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


• func maximizeGreatness(nums []int) int {
sort.Ints(nums)
i := 0
for _, x := range nums {
if x > nums[i] {
i++
}
}
return i
}

• function maximizeGreatness(nums: number[]): number {
nums.sort((a, b) => a - b);
let i = 0;
for (const x of nums) {
if (x > nums[i]) {
i += 1;
}
}
return i;
}