# Minimum Operations to Exceed Threshold Value I
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-operations-to-exceed-threshold-value-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-exceed-threshold-value-i
**Data structures:** Array
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
You are given a **0-indexed** integer array `nums`, and an integer `k`.

In one operation, you can remove one occurrence of the smallest element of `nums`.

Return _the **minimum** number of operations needed so that all elements of the array are greater than or equal to_ `k`.

**Example 1:**

**Input:** nums = [2,11,10,1,3], k = 10
**Output:** 3
**Explanation:** After one operation, nums becomes equal to [2, 11, 10, 3].
After two operations, nums becomes equal to [11, 10, 3].
After three operations, nums becomes equal to [11, 10].
At this stage, all the elements of nums are greater than or equal to 10 so we can stop.
It can be shown that 3 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.

**Example 2:**

**Input:** nums = [1,1,2,4,9], k = 1
**Output:** 0
**Explanation:** All elements of the array are greater than or equal to 1 so we do not need to apply any operations on nums.

**Example 3:**

**Input:** nums = [1,1,2,4,9], k = 9
**Output:** 4
**Explanation:** only a single element of nums is greater than or equal to 9 so we need to apply the operations 4 times on nums.

**Constraints:**

* `1 <= nums.length <= 50`
* `1 <= nums[i] <= 109`
* `1 <= k <= 109`
* The input is generated such that there is at least one index `i` such that `nums[i] >= k`.

# Approaches
## Sorting and Counting
This approach involves first sorting the array. The problem states that we remove the smallest element in each operation. To ensure all remaining elements are at least `k`, we must remove every element that is smaller than `k`. By sorting the array, we conveniently group all these elements at the beginning. We can then simply iterate through the sorted array and count how many elements are less than `k`. This count will be our answer.
**Time:** O(N log N) · **Space:** O(log N) or O(N)
**Pros:** The logic is straightforward and directly models the process of removing the smallest elements first.; It is a correct and reliable way to solve the problem.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than a linear scan.; It modifies the input array (or requires extra space for a copy), which might not be desirable in some contexts.
### Explanation
The algorithm begins by sorting the `nums` array using a standard sorting algorithm, which typically has a time complexity of `O(N log N)`. Once sorted, all elements less than `k` will appear before any elements greater than or equal to `k`. We can then perform a single pass over this sorted array. We initialize a counter for the operations. As we iterate, we check if the current element is less than `k`. If it is, we increment our operations counter. The moment we find an element that is `k` or larger, we can immediately stop because all following elements will also be greater than or equal to `k` due to the sorted nature of the array. The final value of the counter is the minimum number of operations required.

```java
import java.util.Arrays;

class Solution {
    public int minOperations(int[] nums, int k) {
        // Sort the array in ascending order
        Arrays.sort(nums);
        
        int operations = 0;
        // Iterate through the sorted array
        for (int num : nums) {
            if (num < k) {
                // This element must be removed
                operations++;
            } else {
                // Since the array is sorted, all subsequent elements are >= k
                break;
            }
        }
        
        return operations;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize a counter, `operations`, to zero.
- Iterate through the sorted array from the beginning.
- For each element, if it is less than `k`, increment the `operations` counter.
- If an element is greater than or equal to `k`, stop the iteration, as all subsequent elements will also meet the condition.
- Return the final count of `operations`.

## Single Pass Linear Scan
This is the most efficient approach. It correctly deduces that the problem is not about simulating the removal process but simply about counting how many elements need to be removed. To satisfy the condition that all elements are greater than or equal to `k`, we must remove every single element that is less than `k`. The number of such elements is precisely the number of operations needed, regardless of the order in which they are removed. Therefore, a single pass through the array to count these elements is sufficient.
**Time:** O(N) · **Space:** O(1)
**Pros:** Achieves optimal time complexity of O(N).; Uses constant extra space, making it memory efficient.; The implementation is extremely simple and concise.
**Cons:** This approach might seem too simple and overlooks the 'remove the smallest element' part of the problem description, but it correctly identifies the core requirement.
### Explanation
The key insight for this optimal solution is that the step-by-step removal of the smallest element is a distraction. The final state requires no elements less than `k` to be present. This means every element that is initially less than `k` must be removed. The number of operations is therefore simply the count of elements in the original array that are less than `k`. The algorithm implements this directly: it initializes a counter to zero, iterates through the `nums` array once, and for each number, it increments the counter if the number is less than `k`. This avoids any sorting or modification of the array, leading to a linear time complexity and constant space complexity.

```java
class Solution {
    public int minOperations(int[] nums, int k) {
        int operations = 0;
        // Iterate through each number in the array
        for (int num : nums) {
            // If the number is less than k, it needs to be removed
            if (num < k) {
                operations++;
            }
        }
        return operations;
    }
}
```
### Algorithm
- Initialize a counter variable, `operations`, to 0.
- Iterate through each element `num` in the input array `nums`.
- For each `num`, check if it is less than the threshold `k`.
- If `num < k`, increment the `operations` counter.
- After iterating through all the elements, return the total `operations` count.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums, int k) {
    int ans = 0;
    for (int x : nums) {
      if (x < k) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int k) {
    int ans = 0;
    for (int x : nums) {
      if (x < k) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(
        self, nums: List[int], k: int) -> int: return sum(x < k for x in nums)

```