Problem Description

You have an integer array nums with 0-based indexing. Your task is to rearrange this array into a new permutation called perm.

The greatness of the array is defined as the count of indices i (where 0 <= i < nums.length) for which perm[i] > nums[i]. In other words, greatness measures how many positions have a value in the permuted array that is strictly greater than the value at the same position in the original array.

Your goal is to find a permutation of nums that maximizes this greatness value and return the maximum possible greatness.

For example, if nums = [1, 3, 5, 2, 1, 3, 1], you could rearrange it to perm = [2, 5, 1, 3, 3, 1, 1]. Comparing position by position:

• Position 0: 2 > 1 ✓
• Position 1: 5 > 3 ✓
• Position 2: 1 < 5 ✗
• Position 3: 3 > 2 ✓
• Position 4: 3 > 1 ✓
• Position 5: 1 < 3 ✗
• Position 6: 1 = 1 ✗

This gives a greatness of 4 (positions 0, 1, 3, and 4 satisfy the condition).

The solution uses a greedy approach by sorting the array first. It maintains a pointer i starting at index 0. As it iterates through each element x in the sorted array, if x is greater than nums[i], it increments i. The final value of i represents the maximum greatness achievable, as it counts how many elements from the sorted array can be matched with smaller elements to create the perm[i] > nums[i] condition.

Intuition

To maximize greatness, we need to pair each element in the original array with a larger element from the same array in the permuted version. The key insight is that we want to use the smallest possible "larger" element for each position to avoid wasting our larger values.

Think of it this way: if we have a value 3 in the original array, we could pair it with 7 or 4 from our available elements. Using 4 instead of 7 is better because we save 7 for potentially pairing with a larger value later.

This naturally leads us to sort the array first. Once sorted, we can use a two-pointer approach where we try to create the most efficient pairings.

Consider the sorted array as two roles:

• The "original positions" that need to be beaten
• The "candidates" that we can use to beat them

We start with the smallest element in the "original positions" and try to find the smallest element from our "candidates" that can beat it. If we find one, we move to the next position to beat and the next candidate. If the current candidate can't beat the current position, we skip that candidate and try the next one.

For example, with sorted array [1, 1, 2, 3, 3, 5]:

• Can we beat 1 (at index 0)? Yes, with 2 → move both pointers
• Can we beat 1 (at index 1)? Yes, with 3 → move both pointers
• Can we beat 2 (at index 2)? Yes, with 3 → move both pointers
• Can we beat 3 (at index 3)? Yes, with 5 → move both pointers
• No more candidates left

This greedy strategy ensures we maximize the number of positions where perm[i] > nums[i] by always using the smallest sufficient value, preserving larger values for later use.

Learn more about Greedy, Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a greedy algorithm with these steps:

1. Sort the array: First, we sort nums in ascending order. This allows us to efficiently match smaller elements with their smallest possible "greater" counterparts.

   nums.sort()

2. Initialize a pointer: We use a single pointer i starting at position 0. This pointer tracks the current position in the sorted array that we're trying to "beat" (find a larger element for).

   i = 0

3. Traverse and match elements: We iterate through each element x in the sorted array. Each x serves as a potential candidate to beat the element at position i:

   for x in nums:
       i += x > nums[i]

   The clever part here is the expression x > nums[i]:

   • If x > nums[i], the comparison returns True (which equals 1 in Python), so i increments by 1
   • If x <= nums[i], the comparison returns False (which equals 0), so i stays the same

   When we increment i, it means we've successfully found a pairing where the permuted value beats the original value. We then move to the next position to beat.

4. Return the result: The final value of i represents the maximum number of positions where we achieved perm[i] > nums[i].

Why this works: By processing elements in sorted order, we ensure that:

• We always try to use the smallest possible element that can beat the current position
• We never waste larger elements on positions that could be beaten by smaller ones
• The pointer i only advances when we make a successful pairing, automatically counting our greatness

Time Complexity: O(n log n) due to sorting, where n is the length of the array.

Space Complexity: O(1) if we don't count the space used for sorting (in-place sorting), or O(n) if we consider the sorting space.

Example Walkthrough

Let's walk through the solution with nums = [2, 1, 3, 1].

