Problem Informations

• Problem Index: 3375
• Problem Link: Minimum Operations to Make Array Values Equal to K
• Topics: Array, Hash Table

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.

For example, if $nums = [10, 8, 10, 8]$, a valid integer is $h = 9$ because all $nums[i] > 9$ are equal to 10, but 5 is not a valid integer.

You are allowed to perform the following operation on nums:

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

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

Example 1:

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

Output: 2

Explanation:

The operations can be performed in order using valid integers 4 and then 2.

Example 2:

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

Output: -1

Explanation:

It is impossible to make all the values equal to 2.

Example 3:

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

Output: 4

Explanation:

The operations can be performed using valid integers in the order 7, 5, 3, and 1.

Constraints:

• $1 \leq nums.length \leq 100 $
• $1 \leq nums[i] \leq 100$
• $1 \leq k \leq 100$

Intuition

The problem aims to transform an array nums into an array where all elements are equal to a given integer k. The transformation is accomplished by allowing us to select a valid integer h iteratively, reducing elements greater than h in nums to the value of h itself. The core challenge is to minimize the number of such operations needed to accomplish this task or to determine that it is impossible if any element in the original array is less than k.

To solve this, the key observation is that any value in nums that is less than k immediately indicates that the transformation is impossible. Beyond this, if all elements are at least k, we can systematically reduce everything above k by iterating through unique values in descending order until every element equals k.

Approach

The solution uses a combination of a set and some simple checks to ensure correctness with minimal operations:

1. Check for Impossibility:
   First, we determine if it is immediately impossible to convert all array elements to k. This happens if the smallest element in nums is less than k. Leveraging the min_element function helps us efficiently find the minimal value, allowing for a quick return of -1 if necessary.

2. Utilize a Set for Unique Values:
   Using a set, we collect all unique elements in nums. Each unique number represents a different potential valid integer h that can aid in reducing elements to k. If nums meets the initial condition of all elements being greater than or equal to k, we know the approach can progress.

3. Calculate the Operations:
   The task, then, simplifies to determining how many unique values are above k. The number of such unique values dictates how many operations are needed to reduce the array to all ks, as each operation can uniformly lower the largest set of elements not yet reduced to k.

4. Adjustment for Initial Equality with k:
   Finally, consider whether the minimum element is already k. If this is the case, one less transformation is required since the base value of k is already achieved without needing further reduction operations.

Through these steps, the algorithm efficiently counts the minimal operations required or confirms that transforming the array is unobtainable. This strategic combination of set logic and conditional checks delivers the solution within defined constraints.

Code

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        // Check if there's any element in 'nums' less than 'k'. 
        // If so, it's impossible to make all elements equal to 'k', return -1.
        if (*min_element(nums.begin(), nums.end()) < k) {
            return -1;
        }

        // Create a set to store unique elements in 'nums'.
        set<int> uniqueElements;
        for (int num : nums) {
            uniqueElements.insert(num);
        }

        // Calculate the number of unique elements above 'k'.
        // We need one operation to make elements equal to 'k', if 'k' is not already the minimum.
        return uniqueElements.size() - 1 + 
               (*min_element(nums.begin(), nums.end()) == k ? 0 : 1);
    }
};

Python

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        # Check if there's any element in 'nums' less than 'k'. 
        # If so, it's impossible to make all elements equal to 'k', return -1.
        if min(nums) < k:
            return -1

        # Create a set to store unique elements in 'nums'.
        uniqueElements = set()
        for num in nums:
            uniqueElements.add(num)

        # Calculate the number of unique elements above 'k'.
        # We need one operation to make elements equal to 'k', if 'k' is not already the minimum.
        return len(uniqueElements) - 1 + (0 if min(nums) == k else 1)

Complexity

• Time complexity: $O(n \log n)$

  The time complexity is primarily driven by the operations on the set and the min_element function. Inserting each element into the set takes $O(\log n)$ time for a single element, and it is done for each of the $n$ elements in the nums array, so this operation takes $O(n \log n)$ in total. The min_element function, used twice, has a time complexity of $O(n)$. Therefore, the overall time complexity is $O(n \log n) + O(n)$, which simplifies to $O(n \log n)$.

• Space complexity: $O(n)$

  The space complexity is determined by the space needed for the set uniqueElements, which can hold up to $n$ unique elements from the nums array. Hence, the space complexity is $O(n)$. Note that additional space is used by iterators and return values when performing operations like min_element, but these are not significant enough to affect the overall space complexity.