Problem Description

You are given an integer array nums and an integer k.

An integer h is called valid if all values in the array that are strictly greater than h are identical (the same value).

For example, if nums = [10, 8, 10, 8]:

• h = 9 is valid because all values greater than 9 (which are the 10s) are identical
• h = 5 is not valid because values greater than 5 include both 8 and 10, which are different

You can perform the following operation on nums:

1. Select an integer h that is valid for the current values in nums
2. For each index i where nums[i] > h, set nums[i] to h

Your goal is to find the minimum number of operations required to make every element in nums equal to k. If it's impossible to make all elements equal to k, return -1.

The key insight is that each operation allows you to "flatten" all values above a certain threshold to that threshold value. Since you can only decrease values (never increase them), if any element in nums is already less than k, it's impossible to make all elements equal to k.

The solution uses a hash table to count unique values in the array. Since we can choose the second-largest value as our valid h in each operation (making all larger values equal to it), the minimum number of operations equals the number of unique values greater than k. If the minimum value in the array equals k, we need one less operation since k is already present.

Intuition

Let's think about what happens when we perform an operation. When we choose a valid h and apply the operation, all values strictly greater than h become equal to h. This means we're essentially "flattening" the array from the top down.

Consider the array [10, 8, 10, 8]. If we choose h = 9, all values greater than 9 (the 10s) become 9, resulting in [9, 8, 9, 8]. Now we have a new array with one less unique value above our target.

The key observation is: what's the most efficient valid h we can choose in each operation?

If we have distinct values like [12, 10, 8, 5] and want to reach k = 5, we could:

• Choose h = 11 to change 12 → 11, giving us [11, 10, 8, 5]
• Choose h = 10 to change 11 → 10, giving us [10, 10, 8, 5]
• And so on...

But this is inefficient! Instead, we should choose h = 10 (the second-largest value) in the first operation. This changes 12 → 10, immediately eliminating one unique value.

This leads to the insight: in each operation, we can eliminate exactly one unique value that's greater than k by choosing the second-largest value as our valid h. The largest value gets "collapsed" down to the second-largest.

Therefore, the minimum number of operations equals the count of unique values that are strictly greater than k. We use a set to track unique values, and if k itself appears in the original array (meaning k equals the minimum value), we subtract 1 from our count since k doesn't need to be changed.

If any value is less than k, we return -1 immediately since we can only decrease values, never increase them.

Solution Approach

The implementation follows directly from our intuition using a hash table (set) to track unique values:

1. Initialize data structures:

   • Create an empty set s to store unique values from the array
   • Initialize mi to infinity to track the minimum value in the array

2. Iterate through the array: For each element x in nums:

   • Check impossibility condition: If x < k, immediately return -1 since we can only decrease values, not increase them
   • Update minimum: Update mi = min(mi, x) to track the smallest value
   • Track unique values: Add x to the set s

3. Calculate the result:

   • The set s now contains all unique values in the array
   • Each unique value greater than k requires one operation to be eliminated
   • Return len(s) - int(k == mi)

The expression len(s) - int(k == mi) works as follows:

• len(s) gives us the total number of unique values
• If k == mi (meaning k is already the minimum value in the array), we subtract 1 because k itself doesn't need to be changed
• int(k == mi) converts the boolean to 1 if true, 0 if false

Time Complexity: O(n) where n is the length of the array, as we iterate through the array once.

Space Complexity: O(m) where m is the number of unique values in the array, for storing the set.

The elegance of this solution lies in recognizing that we don't need to simulate the actual operations. We just need to count how many "layers" of unique values exist above our target k.

Example Walkthrough

Let's walk through the solution with a concrete example where nums = [7, 2, 7, 5, 2] and k = 2.

Step 1: Build the set and check validity

• Process each element:
  • 7: Not less than k=2 ✓, add to set → s = {7}, mi = 7
  • 2: Not less than k=2 ✓, add to set → s = {7, 2}, mi = 2
  • 7: Not less than k=2 ✓, already in set → s = {7, 2}, mi = 2
  • 5: Not less than k=2 ✓, add to set → s = {7, 2, 5}, mi = 2
  • 2: Not less than k=2 ✓, already in set → s = {7, 2, 5}, mi = 2

