Maximize Greatness of an Array

Problem

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 themaximum possible greatness you can achieve after permuting nums.

Examples

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^5
• 0 <= nums[i] <= 10^9

Solution

Method 1 – Greedy Two Pointers

Intuition

To maximize the number of indices where perm[i] > nums[i], we want to match each number in nums with the smallest possible greater number from the permuted array. By sorting the array and using two pointers, we can greedily pair each number with the next greater number.

Approach

1. Sort the array nums.
2. Use two pointers, i and j, both starting at 0.
3. For each nums[i], move j forward until nums[j] > nums[i].
4. If such a j is found, increment the answer and both pointers.
5. Continue until either pointer reaches the end.
6. Return the answer.

Code

C++

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (nums[j] > nums[i]) {
                ans++;
                i++;
            }
            j++;
        }
        return ans;
    }
};

Go

func maximizeGreatness(nums []int) int {
    sort.Ints(nums)
    n, ans, i, j := len(nums), 0, 0, 0
    for i < n && j < n {
        if nums[j] > nums[i] {
            ans++
            i++
        }
        j++
    }
    return ans
}

Java

class Solution {
    public int maximizeGreatness(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (nums[j] > nums[i]) {
                ans++;
                i++;
            }
            j++;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maximizeGreatness(nums: IntArray): Int {
        nums.sort()
        var ans = 0
        var i = 0
        var j = 0
        while (i < nums.size && j < nums.size) {
            if (nums[j] > nums[i]) {
                ans++
                i++
            }
            j++
        }
        return ans
    }
}

Python

class Solution:
    def maximizeGreatness(self, nums: list[int]) -> int:
        nums.sort()
        n = len(nums)
        ans = i = j = 0
        while i < n and j < n:
            if nums[j] > nums[i]:
                ans += 1
                i += 1
            j += 1
        return ans

Rust

impl Solution {
    pub fn maximize_greatness(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        let (mut ans, mut i, mut j) = (0, 0, 0);
        while i < n && j < n {
            if nums[j] > nums[i] {
                ans += 1;
                i += 1;
            }
            j += 1;
        }
        ans as i32
    }
}

TypeScript

class Solution {
    maximizeGreatness(nums: number[]): number {
        nums.sort((a, b) => a - b);
        let n = nums.length, ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (nums[j] > nums[i]) {
                ans++;
                i++;
            }
            j++;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n) — for sorting the array and a single pass with two pointers.
• 🧺 Space complexity: O(1) — extra space, as sorting can be done in-place.