Step 1: Sort the array

• Original: [2, 1, 3, 1]
• Sorted: [1, 1, 2, 3]

Step 2: Initialize pointer

• i = 0 (pointing to the first element we want to "beat")

Step 3: Iterate through sorted array

Step 4: Return result

• Final i = 2, so maximum greatness is 2

Understanding the result:

• We successfully paired:
  • Position 0 (value 1) with element 2 → 2 > 1 ✓
  • Position 1 (value 1) with element 3 → 3 > 1 ✓
• We couldn't beat positions 2 and 3 because we used up our larger elements

This means we can create a permutation like [2, 3, 1, 1] when mapped back to original indices, achieving a greatness of 2 (though the actual permutation construction isn't part of this algorithm - we only calculate the maximum achievable greatness).

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is dominated by the sorting operation nums.sort(), which uses Timsort algorithm in Python with O(n × log n) time complexity in the average and worst cases. The subsequent for loop iterates through the array once with O(n) operations, but this is absorbed by the larger sorting complexity.

The space complexity is O(log n), where n is the length of the array nums. While the sorting is done in-place and doesn't require additional space proportional to the input size, the sorting algorithm itself uses O(log n) space for the recursion stack during the divide-and-conquer process. The remaining operations use only O(1) additional space for the variable i and the loop variable x.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Pointer Logic

The Problem: Many developers initially misinterpret what the pointer i represents and try to use two separate pointers or arrays to track matches. They might attempt something like:

def maximizeGreatness(self, nums: List[int]) -> int:
    sorted_nums = sorted(nums)
    original = sorted(nums)  # Unnecessary copy
    count = 0
    used = [False] * len(nums)  # Tracking used elements
  
    for i in range(len(nums)):
        for j in range(len(sorted_nums)):
            if not used[j] and sorted_nums[j] > original[i]:
                count += 1
                used[j] = True
                break
    return count

Why It's Wrong: This approach overcomplicates the solution and doesn't leverage the key insight that we're comparing the same sorted array against itself with an offset.

The Fix: Understand that we're essentially trying to match elements from the sorted array with themselves, shifted by some positions. The single pointer tracks how many successful "shifts" we can make.

Pitfall 2: Confusing In-Place Modification

The Problem: Some might think the code is creating the actual permutation array and get confused when the function only returns a count:

def maximizeGreatness(self, nums: List[int]) -> int:
    nums.sort()
    perm = []  # Trying to build the actual permutation
    i = 0
  
    for x in nums:
        if x > nums[i]:
            perm.append(x)  # Wrong approach
            i += 1
  
    return len(perm)  # This won't give the correct answer

Why It's Wrong: The problem only asks for the maximum greatness value (a count), not the actual permutation. Building the permutation array incorrectly will lead to wrong results.

The Fix: Focus on counting successful pairings rather than constructing the actual permutation. The algorithm works by determining how many elements from the sorted array can be successfully paired with smaller elements.

Pitfall 3: Incorrect Boolean Addition

The Problem: In languages other than Python, or for developers unfamiliar with Python's boolean arithmetic, the line i += x > nums[i] might be confusing or implemented incorrectly:

def maximizeGreatness(self, nums: List[int]) -> int:
    nums.sort()
    i = 0
  
    for x in nums:
        if x > nums[i]:
            i = i + 1  # More verbose but clearer
        # Forgetting the else case or incrementing i always
        i += 1  # Wrong! This would increment twice when condition is true
  
    return i

Why It's Wrong: Adding an extra increment outside the conditional would count elements twice or advance the pointer incorrectly.

The Fix: Use either the concise boolean addition i += x > nums[i] or the explicit conditional:

for x in nums:
    if x > nums[i]:
        i += 1
    # No else needed; i stays the same if condition is false

Pitfall 4: Not Handling Edge Cases

The Problem: Failing to consider arrays where all elements are identical:

nums = [1, 1, 1, 1]

Why It Matters: In this case, no element can be greater than any other, so the maximum greatness should be 0. The algorithm handles this correctly (the pointer never advances), but developers might overthink and add unnecessary special case handling.

The Fix: Trust the algorithm - it naturally handles this case without special logic since x > nums[i] will always be False when all elements are equal.