Skip to content

2592. Maximize Greatness of an Array

SourceBiweekly Contest 100 Q2DifficultyMediumRating1569

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

Thinking

Greatness is how many positions satisfy \(perm[i]>nums[i]\); \(perm\) is a rearrangement of \(nums\). The same multiset should pair larger values against as many smaller ones as possible.

After sorting, scan candidates \(x\) from the left and pair \(x\) with the next unmatched \(nums[i]\) whenever \(x\) is strictly larger. The number of successful pairs is the answer.

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\).

1
2
3
4
5
6
7
class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            i += x > nums[i]
        return i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maximizeGreatness(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        for (int x : nums) {
            if (x > nums[i]) {
                ++i;
            }
        }
        return i;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maximizeGreatness(nums []int) int {
    sort.Ints(nums)
    i := 0
    for _, x := range nums {
        if x > nums[i] {
            i++
        }
    }
    return i
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Comments