LeetCode Problem 3375

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 3375 - Minimum Operations to Make Array Values Equal to K

Problem Understanding

The problem gives us an integer array nums and a target value k. Our goal is to transform the entire array so that every element becomes exactly equal to k.

However, we cannot arbitrarily change values. Each operation follows a very specific rule.

We choose an integer h such that all numbers strictly greater than h are identical. This condition makes h a valid choice. After choosing such an h, every value greater than h is replaced with h.

This operation effectively lowers the current maximum values in the array down to some smaller value.

The key observation is that we can only decrease values, never increase them. Therefore, if any element is already smaller than k, it is impossible to make the entire array equal to k.

The input constraints are very small:

• 1 <= nums.length <= 100
• 1 <= nums[i], k <= 100

These constraints mean that even relatively inefficient solutions would work, but the problem has a very elegant observation that leads to a simple optimal solution.

The important edge cases are:

• Arrays containing values smaller than k, which immediately make the answer -1
• Arrays where all elements already equal k, requiring 0 operations
• Arrays with multiple repeated large values
• Arrays with many distinct values larger than k

The operation structure implies that every distinct value larger than k must eventually be reduced, and each operation can only eliminate one distinct larger value at a time.

Approaches

Brute Force Approach

A brute force simulation would repeatedly search for a valid h, apply the operation, and continue until all values become k.

One way to do this is:

1. Find the current maximum value.
2. Reduce it to the next smaller distinct value.
3. Repeat until everything becomes k.

This works because the validity condition guarantees that the largest value can always be reduced.

However, this approach repeatedly modifies the array and repeatedly scans for distinct values. While still acceptable for the small constraints, it performs unnecessary work.

Key Insight

The important insight is that every distinct value greater than k requires exactly one operation.

Why?

Suppose the distinct values larger than k are:

9, 7, 5, 3

We cannot reduce both 9 and 7 simultaneously unless they are already equal. Since operations only affect numbers strictly greater than h, each operation removes exactly one distinct "layer" of values.

Therefore:

• If any number is smaller than k, return -1
• Otherwise, count how many distinct values are greater than k
• That count is the minimum number of operations

This reduces the problem to a simple set-counting problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly simulates reductions
Optimal	O(n)	O(n)	Counts distinct values greater than k

Algorithm Walkthrough

1. Initialize an empty set called greater_values.

The set will store every distinct number that is strictly greater than k. 2. Traverse the array one element at a time.

For each number:

• If the number is smaller than k, immediately return -1
• Otherwise, if the number is greater than k, add it to the set

3. After processing the entire array, return the size of the set.

Each distinct value greater than k corresponds to exactly one required operation.

Why it works

The operation can only decrease numbers. Therefore, any value below k makes the task impossible.

For values above k, each operation can only eliminate one distinct value level at a time. Since all larger values affected in an operation must already be identical, distinct larger values cannot be merged together in a single operation.

Thus, the minimum number of operations is exactly the number of distinct values greater than k. We are given an array nums and a target value k.

An operation works as follows:

• Choose an integer h that is valid for the current array.
• An integer h is valid if every array value strictly greater than h is the same number.
• After choosing h, every element greater than h is replaced by h.

The goal is to make every element of the array equal to k using the minimum number of operations.

The key observation is that an operation can only decrease values. No operation can increase an element. Therefore, if any element is already less than k, that element can never become k, making the task impossible.

To understand the operation more deeply, suppose the distinct values greater than k are:

$$v_1 < v_2 < \cdots < v_m$$

The only way to eliminate the largest value is to lower it to some smaller value. Because a valid h requires all values above h to be identical, each operation can remove at most one distinct value level from the set of values above k.

Consequently, the minimum number of operations is exactly the number of distinct values greater than k, provided that no element is less than k.

The constraints are very small:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

Even a less efficient solution would fit comfortably within the limits, but there is a very simple optimal solution.

Important edge cases include:

• Some element is less than k, making the answer -1.
• Every element already equals k, making the answer 0.
• Multiple occurrences of the same value above k, which require only one elimination step.
• Arrays with many distinct values above k, where each distinct level requires one operation.

Approaches

Brute Force

A direct simulation approach repeatedly performs operations until all values become k.

At each stage, identify the current distinct values, determine a valid choice of h, perform the operation, and continue until either all values equal k or the process becomes impossible.

This approach is correct because it explicitly follows the rules of the problem. However, it requires repeatedly modifying and scanning the array. Although the constraints are small, the simulation is unnecessarily complicated.

Key Insight

The operation only decreases values.

Therefore:

• If any value is less than k, it can never be increased to k, so the answer is -1.
• Otherwise, every value is at least k.

Now consider the distinct values greater than k.

Suppose these values are:

$$a_1 < a_2 < \cdots < a_t$$

The largest value a_t must eventually disappear. An operation can only eliminate one distinct value level at a time because all values above a valid threshold must be identical.

Thus each distinct value greater than k requires exactly one operation to remove.

Therefore:

$$\text{answer} = \left|{x \in nums : x > k}\right|_{\text{distinct}}$$

