Maximize Greatness of an Array

Maximize Greatness of an Array

What is this problem about?

The Maximize Greatness of an Array problem gives you an integer array nums. You are asked to create a permutation of nums called perm. The "greatness" of a permutation is defined as the number of indices i where perm[i] > nums[i]. Your goal is to return the maximum possible greatness you can achieve.

Why is this asked in interviews?

This is a pure logic and sorting optimization problem. Interviewers use it to see if candidates can abstract away the idea of generating permutations (which is $O(N!)$) and instead rely on the Two Pointers technique on sorted data. It is a fantastic question to evaluate if a candidate understands the concept of "greedy assignment"—pairing the smallest possible larger number to secure a point without wasting high-value numbers.

Algorithmic pattern used

This problem leverages Sorting combined with the Two Pointers (Greedy) pattern. To maximize the number of indices where perm[i] > nums[i], you should always try to beat nums[i] with the smallest possible number that is strictly greater than it.

1. Sort the array.
2. Use a left pointer starting at 0, and a right pointer iterating through the array.
3. If sorted_nums[right] > sorted_nums[left], you've found a valid pair! You increment the left pointer (essentially "locking in" a point of greatness) and continue moving right.
4. The final value of the left pointer is exactly your maximum greatness.

Example explanation

Array: [1, 3, 5, 2, 1, 3, 1]

1. Sort it: [1, 1, 1, 2, 3, 3, 5].
2. Initialize left = 0 (pointing to the first 1).
3. Iterate right from 0 to end:
   • right=0 (1): Not strictly greater than left (1).
   • right=1 (1): Not greater.
   • right=2 (1): Not greater.
   • right=3 (2): 2 > 1! Greatness point! Increment left to 1.
   • right=4 (3): 3 > 1! Greatness point! Increment left to 2.
   • right=5 (3): 3 > 1! Greatness point! Increment left to 3.
   • right=6 (5): 5 > 2! Greatness point! Increment left to 4. The final value of left is 4, which is our max greatness.

Common mistakes candidates make

A common mistake is over-engineering the solution using Hash Maps to count frequencies or attempting to construct the actual permutation array. The problem only asks for the count of the greatness, so physically building the permutation array wastes space and complicates the logic. Another error is using >= instead of strictly > when comparing pointers.

Interview preparation tip

When tackling the Maximize Greatness of an Array interview pattern, recognize that this is mathematically identical to the classic "Assign Mice to Holes" or "Assign Cookies to Children" greedy problems. If you want to beat a target, sort both arrays (in this case, the array against itself) and greedily match the smallest available winner to the smallest available target.