Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Operations only decrease values, so any element below k makes the goal impossible. Otherwise a valid operation can lower the current largest distinct value to the next lower distinct level, eventually reaching k. Each distinct level above k requires one such reduction.

Approach

Build the set of distinct values, convert it to a list, and sort it. If its smallest value is below k, return -1. Otherwise count the distinct values strictly greater than k and return that count.

To achieve this bound, repeatedly choose the next lower distinct value as the threshold, using k for the final reduction. All values above that threshold are then equal, so the operation is valid. No operation can skip a lower distinct value still above the threshold, since that would leave unequal values above it. Therefore the number of distinct levels above k is both necessary and sufficient.

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        unique = set(nums)
        arr = list(unique)
        arr.sort()

        # 1. If any element is smaller than k, return -1
        if arr[0] < k:
            return -1

        # 2. Count elements greater than k
        count = 0
        for x in arr:
            if x > k:
                count += 1

        return count

Complexity analysis

Let n = nums.length and u be its number of distinct values. Time: O(n + u log u). Auxiliary space: O(u).