#2592

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Maximize Greatness of an Array

Maximize Greatness of an Array requires permuting numbers to exceed original values at most indices efficiently.

Problem Statement

You are given a 0-indexed integer array nums and can rearrange its elements into a new array perm. The greatness of perm is defined as the number of indices i where perm[i] > nums[i].

Return the maximum possible greatness achievable after permuting nums. Consider that sorting and scanning with two pointers allows optimal matching of elements while tracking successful increments in greatness.

Examples

Example 1

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

Output: 4

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

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 <= 105
0 <= nums[i] <= 109

Solution Approach

Sort and Initialize Pointers

Sort nums to prepare for a greedy matching strategy. Initialize two pointers: one for the original array and one for the candidate permutation. This setup enables efficient scanning for greatness matches.

Greedy Two-Pointer Scan

Move through the sorted array using two pointers. For each element in the candidate permutation, check if it can exceed the current nums element. Increment greatness when a valid match is found and advance both pointers to maintain the invariant.

Finalize Maximum Greatness

Continue the two-pointer scan until all elements are considered. The pointer strategy guarantees that each increment is optimal. Return the total count of successful matches as the maximum greatness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n) and the two-pointer scan takes O(n), giving overall O(n log n) time. Space complexity is O(n) if creating a separate perm array, otherwise O(1) extra space with in-place operations.

What Interviewers Usually Probe

Consider sorting nums before attempting greedy matches.
Think about maintaining a pointer invariant to count successful greatness increments.
Watch for repeated numbers affecting the greedy scan outcome.

Common Pitfalls or Variants

Common pitfalls

Failing to sort nums leads to suboptimal matching and lower greatness.
Advancing pointers incorrectly can skip potential matches, reducing the result.
Ignoring duplicates can inflate or undercount greatness incorrectly.

Follow-up variants

Maximize greatness when only a subset of indices can be permuted.
Compute maximum greatness with additional constraints like fixed positions for certain elements.
Determine maximum greatness under a circular array matching constraint.

FAQ

What is the main strategy to solve Maximize Greatness of an Array?

Sort the array and use a two-pointer greedy scan to match larger numbers against smaller originals for maximal greatness.

Can duplicates affect the two-pointer approach?

Yes, duplicates require careful pointer advancement to ensure each increment is counted correctly without skipping matches.

What is the time complexity for this approach?

Sorting dominates with O(n log n) and the two-pointer scan is O(n), resulting in overall O(n log n) time complexity.

Do we need extra space to compute maximum greatness?

A separate perm array uses O(n) space, but the scan can also be done in-place with O(1) extra space if allowed.

Is this problem pattern-specific to two-pointer scanning?

Yes, the problem leverages two-pointer scanning with invariant tracking to implement the greedy matching strategy effectively.

terminal

Solution

Solution 1: Greedy

We can sort the array $nums$ first.

1

2

3

4

5

6

7

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            i += x > nums[i]
        return i

Continue Practicing

#2576 find the maximum number of marked indices #2410 maximum matching of players with trainers #2406 divide intervals into minimum number of groups