2592. Maximize Greatness of an Array

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

Solution (Java)

class Solution {
    public int maximizeGreatness(int[] nums) {
        PriorityQueue<Integer> pq1 = new PriorityQueue();
        PriorityQueue<Integer> pq2 = new PriorityQueue();
        for(int i: nums){
            pq1.add(i);
            pq2.add(i);
        }
        int count = 0;
        while(!pq2.isEmpty()){
            if(pq1.peek() < pq2.peek()){
                pq1.poll();
                count++;
            }
            pq2.poll();
        }
        return count;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).