Watch 10 video solutions for Maximize Greatness of an Array, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by Aryan Mittal has 2,128 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1050 <= nums[i] <= 109Problem Overview: You are given an integer array nums. You can rearrange its elements to create a permutation perm. The goal is to maximize the number of indices i where perm[i] > nums[i]. In other words, you want as many elements as possible in the new arrangement to strictly beat the value at the same index in the original array.
Approach 1: Sorting + Two Pointers (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This is the clean greedy solution and the one most interviewers expect. Start by sorting nums. Use two pointers: one pointer i tracks the smallest element that still needs to be beaten, and another pointer j scans for a larger element that can beat it. If nums[j] > nums[i], you form a valid pair and increase the greatness count, then move both pointers forward. If not, move j forward until you find a larger value. Sorting exposes the smallest possible targets first, which ensures you use the minimal winning number each time and preserve larger numbers for future matches. This greedy matching pattern appears frequently in greedy and two pointers problems. The algorithm scans the sorted array once after sorting, producing an overall time complexity of O(n log n) and constant extra space if sorting in place.
Approach 2: Hash Map Frequency Matching (Time: O(n), Space: O(n))
You can also think of the problem as matching each number with the smallest strictly greater number available. Build a frequency map of all values using a hash map. Iterate through the numbers in increasing order and try to assign a larger value from the frequency table. Each time you find a candidate x, search for the next value > x that still has remaining frequency and decrement it. Every successful assignment increases the greatness score. This approach avoids explicitly storing a sorted permutation but still relies on ordered processing of values. It works well when you already maintain counts or when the value range is small. Hash lookups and frequency updates take O(1) on average, giving an overall complexity near O(n) with O(n) additional space. The strategy relies on counting techniques common in array and frequency-map problems.
Recommended for interviews: The sorting + two-pointer greedy solution is the most common interview answer. It demonstrates understanding of ordering, greedy pairing, and pointer techniques in a compact implementation. A brute-force comparison of permutations would be factorial time and impractical, so recognizing that sorted greedy pairing maximizes wins shows strong problem-solving intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointers (Greedy) | O(n log n) | O(1) extra (in-place sort) | Best general solution. Clean greedy logic and easy to implement in interviews. |
| Hash Map Frequency Matching | O(n) | O(n) | Useful when working with value frequencies or constrained ranges. |