Problem

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:

1
2
3
4

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:

1
2
3
4

Input: nums = [2,1,2], k = 2
Output: -1
Explanation:
It is impossible to make all the values equal to 2.

Example 3:

1
2
3
4
5

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 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

Examples

Solution

Method 1 - Using Set

The problem involves transforming an array so all elements equal the target k. Here’s the merged explanation:

  1. Early Feasibility Check: If k is greater than the smallest number in the array, transforming the array into k is impossible. We return -1 immediately to avoid further computations.
  2. Unique Elements Count: Each unique number in the array corresponds to a potential operation required to transform values into k. Using a set, we count unique values in the array.
  3. Optimised Operations: If k is among these unique values, one operation is saved because no transformation is needed for k. Otherwise, the total required operations will match the count of unique values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {

    public int minOperations(int[] nums, int k) {
        int minValue = Integer.MAX_VALUE;
        for (int num : nums) { // Find the smallest value in nums.
            minValue = Math.min(minValue, num);
        }

        if (k > minValue) { // If smallest value is less than k, return -1.
            return -1;
        }

        Set<Integer> uniqueNumbers = new HashSet<>(); // Create a set of unique values.
        for (int num : nums) {
            uniqueNumbers.add(num);
        }

        int uniqueCount = uniqueNumbers.size(); // Count how many unique values exist.

        return uniqueNumbers.contains(k) ? uniqueCount - 1 : uniqueCount; // Save operation if `k` exists.
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minOperations(self, nums, k):
        if k > min(nums):  # If smallest number is smaller than k, return -1.
            return -1

        unique_count = len(set(nums))  # Count unique values in nums.

        return unique_count - 1 if k in set(nums) else unique_count  # Save operation if `k` exists.

Complexity

  • ⏰ Time complexity: O(n). For finding the minimum value and creating a set of unique elements.
  • 🧺 Space complexity: O(n) in the worst case, all the elements in array can be unique.