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

1
2
3
4

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

1
2
3
4

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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.