Medium

Maximize Greatness of an Array

LAB

Return the maximum count of positions where a permutation of nums can place a strictly larger value than the original value.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    3,
    5,
    2,
    1,
    3,
    1
  ]
}

Output
4

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Instead of initializing both pointers at opposite ends, we initialize both at the beginning.

The idea is greedy - for every value v, the optimal permutation has the smallest greater value than v in the same index. Sort the array and keep pointer j representing the immediately next greater value than nums[i] in sorted order.

Edge case: when j == n (no larger value), we only match (i,j) when j < n. The final index of i is precisely the number of matched pairs.

Reveal reference solution +

pythonREFERENCE

def maximizeGreatness(self, nums: List[int]) -> int:
    nums.sort()
    i, j = 0, 0
    n = len(nums)

    while j < n:
        while j < n and nums[i] == nums[j]:
            j += 1
        # match nums[i] and nums[j]
        if j < n:
            i += 1
            j += 1

    return i

TimeO(n log n)

SpaceO(1)

Open on LeetCode ↗