Maximize Greatness of an Array

Med

#2372Time: O(N log N), dominated by the initial sorting of the array. The two-pointer scan that follows is O(N).Space: O(log N) to O(N), depending on the sorting algorithm's space requirements. In Java, `Arrays.sort` for primitives uses a variant of Quicksort, which requires `O(log N)` space on average for the recursion stack.4 companies

Patterns

Two Pointers Greedy

Algorithms

Sorting

Data structures

Array

Companies

Salesforce BlackRock Twilio WeRide

Prompt

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 <= 10⁵
0 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A greedy approach can be formulated by first sorting the array. Once the array nums is sorted, the problem becomes finding the maximum number of pairs (nums[i], nums[j]) such that nums[j] > nums[i] where each index is used at most once. To maximize this count, for each element nums[i], we should greedily pick the smallest available element nums[j] that is larger than nums[i]. This strategy saves larger numbers for later elements which are themselves larger and thus harder to find a greater partner for. This greedy choice can be implemented efficiently using a two-pointer technique on the sorted array.

Algorithm

Sort the input array nums in non-decreasing order.
Initialize a greatness counter to 0.
Use two pointers, i (the slow pointer) starting at index 0, and j (the fast pointer) starting at index 1.
Iterate with the j pointer from 1 to the end of the array.
At each step, compare nums[j] with nums[i].
If nums[j] > nums[i], it means we've found a number nums[j] that can be used in the permutation to be greater than nums[i]. We increment greatness and also increment i to signify that we have found a match for nums[i] and are now looking for a match for the next element.
If nums[j] <= nums[i], nums[j] cannot be a greater partner for nums[i]. We only increment j to find a larger candidate, while i remains unchanged.
Continue until j traverses the entire array.
The final greatness count is the answer.

Walkthrough

First, we sort the input array nums. This allows us to consider elements in increasing order. The core idea is to match elements from the first part of the sorted array with elements from the second part.

We use two pointers, i and j. The pointer i represents an element nums[i] for which we are trying to find a greater element in the permutation. The pointer j scans the array for an available element nums[j] to serve as that greater element.

We initialize greatness = 0, i = 0, and j = 1. We iterate through the array with j. If nums[j] is greater than nums[i], we have found a successful pairing. We increment greatness, and since we've used nums[i] and nums[j], we advance both pointers. If nums[j] is not greater than nums[i], we can't use nums[j] for nums[i]. Since the array is sorted, we need to look further for a larger element, so we only advance j.

This process correctly counts the maximum number of such pairs, which corresponds to the maximum greatness.

1import java.util.Arrays;2 3class Solution {4    public int maximizeGreatness(int[] nums) {5        Arrays.sort(nums);6        int greatness = 0;7        int i = 0; // Pointer for the element that needs a greater partner8        9        // j is the pointer for the potential greater element in the permutation10        for (int j = 1; j < nums.length; j++) {11            if (nums[j] > nums[i]) {12                greatness++;13                i++; // Move to the next element to find a partner for14            }15        }16        return greatness;17    }18}

Complexity

Time

O(N log N), dominated by the initial sorting of the array. The two-pointer scan that follows is O(N).

Space

O(log N) to O(N), depending on the sorting algorithm's space requirements. In Java, `Arrays.sort` for primitives uses a variant of Quicksort, which requires `O(log N)` space on average for the recursion stack.

Trade-offs

Pros

The logic is relatively straightforward and easy to understand.
The implementation is simple and concise.
It correctly solves the problem by making locally optimal choices that lead to a global optimum.

Cons

The time complexity is dominated by the sorting step, which is O(N log N). This can be slower than a linear time solution if one exists.

A more efficient approach avoids sorting and instead relies on a key insight about the problem's constraints. The maximum greatness is limited by the frequency of the most common element. If an element x appears k times, these k instances of x cannot be used to make each other 'great' (since x is not greater than x). This creates a bottleneck. It can be proven that the number of elements that cannot be made great is equal to the frequency of the most common element. Therefore, the maximum greatness is n - max_freq, where n is the total number of elements and max_freq is the highest frequency of any single element.

Algorithm

Create a frequency map (e.g., a HashMap) to store the counts of each unique number in the nums array.
Iterate through the nums array once.
For each number, update its count in the frequency map.
While populating the map, keep track of the highest frequency encountered so far (maxFreq).
After the loop, maxFreq will hold the frequency of the most common element in the array.
The maximum possible greatness is the total number of elements minus this maximum frequency: nums.length - maxFreq.

Walkthrough

This optimal solution is based on a combinatorial argument. Let the most frequent element in nums be x, and its frequency be k. These k elements must be assigned a value from the permutation perm at their respective indices. To achieve greatness for these positions, perm[i] must be strictly greater than x. The k instances of x in the perm array cannot be used for this purpose.

Consider a permutation perm formed by a cyclic shift of the sorted version of nums by k positions. This construction shows that a greatness of n - k is always achievable. It can also be argued that it's impossible to achieve a greatness of more than n - k, as the k instances of the most frequent element act as a bottleneck.

Thus, the problem reduces to finding the frequency of the most common element. We can do this in a single pass through the array using a hash map to store frequencies.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maximizeGreatness(int[] nums) {6        Map<Integer, Integer> counts = new HashMap<>();7        int maxFreq = 0;8        for (int num : nums) {9            int newCount = counts.getOrDefault(num, 0) + 1;10            counts.put(num, newCount);11            if (newCount > maxFreq) {12                maxFreq = newCount;13            }14        }15        return nums.length - maxFreq;16    }17}

Complexity

Time

O(N), as we only need to iterate through the array once to populate the frequency map and find the maximum frequency.

Space

O(K), where `K` is the number of unique elements in `nums`. This is for storing the frequency map. In the worst case, where all elements are unique, the space complexity is O(N).

Trade-offs

Pros

Extremely efficient with a linear time complexity of O(N).
Avoids the O(N log N) cost of sorting, making it significantly faster for large inputs.

Cons

Requires extra space for the frequency map, which can be up to O(N) in the worst case (all elements are unique).
The underlying logic is less intuitive than the sorting approach and relies on a key insight about permutations.

Solutions

Solution

1class Solution {2public3  int maximizeGreatness(int[] nums) {4    Arrays.sort(nums);5    int i = 0;6    for (int x : nums) {7      if (x > nums[i]) {8        ++i;9      }10    }11    return i;12  }13}

1class Solution {2public:3  int maximizeGreatness(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int i = 0;6    for (int x : nums) {7      i += x > nums[i];8    }9    return i;10  }11};

1class Solution:2    def maximizeGreatness(self, nums: List[int]) -> int: nums . sort() i = 0 for x in nums: i += x > nums[i] return i

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem