Skip to content

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

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