provided that no element is less than k.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly simulate operations and update the array
Optimal	O(n)	O(n)	Count distinct values greater than k after checking feasibility

Algorithm Walkthrough

Optimal Algorithm

1. Create an empty set to store distinct values greater than k.
2. Iterate through every element num in nums.
3. If num < k, immediately return -1.

This is necessary because operations can only decrease values, never increase them. 4. If num > k, insert it into the set.

The set automatically keeps only distinct values. 5. After processing the entire array, return the size of the set.

Each distinct value greater than k corresponds to one required operation.

Why it works

Assume every element is at least k.

Each operation can remove only the current largest distinct value level. Therefore every distinct value greater than k must be eliminated at least once, giving a lower bound equal to the number of distinct values greater than k.

Conversely, we can eliminate those values one by one from largest to smallest. Each elimination corresponds to a valid operation. Hence the lower bound is achievable.

Therefore the minimum number of operations is exactly the number of distinct values greater than k.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        greater_values = set()

        for num in nums:
            if num < k:
                return -1

            if num > k:
                greater_values.add(num)

        return len(greater_values)

The implementation directly follows the algorithm.

The set greater_values tracks all unique values larger than k. Using a set automatically removes duplicates, which is important because repeated identical values can all be reduced in the same operation.

During traversal:

• If we encounter a value smaller than k, we immediately return -1 because operations can never increase values.
• If the value is greater than k, we add it to the set.

Finally, the answer is simply the number of distinct larger values. The implementation directly follows the mathematical observation.

The loop first checks feasibility. If any value is below k, the function immediately returns -1.

For values greater than k, the code inserts them into a set. Since a set stores only unique values, duplicate occurrences are ignored automatically.

Finally, the size of the set is returned. This count equals the number of distinct value levels above k, which is the minimum number of required operations.

Go Solution

func minOperations(nums []int, k int) int {
    greaterValues := make(map[int]bool)

    for _, num := range nums {
        if num < k {
            return -1
        }

        if num > k {
            greaterValues[num] = true
        }
    }

    return len(greaterValues)
}

The Go implementation uses a map[int]bool to simulate a set, since Go does not have a built-in set type.

The logic is otherwise identical to the Python solution. The constraints are small, so integer overflow is not a concern. The Go solution uses a map[int]bool as a hash set because Go does not provide a built-in set type.

The logic is otherwise identical to the Python version. Every value below k immediately causes a return of -1, and every distinct value greater than k is recorded in the map. The answer is the number of keys in the map.

Since values are at most 100, integer overflow is not a concern.

Worked Examples

Example 1

Input: Input

nums = [5,2,5,4,5]
k = 2

We process each element:

Current Number	Action	Set Contents
5	Greater than 2, add to set	{5}
2	Equal to 2, ignore	{5}
5	Already in set	{5}
4	Greater than 2, add to set	{5, 4}
5	Already in set	{5, 4}

The set contains two distinct values greater than k. Process each element:

Current Value	Action	Set
5	Greater than k, add	{5}
2	Equal to k	{5}
5	Already present	{5}
4	Greater than k, add	{4,5}
5	Already present	{4,5}

Final set:

{4, 5}

Number of distinct values greater than k:

2

Answer:

2

Possible operations:

1. Reduce all 5s to 4
2. Reduce all 4s to 2

Example 2

Input:

Example 2

Input

nums = [2,1,2]
k = 2

Process elements:

Current Number	Action
2	Ignore
1	Smaller than 2, impossible

Since values cannot be increased, the answer is:

Current Value	Action
2	Equal to k
1	Less than k

A value below k is found.

Since operations cannot increase values:

return -1

Answer:

-1

Example 3

Input: Input

nums = [9,7,5,3]
k = 1

Process elements:

Current Number	Set Contents
9	{9}
7	{9, 7}
5	{9, 7, 5}
3	{9, 7, 5, 3}

There are four distinct values larger than 1.

Current Value	Set
9	{9}
7	{7,9}
5	{5,7,9}
3	{3,5,7,9}

Final set:

{3,5,7,9}

Size:

4

Answer:

4

Possible sequence:

1. 9 → 7
2. 7 → 5
3. 5 → 3
4. 3 → 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(n)	Set may store all distinct values

The algorithm scans the array exactly once. Every insertion into the set is an average O(1) operation.

In the worst case, every element is distinct and greater than k, so the set may contain up to n elements.

Test Cases

sol = Solution()

assert sol.minOperations([5, 2, 5, 4, 5], 2) == 2  # Example 1
assert sol.minOperations([2, 1, 2], 2) == -1  # Example 2
assert sol.minOperations([9, 7, 5, 3], 1) == 4  # Example 3

assert sol.minOperations([2, 2, 2], 2) == 0  # Already equal
assert sol.minOperations([3, 3, 3], 2) == 1  # Single distinct value above k
assert sol.minOperations([10], 10) == 0  # Single element already correct
assert sol.minOperations([10], 5) == 1  # Single element needs one reduction
assert sol.minOperations([1], 2) == -1  # Impossible single element case

