LeetCode 2592 - Maximize Greatness of an Array

LeetCode Problem 2592

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

Here is the complete, detailed technical solution guide for LeetCode 2592 - Maximize Greatness of an Array following your formatting requirements.

Problem Understanding

The problem gives us an integer array nums and asks us to permute it into a new array perm such that the number of indices i for which perm[i] > nums[i] is maximized. This count is called the greatness of the permutation. The output should be the maximum possible greatness after any permutation.

In other words, for each element in the original array, we want to place a larger number in its position if possible. Since the array can be permuted, the ordering of nums does not restrict us. The key is identifying which elements can “beat” others to maximize the count.

Constraints give us important information about the input scale: nums can have up to 100,000 elements, and each element can be as large as 10^9. This immediately rules out any brute-force permutation solution, since there are n! possible permutations. We need a solution that runs in O(n log n) or O(n) time.

Important edge cases include arrays with all identical elements (maximum greatness is 0), arrays already strictly increasing or decreasing, and arrays with repeated numbers.

Approaches

Brute Force

The brute-force approach would generate all permutations of nums, then for each permutation, count the number of positions i such that perm[i] > nums[i]. The maximum count over all permutations is the answer.

This is obviously too slow: generating n! permutations is infeasible for n up to 10^5. Hence, brute force is not practical.

Optimal Approach

The key observation is that the problem reduces to a greedy matching problem. If we sort nums, then for each element x, we want to pair it with the smallest number greater than x in the array. This ensures we maximize the number of positions where perm[i] > nums[i].

We can implement this efficiently using sorting and a two-pointer approach:

1. Sort nums.
2. Use one pointer for the original sorted array and another for selecting candidates for the permutation.
3. Count how many elements in the sorted array can be matched with a strictly larger element.

Effectively, this is similar to counting the number of elements in a multiset that can be strictly paired with another element, maximizing the “wins.”

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Generates all permutations and counts greatness, infeasible for n > 10
Optimal	O(n log n)	O(n)	Sort array and use greedy two-pointer matching to maximize count

Algorithm Walkthrough

1. Sort nums in ascending order.
2. Initialize two pointers: i at the start of the sorted array (tracking elements to beat) and j at the start of the sorted array (tracking candidates for perm).
3. Initialize greatness = 0.
4. Iterate through the array with j. For each candidate element nums[j], check if nums[j] > nums[i].

• If true, increment greatness and move both pointers forward (we have successfully paired one element).
• If false, only move j forward (current candidate cannot beat the current i element, try next candidate).

5. Continue until either pointer reaches the end of the array.
6. Return greatness.

Why it works: Sorting guarantees that we always attempt to beat the smallest remaining element with the smallest available larger element. This greedy pairing maximizes the total number of elements we can “win” against, which is exactly the maximum greatness.

Python Solution

from typing import List

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        i = 0
        greatness = 0
        
        for j in range(n):
            if nums[j] > nums[i]:
                greatness += 1
                i += 1
        
        return greatness

Explanation: We first sort nums to enable greedy pairing. Pointer i tracks the elements we are trying to beat. Pointer j iterates through possible candidates in sorted order. Whenever nums[j] > nums[i], we can increment the greatness and move to the next element to beat. This loop ensures we maximize the total number of indices where perm[i] > nums[i].

Go Solution

import "sort"

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

Go-specific notes: The implementation mirrors the Python version. Sorting uses sort.Ints. Go slices automatically handle iteration with indices, and integers do not overflow in this problem range. Edge cases like empty slices are implicitly handled by the loop bounds.

Worked Examples

Example 1

nums = [1,3,5,2,1,3,1]

Sorted: [1,1,1,2,3,3,5]

i (to beat)	j (candidate)	nums[j] > nums[i]?	greatness
0	0	1 > 1? No	0
0	1	1 > 1? No	0
0	2	1 > 1? No	0
0	3	2 > 1? Yes	1 (i->1)
1	4	3 > 1? Yes	2 (i->2)
2	5	3 > 1? Yes	3 (i->3)
3	6	5 > 2? Yes	4 (i->4)

Output: 4

Example 2

nums = [1,2,3,4]

Sorted: [1,2,3,4]

i	j	nums[j] > nums[i]?	greatness
0	0	1 > 1? No	0
0	1	2 > 1? Yes	1
1	2	3 > 2? Yes	2
2	3	4 > 3? Yes	3

Output: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the array dominates the runtime, two-pointer iteration is O(n)
Space	O(n)	Sorting may require O(n) auxiliary space depending on language implementation

The greedy matching does not require additional data structures beyond pointers and counters.

Test Cases

# Provided examples
assert Solution().maximizeGreatness([1,3,5,2,1,3,1]) == 4  # mixed duplicates
assert Solution().maximizeGreatness([1,2,3,4]) == 3        # strictly increasing

# Edge cases
assert Solution().maximizeGreatness([1,1,1,1]) == 0        # all identical
assert Solution().maximizeGreatness([4,3,2,1]) == 3        # strictly decreasing
assert Solution().maximizeGreatness([1]) == 0              # single element
assert Solution().maximizeGreatness([1,2,2,3,3,3,4]) == 4  # duplicates mixed

Test	Why
[1,3,5,2,1,3,1]	Mixed duplicates test greedy matching correctness
[1,2,3,4]	Increasing array tests general correctness
[1,1,1,1]	All identical elements ensure greatness = 0
[4,3,2,1]	Decreasing array ensures sorting is necessary
[1]	Single element edge case
[1,2,2,3,3,3,4]	Duplicates test greedy selection

Edge Cases

1. All identical elements: If nums = [x, x, x, ...], no element can beat another, so greatness is 0. The algorithm correctly handles this because nums[j] > nums[i] never holds.
2. Single element array: With nums = [x], there is nothing to pair against, so greatness is 0. The loop never increments greatness and returns 0.
3. Arrays with multiple duplicates: For example, nums = [1,2,2,3]. Sorting ensures we match each i with the next largest j, preventing overcounting and correctly maximizing greatness. Greedy pairing avoids assigning a large number to a small one that does not yield additional greatness.
4. Strictly decreasing array: The algorithm handles decreasing sequences by sorting first, ensuring we can maximize matches. Without sorting, naive