Maximize Greatness of an Array

Medium
1170.

Maximize Greatness of an Array

Maximize Greatness of an Array is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

You may permute the integer array nums into a new array perm. The greatness of perm is the number of indices i with perm[i] > nums[i] (comparing against the original, unpermuted nums).

Return the maximum greatness you can achieve.

Example 1

Input
nums = [2,7,2,4,9]
Output
3
Explanation
`perm = [4,9,7,2,2]` beats `nums` at indices 0, 1 and 2. The two 2s can never both be beaten by smaller-or-equal values left over.

Example 2

Input
nums = [6,6,6]
Output
0

Example 3

Input
nums = [1,2,3,4]
Output
3
Explanation
`perm = [2,3,4,1]`.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximizeGreatness = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize Greatness of an Array — Problem & Solution

Maximize Greatness of an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximize Greatness of an Array is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Two Pointers
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may permute the integer array nums into a new array perm. The greatness of perm is the number of indices i with perm[i] > nums[i] (comparing against the original, unpermuted nums).

Return the maximum greatness you can achieve.

Example 1

Input: nums = [2,7,2,4,9]
Output: 3
Explanation: `perm = [4,9,7,2,2]` beats `nums` at indices 0, 1 and 2. The two 2s can never both be beaten by smaller-or-equal values left over.

Example 2

Input: nums = [6,6,6]
Output: 0

Example 3

Input: nums = [1,2,3,4]
Output: 3
Explanation: `perm = [2,3,4,1]`.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

Hints for Maximize Greatness of an Array

  1. Hint 1

    Only the multiset of values matters: think of matching each original value with a strictly larger value from the same multiset.

  2. Hint 2

    Sort. Try to beat the smallest values first, each with the smallest value that is strictly larger.

  3. Hint 3

    Two pointers over the sorted array: a pointer to the next value to beat, and a scan for the next strictly larger one.

How to solve Maximize Greatness of an Array

This is a matching problem on the sorted values: pair as many values as possible with a strictly larger partner, each value used once as a partner. Greedily beating the smallest remaining value with the smallest sufficient partner is optimal.

Approach

  1. Sort nums ascending into s.
  2. Keep beaten = 0 — the index in s of the smallest value not yet beaten.
  3. Scan x over s; whenever x > s[beaten], use x to beat it and increment beaten.
  4. Return beaten.

Why it works

Exchange argument: in any optimal matching we can reassign partners so that the smallest beaten values are beaten by the smallest larger values without losing a pair, so the greedy count is optimal. Equivalently, the answer is n minus the largest multiplicity of a value — copies of the most frequent value can only be beaten by larger values, and at most n - maxFreq such partners exist.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • The comparison is strict: an equal value does not count.
  • Sorting perm alone and comparing position by position is not the same as matching — use the greedy scan.
  • The answer never exceeds n - 1: the largest value can never be beaten.

Reference solution

Python

from typing import List

def maximizeGreatness(nums: List[int]) -> int:
    s = sorted(nums)
    beaten = 0
    for x in s:
        if x > s[beaten]:
            beaten += 1
    return beaten

Java

public static int maximizeGreatness(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int beaten = 0;
    for (int x : s) if (x > s[beaten]) beaten++;
    return beaten;
}

C++

int maximizeGreatness(vector<int>& nums) {
    vector<int> s(nums.begin(), nums.end());
    sort(s.begin(), s.end());
    int beaten = 0;
    for (int x : s) if (x > s[beaten]) beaten++;
    return beaten;
}

JavaScript

var maximizeGreatness = function(nums) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var beaten = 0;
    for (var i = 0; i < s.length; i++) if (s[i] > s[beaten]) beaten++;
    return beaten;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms