Maximize Greatness of an Array - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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 1: Approach 1: Use Sorting and Two-Pointers
The simplest approach is to sort the array and then use the two-pointer technique to find pairs that sum up to the target.
Steps:
- Sort the array.
- Initialize two pointers, one at the start and the other at the end of the array.
- Iterate through the array, adjust the pointers based on the sum of values at the pointers.
This C solution first sorts the array using the built-in qsort function. It then uses two pointers, initialized at the start and end of the array, to traverse the array. By adjusting these pointers based on the sum of the values at their positions relative to the target, it efficiently finds all pairs in the array that sum up to the target.
Complexity
Time Complexity: O(n log n), primarily due to the sorting step.
Space Complexity: O(1), as we're using pointers and not storing additional data structures.
Approach 2: Approach 2: Use Hash Map
This approach aims to find pairs by utilizing a hash map for achieving faster lookup times. This allows checking the complement for each number in the array.
Steps:
- Iterate over each element in the array.
- Check if the complement of the current element (target - current number) exists in the hash map.
- If it exists, a pair has been found; otherwise, store the current number in the hash map.
This C solution uses a simple hash map implementation via an array to store visited numbers. It looks for the complement of the current element in the hash map, printing out pairs whenever complements are found. This approach offers constant average time complexity for lookups.
Complexity
Time Complexity: O(n), with hash table lookups in constant time.
Space Complexity: O(n), for storing elements in the hash map.
Approach 3: 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use Sorting and Two-Pointers | Time Complexity: O(n log n), primarily due to the sorting step. Space Complexity: O(1), as we're using pointers and not storing additional data structures. |
| Approach 2: Use Hash Map | Time Complexity: O(n), with hash table lookups in constant time. Space Complexity: O(n), for storing elements in the hash map. |
| Greedy | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Maximize Greatness of an Array || 2-Pointer & Sorting || Leetcode-2592 • Aryan Mittal • 2,210 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximize Greatness of an Array easy or hard?
Maximize Greatness of an Array Python/Java solution
How to solve Maximize Greatness of an Array in O(n)?
What is the best approach for Maximize Greatness of an Array?
Is Maximize Greatness of an Array asked at Google/Amazon/Meta?
What data structure is used in Maximize Greatness of an Array?
What is the time complexity of Maximize Greatness of an Array?
Ready to solve this problem?
Practice Maximize Greatness of an Array with our built-in code editor and test cases.
Practice on FleetCode