# Minimum Operations to Make Array Values Equal to K
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-operations-to-make-array-values-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-array-values-equal-to-k
**Data structures:** Array, Hash Table
**Companies:** [Lowe's](https://scaleengineer.com/companies/lowe's)
---
## 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:**

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

# Approaches
## Direct Simulation Approach
This approach directly simulates the process described in the problem. It iteratively finds the largest value in the array that is greater than `k` and performs an operation to reduce it. This is repeated until all values in the array are less than or equal to `k`. While conceptually straightforward, this method is less efficient because it requires multiple passes over the array.
**Time:** O(U * N), where N is the length of `nums` and U is the number of unique elements greater than `k`. In each of the U operations, we scan the array multiple times (to find max, next max, and update), leading to O(N) work per operation. In the worst case, U can be up to N, leading to O(N^2). · **Space:** O(N), where N is the number of elements in `nums`. This is because we create a mutable list to store the current state of the array. If the input array is modified in-place, the space complexity would be O(1).
**Pros:** Directly models the problem statement, which can be easier to reason about initially.; Does not require complex data structures.
**Cons:** Inefficient due to repeated traversals of the array within a loop.; Finding the max and next-max value in each iteration adds significant overhead.; Modifying the array (or a copy) in each step is computationally expensive.
### Explanation
The algorithm begins by checking for an impossible scenario: if any element in `nums` is already smaller than `k`, we can never increase it to `k`, so we return -1. Otherwise, we enter a loop to perform the operations. In each iteration, we find the current maximum value, `max_val`. If this `max_val` is greater than `k`, we must reduce it. To do this, we find the next distinct value smaller than `max_val` in the array to use as our `h`. This choice of `h` guarantees validity because all elements greater than `h` will be identical (they will all be `max_val`). We then increment our operation count and update all instances of `max_val` to `h`. This process continues until the array's maximum value is no longer greater than `k`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int minOperations(int[] nums, int k) {
        for (int num : nums) {
            if (num < k) {
                return -1;
            }
        }

        List<Integer> currentNums = new ArrayList<>();
        for (int num : nums) {
            currentNums.add(num);
        }

        int operations = 0;
        while (true) {
            int maxVal = 0;
            for (int num : currentNums) {
                if (num > maxVal) {
                    maxVal = num;
                }
            }

            if (maxVal <= k) {
                break;
            }

            operations++;

            int h = k;
            int nextMax = 0;
            for (int num : currentNums) {
                if (num < maxVal && num > nextMax) {
                    nextMax = num;
                }
            }
            
            if (nextMax > k) {
                h = nextMax;
            }

            for (int i = 0; i < currentNums.size(); i++) {
                if (currentNums.get(i) == maxVal) {
                    currentNums.set(i, h);
                }
            }
        }

        return operations;
    }
}
```
### Algorithm
- First, perform an initial check: iterate through the array `nums`. If any element `num` is less than `k`, it's impossible to reach the target, so return -1.
- Initialize an `operations` counter to 0.
- Start a loop that continues as long as the maximum value in the array is greater than `k`.
- Inside the loop:
  1. Find the maximum value `max_val` in the current array.
  2. If `max_val` is less than or equal to `k`, the process is complete, so break the loop.
  3. Find the largest value `h` in the array that is strictly less than `max_val`. If no such element exists (meaning all elements greater than `k` are `max_val`), set `h = k`.
  4. Increment the `operations` counter.
  5. Iterate through the array and replace all occurrences of `max_val` with `h`. This simulates one operation.
- After the loop terminates, return the total `operations` count.

## Sorting-Based Approach
A more efficient approach is to sort the array. After sorting, all identical values are grouped together, and all values are ordered. This makes it easy to count the number of unique values greater than `k` by performing a single pass over the sorted array. Each such unique value corresponds to one required operation.
**Time:** O(N log N), where N is the length of `nums`. The sorting step is the dominant factor in the time complexity. The initial check and the final scan are both O(N). · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. For instance, Java's `Arrays.sort()` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
**Pros:** Significantly more efficient than the simulation approach.; The logic is simple and clean after the initial sort.
**Cons:** The O(N log N) time complexity from sorting is not optimal.; Modifies the input array if sorted in-place, which might not be desirable in some contexts.
### Explanation
The logic behind this approach is that each unique value greater than `k` represents a 'level' that must be flattened down to `k`. By sorting the array, we can easily identify these unique levels. The algorithm first handles the base case where any element is less than `k`, returning -1. Then, it sorts `nums`. A single pass from the end of the sorted array is sufficient to count the unique elements greater than `k`. We use a variable to keep track of the most recently seen value to avoid counting duplicates. For every new value we see that is greater than `k`, we increment our operation counter.

```java
import java.util.Arrays;

