Maximize greatness of an array

Array Two Pointers Greedy Sorting

61.3% acceptance

Feb 25, 2026

505

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximize_greatness(mut nums: Vec<i32>) -> i32 {
    // Maximize the number of indices where perm[i] > nums[i].
    // Greedy: sort, then use two-pointer to maximally match each
    // element with a strictly greater element.
    nums.sort_unstable();
    let mut i = 0; // pointer to the "target" element we want to beat
    for j in 0..nums.len() {
      if nums[j] > nums[i] {
        i += 1; // matched nums[i] with nums[j]
      }
    }
    i as i32
  }
}