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.
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:
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.
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.
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:
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.
Time Complexity: O(n), with hash table lookups in constant time.
Space Complexity: O(n), for storing elements in the hash map.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Maximize Greatness of an Array || 2-Pointer & Sorting || Leetcode-2592 • Aryan Mittal • 2,128 views views
Watch 9 more video solutions →Practice Maximize Greatness of an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor