Maximize Greatness of an Array — Problem & Solution
Maximize Greatness of an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximize Greatness of an Array is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may permute the integer array nums into a new array perm. The greatness of perm is the number of indices i with perm[i] > nums[i] (comparing against the original, unpermuted nums).
Return the maximum greatness you can achieve.
Example 1
Input: nums = [2,7,2,4,9]
Output: 3
Explanation: `perm = [4,9,7,2,2]` beats `nums` at indices 0, 1 and 2. The two 2s can never both be beaten by smaller-or-equal values left over.
Example 2
Input: nums = [6,6,6]
Output: 0
Example 3
Input: nums = [1,2,3,4]
Output: 3
Explanation: `perm = [2,3,4,1]`.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
Hints for Maximize Greatness of an Array
Hint 1
Only the multiset of values matters: think of matching each original value with a strictly larger value from the same multiset.
Hint 2
Sort. Try to beat the smallest values first, each with the smallest value that is strictly larger.
Hint 3
Two pointers over the sorted array: a pointer to the next value to beat, and a scan for the next strictly larger one.
How to solve Maximize Greatness of an Array
This is a matching problem on the sorted values: pair as many values as possible with a strictly larger partner, each value used once as a partner. Greedily beating the smallest remaining value with the smallest sufficient partner is optimal.
Approach
- Sort
numsascending intos. - Keep
beaten = 0— the index insof the smallest value not yet beaten. - Scan
xovers; wheneverx > s[beaten], usexto beat it and incrementbeaten. - Return
beaten.
Why it works
Exchange argument: in any optimal matching we can reassign partners so that the smallest beaten values are beaten by the smallest larger values without losing a pair, so the greedy count is optimal. Equivalently, the answer is n minus the largest multiplicity of a value — copies of the most frequent value can only be beaten by larger values, and at most n - maxFreq such partners exist.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- The comparison is strict: an equal value does not count.
- Sorting
permalone and comparing position by position is not the same as matching — use the greedy scan. - The answer never exceeds
n - 1: the largest value can never be beaten.
Reference solution
Python
from typing import List
def maximizeGreatness(nums: List[int]) -> int:
s = sorted(nums)
beaten = 0
for x in s:
if x > s[beaten]:
beaten += 1
return beatenJava
public static int maximizeGreatness(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
int beaten = 0;
for (int x : s) if (x > s[beaten]) beaten++;
return beaten;
}C++
int maximizeGreatness(vector<int>& nums) {
vector<int> s(nums.begin(), nums.end());
sort(s.begin(), s.end());
int beaten = 0;
for (int x : s) if (x > s[beaten]) beaten++;
return beaten;
}JavaScript
var maximizeGreatness = function(nums) {
var s = nums.slice().sort(function(a, b) { return a - b; });
var beaten = 0;
for (var i = 0; i < s.length; i++) if (s[i] > s[beaten]) beaten++;
return beaten;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms