Is Maximize Greatness of an Array easy or hard?

The problem is rated Medium because the greedy insight is not immediately obvious. Once you recognize that pairing the smallest numbers with the smallest possible larger numbers maximizes wins, the implementation becomes straightforward. The core difficulty lies in spotting the sorting-based greedy strategy.

Maximize Greatness of an Array Python/Java solution

Most implementations follow the same idea: sort the array and use two pointers to count how many elements can beat earlier elements. This logic translates directly to Python, Java, C++, C#, and JavaScript with minimal differences. The implementation typically fits within 10–15 lines of code.

How to solve Maximize Greatness of an Array in O(n)?

A near O(n) strategy can be implemented using a hash map or frequency table to track counts of values. Iterate through numbers and greedily match each value with the smallest strictly larger value still available. Hash lookups and updates are O(1) on average, giving overall linear behavior with O(n) additional space.

What is the best approach for Maximize Greatness of an Array?

The most common solution uses sorting and a greedy two-pointer technique. After sorting the array, one pointer tracks the smallest element that needs to be beaten while another searches for the next larger value. Each successful match increases the greatness score. This approach runs in O(n log n) time due to sorting and uses O(1) extra space.

Is Maximize Greatness of an Array asked at Google/Amazon/Meta?

This problem follows a classic greedy pairing pattern that appears in interviews at companies like Amazon, Google, and Meta. Variants involving rearranging arrays, advantage matching, or maximizing wins are common in technical interviews. Understanding sorting-based greedy matching is the key takeaway.

What data structure is used in Maximize Greatness of an Array?

The primary structures are arrays combined with sorting and two pointers for the greedy approach. An alternative solution uses a hash map or frequency table to track how many times each number appears. Both methods rely on efficiently finding a larger element to pair against the current value.

What is the time complexity of Maximize Greatness of an Array?

The optimal practical solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan with two pointers computes the maximum greatness in O(n). Space complexity can be O(1) if the sort is in place.

Description Hints 2 Solution Video 8:34

2592. Maximize Greatness of an Array

Medium62.0% acceptance7 companies

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⁹

Asked at 7 companies

Twilio WeRide NVIDIA UKG Oracle Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Can we use sorting and two pointers here?

Hint 2

Assign every element the next bigger unused element as many times as possible.

8:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution