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

You are allowed to perform some operations on `nums`, where in a single operation, you can:

* Select the two **smallest** integers `x` and `y` from `nums`.
* Remove `x` and `y` from `nums`.
* Insert `(min(x, y) * 2 + max(x, y))` at any position in the array.

**Note** that you can only apply the described operation if `nums` contains **at least** two elements.

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:** 2

**Explanation:**

1. In the first operation, we remove elements 1 and 2, then add `1 * 2 + 2` to `nums`. `nums` becomes equal to `[4, 11, 10, 3]`.
2. In the second operation, we remove elements 3 and 4, then add `3 * 2 + 4` to `nums`. `nums` becomes equal to `[10, 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 2 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 = 20

**Output:** 4

**Explanation:**

1. After one operation, `nums` becomes equal to `[2, 4, 9, 3]`.
2. After two operations, `nums` becomes equal to `[7, 4, 9]`.
3. After three operations, `nums` becomes equal to `[15, 9]`.
4. After four operations, `nums` becomes equal to `[33]`.

At this stage, all the elements of `nums` are greater than 20 so we can stop. 

It can be shown that 4 is the minimum number of operations needed so that all elements of the array are greater than or equal to 20.

**Constraints:**

* `2 <= nums.length <= 2 * 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= 109`
* The input is generated such that an answer always exists. That is, after performing some number of operations, all elements of the array are greater than or equal to `k`.

# Approaches
## Brute Force with Repeated Sorting
This approach directly simulates the process described in the problem. In each step, we sort the current collection of numbers to identify the two smallest. After finding them, we perform the specified operation, update the collection with the new number, and increment our operation count. We repeat this entire process until the smallest number in our collection meets or exceeds the threshold `k`.
**Time:** O(N^2 log N), where N is the initial number of elements. The loop can run up to N-1 times. In each iteration, we sort a list of size roughly N, which takes O(N log N) time. This leads to a total complexity of O(N * N log N), which is too slow for the given constraints. · **Space:** O(N), where N is the initial number of elements in `nums`. This space is used to store the numbers in a dynamic list.
**Pros:** Conceptually simple and easy to follow.; Direct translation of the problem statement into code.
**Cons:** Extremely inefficient due to repeated sorting.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
To implement this, we can use a dynamic array, such as an `ArrayList` in Java, to store the numbers, as its size will change with each operation. We also need a counter for the number of operations, initialized to zero.

The main logic resides in a loop. In each iteration, we first sort the list. This brings the two smallest elements to the front. We then check if the smallest element (at index 0) is greater than or equal to `k`. If it is, our goal is achieved, and we can stop. Otherwise, we remove the first two elements, calculate the new value using the formula `min(x, y) * 2 + max(x, y)`, add this new value back to the list, and increment our operation counter. The loop continues until the condition is met.

It's important to use a `long` data type for the numbers in the list, as the result of the operation `min * 2 + max` can easily exceed the maximum value of a standard 32-bit integer.

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

class Solution {
    public int minOperations(int[] nums, int k) {
        List<Long> list = new ArrayList<>();
        for (int num : nums) {
            list.add((long) num);
        }

        int operations = 0;
        while (true) {
            Collections.sort(list);
            if (list.isEmpty() || list.get(0) >= k) {
                break;
            }
            if (list.size() < 2) {
                break; // Cannot perform operation
            }
            
            long x = list.remove(0);
            long y = list.remove(0);
            
            long newValue = x * 2 + y;
            list.add(newValue);
            operations++;
        }
        
        return operations;
    }
}
```
### Algorithm
*   Initialize `operations = 0`.
*   Create a `List<Long>` from the input `nums` array to handle potentially large numbers and allow for dynamic resizing.
*   Start a loop that continues as long as the smallest element in the list is less than `k`.
*   Inside the loop:
    1.  Sort the list in non-decreasing order.
    2.  If the list has fewer than two elements or if its smallest element (at index 0) is already `>= k`, break the loop.
    3.  Extract the two smallest elements, `x` from index 0 and `y` from index 1.
    4.  Remove these two elements from the list.
    5.  Calculate the new value: `newValue = x * 2 + y`.
    6.  Add `newValue` back to the list.
    7.  Increment the `operations` counter.
*   Return the final `operations` count.

## Optimized Approach using a Min-Heap (Priority Queue)
A significantly more efficient solution involves using a min-heap, which is perfectly suited for problems that require repeatedly finding and extracting the minimum element from a collection. In Java, this is implemented with the `PriorityQueue` class. By maintaining the numbers in a min-heap, we can access the smallest element in O(1) time and extract it in O(log N) time, which is a massive improvement over the O(N log N) sorting step in the brute-force approach.
**Time:** O(N log N), where N is the number of elements. Initializing the heap by adding N elements one by one takes O(N log N). The `while` loop runs at most N-1 times, and each iteration involves `poll()` and `add()` operations, which take O(log M) time where M is the current heap size (M ≤ N). Thus, the overall time complexity is dominated by these heap operations. · **Space:** O(N), where N is the number of elements in `nums`. This space is required to store all the numbers in the priority queue.
**Pros:** Highly efficient, with a time complexity that passes the problem constraints.; It is the optimal approach for this problem.; The use of a min-heap is a natural fit for the problem's requirement of repeatedly finding the smallest elements.
**Cons:** Requires knowledge of the Priority Queue data structure.; Slightly higher constant factor overhead compared to a simple array, but this is negligible given the asymptotic improvement.
### Explanation
The strategy is to use the greedy approach of always combining the two smallest available numbers. A min-heap makes this strategy highly efficient.

First, we insert all numbers from the input array `nums` into a min-heap. We must use a `PriorityQueue<Long>` to avoid integer overflow when calculating the new values. We also initialize an `operations` counter to zero.

The main logic is a loop that runs as long as the heap's smallest element is less than `k` and there are at least two elements to combine. Inside the loop, we `poll()` the two smallest elements, `x` and `y`. We then compute the new value `x * 2 + y` and `add()` it back to the heap. For each such combination, we increment our operations counter. The heap automatically reorganizes itself to maintain the min-heap property after each insertion.

The loop terminates when the smallest element in the heap is finally greater than or equal to `k`. At this point, we have performed the minimum number of operations required, and we return the count.

```java
import java.util.PriorityQueue;

class Solution {
    public int minOperations(int[] nums, int k) {
        // Use a min-heap to efficiently find the two smallest elements.
        // Use Long to prevent overflow from the operation.
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.add((long) num);
        }

        int operations = 0;
        // Continue as long as there are at least two elements and the smallest
        // element is less than k.
        while (pq.size() >= 2 && pq.peek() < k) {
            // Get the two smallest elements
            long x = pq.poll();
            long y = pq.poll();

            // Perform the operation and add the new element back to the heap
            // Since x was polled first, x <= y, so this is min*2 + max.
            long newValue = x * 2 + y;
            pq.add(newValue);
            
            // Increment the operation count
            operations++;
        }

        return operations;
    }
}
```
### Algorithm
*   Initialize `operations = 0`.
*   Create a min-heap (a `PriorityQueue<Long>` in Java) and populate it with all elements from the `nums` array. Using `long` prevents potential integer overflow.
*   Start a `while` loop that continues as long as the heap contains at least two elements and the smallest element (retrieved via `peek()`) is less than `k`.
*   Inside the loop:
    1.  Extract the two smallest elements, `x` and `y`, by calling `poll()` twice.
    2.  Calculate the new value: `newValue = x * 2 + y`. Since `x` is guaranteed to be the smaller of the two, this is equivalent to `min(x, y) * 2 + max(x, y)`.
    3.  Add `newValue` back into the heap using `add()`.
    4.  Increment the `operations` counter.
*   Once the loop terminates, return the total `operations` count.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums, int k) {
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int x : nums) {
      pq.offer((long)x);
    }
    int ans = 0;
    for (; pq.size() > 1 && pq.peek() < k; ++ans) {
      long x = pq.poll(), y = pq.poll();
      pq.offer(Math.min(x, y) * 2 + Math.max(x, y));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int k) {
    using ll = long long;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int x : nums) {
      pq.push(x);
    }
    int ans = 0;
    for (; pq.size() > 1 && pq.top() < k; ++ans) {
      ll x = pq.top();
      pq.pop();
      ll y = pq.top();
      pq.pop();
      pq.push(min(x, y) * 2 + max(x, y));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int: heapify(nums) ans = 0 while len(nums) > 1 and nums[0] < k: x, y = heappop(nums), heappop(nums) heappush(nums, min(x, y) * 2 + max(x, y)) ans += 1 return ans

```