assert sol.minOperations([5, 5, 5, 5], 1) == 1  # All same large value
assert sol.minOperations([6, 5, 4, 3, 2], 2) == 4  # Multiple distinct values
assert sol.minOperations([100, 99, 100, 98], 97) == 3  # Large values
assert sol.minOperations([4, 4, 3, 3, 2], 2) == 2  # Repeated distinct values
assert sol.minOperations([7, 7, 7], 8) == -1  # All below target

Test Summary

Test	Why
[5,2,5,4,5], k=2	Standard mixed case
[2,1,2], k=2	Impossible because of smaller value
[9,7,5,3], k=1	Many distinct reductions
[2,2,2], k=2	Already solved
[3,3,3], k=2	One distinct value above target
[10], k=10	Single element no-op
[10], k=5	Single reduction needed
[1], k=2	Impossible single element
[5,5,5,5], k=1	Duplicate large values
[6,5,4,3,2], k=2	Strictly descending values
[100,99,100,98], k=97	Large constraint values
[4,4,3,3,2], k=2	Repeated distinct groups
[7,7,7], k=8	Entire array below target

Edge Cases

One important edge case occurs when some element is already smaller than k. Since operations only decrease values, there is no way to increase that smaller element back up to k. A naive implementation that only counts distinct larger values might incorrectly produce a positive answer. The implementation prevents this by immediately returning -1 whenever num < k.

Another important case is when the array is already equal to k. In this situation, there are no distinct values greater than k, so the correct answer is 0. The set remains empty throughout processing, and the implementation correctly returns len(greater_values), which is zero.

A third edge case involves repeated large values. For example, [5,5,5,5] with k=1 only requires one operation, not four. A naive approach might incorrectly count every element individually. Using a set ensures that duplicate values are counted only once, producing the correct minimum number of operations. | Space | O(n) | Set may contain all distinct elements |

The algorithm scans the array exactly once. Every set insertion is expected O(1), so the total running time is O(n). The set stores only distinct values greater than k, requiring at most O(n) space.

Test Cases

from typing import List

s = Solution()

assert s.minOperations([5, 2, 5, 4, 5], 2) == 2  # example 1
assert s.minOperations([2, 1, 2], 2) == -1       # example 2
assert s.minOperations([9, 7, 5, 3], 1) == 4     # example 3

assert s.minOperations([2], 2) == 0              # single element already k
assert s.minOperations([5], 2) == 1              # single element above k
assert s.minOperations([1], 2) == -1             # single element below k

assert s.minOperations([3, 3, 3], 3) == 0        # all already equal
assert s.minOperations([4, 4, 4], 2) == 1        # one distinct value above k

assert s.minOperations([5, 5, 4, 4, 3, 3], 2) == 3  # three distinct levels
assert s.minOperations([10, 9, 8, 7], 7) == 3       # descending values

assert s.minOperations([100] * 100, 1) == 1         # maximum duplicates
assert s.minOperations(list(range(1, 101)), 1) == 99 # many distinct values

assert s.minOperations([2, 2, 2, 1], 2) == -1       # impossible due to smaller value
assert s.minOperations([6, 4, 6, 4, 2], 2) == 2     # duplicates of distinct levels

Test Summary

Test	Why
[5,2,5,4,5], k=2	Provided example
[2,1,2], k=2	Impossible case
[9,7,5,3], k=1	Multiple distinct levels
[2], k=2	Smallest valid array
[5], k=2	Single reduction needed
[1], k=2	Single impossible element
[3,3,3], k=3	Already solved
[4,4,4], k=2	One distinct value above k
[5,5,4,4,3,3], k=2	Multiple duplicate levels
[10,9,8,7], k=7	Strictly decreasing sequence
[100]*100, k=1	Maximum duplicate count
range(1,101), k=1	Many distinct values
[2,2,2,1], k=2	Feasibility failure
[6,4,6,4,2], k=2	Distinct-level counting

Edge Cases

An Element Smaller Than k

Consider:

nums = [2, 1, 2]
k = 2

A common mistake is to count distinct values above k without checking whether some value is below k. Since operations only decrease values, the value 1 can never become 2. The implementation immediately returns -1 when such an element is encountered.

All Elements Already Equal to k

Consider:

nums = [3, 3, 3]
k = 3

There are no values greater than k, so the set remains empty. The answer should be 0, not 1. Returning the size of the set correctly handles this situation.

Many Duplicate Values Above k

Consider:

nums = [5, 5, 5, 5]
k = 2

Although there are four elements above k, they all belong to the same distinct value level. One operation can reduce all of them simultaneously. The set contains only {5}, so the algorithm correctly returns 1.

Multiple Distinct Levels With Repetitions

Consider:

nums = [6, 6, 4, 4, 2]
k = 2

The distinct values greater than k are {4, 6}. Each level must be removed exactly once. The algorithm counts two distinct values and returns 2, regardless of how many times each value appears. This correctly captures the effect of the operation, which acts on all occurrences of a value simultaneously.