class Solution {
    public int minOperations(int[] nums, int k) {
        for (int num : nums) {
            if (num < k) {
                return -1;
            }
        }

        Arrays.sort(nums);

        int operations = 0;
        int lastVal = -1;

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] <= k) {
                break;
            }
            if (nums[i] > k && nums[i] != lastVal) {
                operations++;
                lastVal = nums[i];
            }
        }

        return operations;
    }
}
```
### Algorithm
- First, check for the impossibility condition: iterate through `nums` and if any element `num < k`, return -1.
- Sort the `nums` array in non-decreasing order.
- Initialize `operations = 0` and a variable `last_val = -1` to track the last unique value encountered.
- Iterate through the sorted array from right to left (from index `n-1` to `0`).
- For each element `nums[i]`:
  - If `nums[i] <= k`, we can stop. Since the array is sorted, all subsequent elements will also be less than or equal to `k`.
  - If `nums[i] > k` and `nums[i]` is not equal to `last_val`, it means we have found a new, unique value level that needs an operation. Increment `operations` and update `last_val = nums[i]`.
- Return the final `operations` count.

## Optimal Approach with a Frequency Array
The most efficient approach recognizes that the problem is equivalent to counting the number of unique elements in the array that are strictly greater than `k`. Each such unique value requires one operation to be reduced. This can be solved in linear time using a hash set or, even better, a simple boolean array given the small range of values.
**Time:** O(N), where N is the length of `nums`. The algorithm involves two separate, non-nested passes through the array, resulting in linear time complexity. · **Space:** O(C), where C is the range of possible values for `nums[i]`. Given the constraint `nums[i] <= 100`, C is a constant (101), making the space complexity O(1).
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) due to the fixed, small range of input values.; Simple and easy to implement.
**Cons:** Requires extra space for the hash set or frequency array. However, given the problem's constraints, this space is constant and small.
### Explanation
The core insight is that the minimum number of operations is exactly the number of unique values in `nums` that are greater than `k`. Each of these unique value 'levels' must be collapsed one by one until all values are `k`. The algorithm first ensures possibility by checking that no element is less than `k`. Then, it iterates through the array once, using a boolean array `seen` (acting as a frequency map for the small, fixed range of numbers) to keep track of the unique values greater than `k`. For each number `num > k`, if it hasn't been seen before, we increment an operation counter and mark it as seen. The final count is the answer.

```java
class Solution {
    public int minOperations(int[] nums, int k) {
        // First pass: check for impossibility
        for (int num : nums) {
            if (num < k) {
                return -1;
            }
        }

        boolean[] seen = new boolean[101]; // Constraints: 1 <= nums[i] <= 100
        int operations = 0;

        // Second pass: count unique elements greater than k
        for (int num : nums) {
            if (num > k) {
                if (!seen[num]) {
                    operations++;
                    seen[num] = true;
                }
            }
        }

        return operations;
    }
}
```
### Algorithm
- First, iterate through `nums` to check for the impossibility condition. If any `num < k`, return -1.
- Initialize a data structure to keep track of unique numbers. Given the constraint `nums[i] <= 100`, a boolean array `seen` of size 101 is highly efficient. Initialize all its values to `false`.
- Initialize `operations = 0`.
- Iterate through the `nums` array a second time.
- For each `num` in `nums`:
  - If `num > k` and `seen[num]` is `false`, it means this is the first time we are encountering this unique value greater than `k`.
  - In this case, increment `operations` and mark this value as seen by setting `seen[num] = true`.
- Return the total `operations` count.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums, int k) {
    Set<Integer> s = new HashSet<>();
    int mi = 1 << 30;
    for (int x : nums) {
      if (x < k) {
        return -1;
      }
      mi = Math.min(mi, x);
      s.add(x);
    }
    return s.size() - (mi == k ? 1 : 0);
  }
}

```

### JavaScript

```javascript
function minOperations ( nums , k ) { const s = new Set ([ k ]); for ( const x of nums ) { if ( x < k ) return - 1 ; s . add ( x ); } return s . size - 1 ; }
```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int k) {
    unordered_set<int> s;
    int mi = INT_MAX;
    for (int x : nums) {
      if (x < k) {
        return -1;
      }
      mi = min(mi, x);
      s.insert(x);
    }
    return s.size() - (mi == k);
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int: s = set() mi = inf for x in nums: if x < k: return - 1 mi = min(mi, x) s . add(x) return len(s) - int(k == mi)

```