LeetCode 2592. Maximize Greatness of an Array Solution in Java, C++, Python & More | Explanation + Code

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 × log n), and the space complexity is O(log n), where n is the length of the array nums.

PythonJavaC++GoTypeScript

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

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

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; } };(code-box)

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

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; }(code-box)