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

All Problems

All Solutions