Step 2: Count unique values

• Set s = {2, 5, 7} contains 3 unique values
• Minimum value mi = 2 equals k = 2

Step 3: Calculate operations needed

• Total unique values: len(s) = 3
• Since k == mi (both are 2), subtract 1: 3 - 1 = 2
• Result: 2 operations

Verification of the operations: Let's verify this makes sense by simulating the actual operations:

• Initial: [7, 2, 7, 5, 2] with unique values {2, 5, 7}
• Operation 1: Choose h = 5 (valid since all values > 5 are 7s, which are identical)
  • Array becomes [5, 2, 5, 5, 2] with unique values {2, 5}
• Operation 2: Choose h = 2 (valid since all values > 2 are 5s, which are identical)
  • Array becomes [2, 2, 2, 2, 2] with unique values {2}

The array now has all elements equal to k = 2, confirming our answer of 2 operations.

The key insight illustrated here: we had 3 unique values {2, 5, 7}, but since our target k = 2 was already present as the minimum, we only needed to eliminate the 2 unique values above it (5 and 7), requiring exactly 2 operations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array nums exactly once. During each iteration, it performs constant-time operations:

• Comparison x < k: O(1)
• Finding minimum with min(mi, x): O(1)
• Adding to set s.add(x): O(1) average case
• After the loop, len(s) and the final subtraction are both O(1)

Therefore, the overall time complexity is O(n), where n is the length of the array nums.

Space Complexity: O(n)

The algorithm uses a set s to store unique elements from the array. In the worst case, when all elements in nums are distinct, the set will contain all n elements. The variable mi uses O(1) space.

Therefore, the space complexity is O(n), where n is the length of the array nums.

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

Common Pitfalls

1. Misunderstanding the Valid H Condition

A common mistake is misinterpreting what makes an h value "valid". Students often think that h must be a value present in the array, but this is incorrect.

Wrong interpretation: "I can only choose h from values that exist in nums"

Correct understanding: h can be ANY integer, as long as all values strictly greater than h in the array are identical.

For example, if nums = [10, 8, 10, 8]:

• h = 9 is valid (not in array, but all values > 9 are the same: 10)
• h = 100 is valid (no values > 100, so the condition is vacuously true)
• h = 7.5 would be valid if we allowed decimals

2. Forgetting to Check for Values Less Than K

A critical pitfall is forgetting to check if any element is already less than k before processing:

# WRONG: Processes all values without checking impossibility
def minOperations(self, nums: List[int], k: int) -> int:
    unique_values = set(nums)
    min_value = min(nums)
    return len(unique_values) - (1 if k == min_value else 0)

Fix: Always check each element against k during iteration:

for num in nums:
    if num < k:  # Must check this FIRST
        return -1
    # ... rest of processing

3. Incorrectly Counting Operations When K is Not in the Array

Students might assume that if k is not present in the original array, they need an extra operation to create it:

# WRONG: Trying to add extra operation if k not in array
def minOperations(self, nums: List[int], k: int) -> int:
    unique_values = set()
    for num in nums:
        if num < k:
            return -1
        unique_values.add(num)
  
    # Incorrect logic: thinking we need extra operation if k not present
    if k not in unique_values:
        return len(unique_values) + 1  # WRONG!
    return len(unique_values) - 1

Correct approach: The number of operations depends only on how many unique values are greater than k. Whether k exists initially doesn't add operations—it only affects whether we subtract 1 from the count.

4. Using len(unique_values) - 1 Unconditionally

Another mistake is always subtracting 1 from the unique count without checking if k is the minimum:

# WRONG: Always subtracting 1
def minOperations(self, nums: List[int], k: int) -> int:
    unique_values = set()
    for num in nums:
        if num < k:
            return -1
        unique_values.add(num)
  
    return len(unique_values) - 1  # WRONG if k is not the minimum!

Why this fails: If nums = [10, 8, 10, 8] and k = 5:

• Unique values: {8, 10}
• We need 2 operations: first to reduce 10→8, then 8→5
• Wrong code returns 1, but correct answer is 2

Fix: Only subtract 1 when k equals the minimum value in the array, because only then is k already present and doesn't need to be "reached."