3066. Minimum Operations to Exceed Threshold Value II LeetCode Solution

In this guide, you will get 3066. Minimum Operations to Exceed Threshold Value II LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Exceed Threshold Value II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Operations to Exceed Threshold Value II solution in C++
4. Minimum Operations to Exceed Threshold Value II solution in Java
5. Minimum Operations to Exceed Threshold Value II solution in Python
6. Additional Resources

Problem Statement of Minimum Operations to Exceed Threshold Value II

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:

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].
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:

After one operation, nums becomes equal to [2, 4, 9, 3].
After two operations, nums becomes equal to [7, 4, 9].
After three operations, nums becomes equal to [15, 9].
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.

Complexity Analysis

• Time Complexity: O(n\log n)
• Space Complexity: O(n)

3066. Minimum Operations to Exceed Threshold Value II LeetCode Solution in C++

class Solution {
 public:
  int minOperations(vector<int>& nums, int k) {
    int ans = 0;
    priority_queue<long, vector<long>, greater<>> minHeap;

    for (const int num : nums)
      minHeap.push(num);

    while (minHeap.size() > 1 && minHeap.top() < k) {
      const int x = minHeap.top();
      minHeap.pop();
      const int y = minHeap.top();
      minHeap.pop();
      minHeap.push(min(x, y) * 2L + max(x, y));
      ++ans;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3066. Minimum Operations to Exceed Threshold Value II LeetCode Solution in Java

class Solution {
  public int minOperations(int[] nums, int k) {
    int ans = 0;
    Queue<Long> minHeap = new PriorityQueue<>();

    for (final int num : nums)
      minHeap.add((long) num);

    while (minHeap.size() > 1 && minHeap.peek() < k) {
      final long x = minHeap.poll();
      final long y = minHeap.poll();
      minHeap.add(Math.min(x, y) * 2 + Math.max(x, y));
      ++ans;
    }

    return ans;
  }
}
// code provided by PROGIEZ

3066. Minimum Operations to Exceed Threshold Value II LeetCode Solution in Python

class Solution:
  def minOperations(self, nums: list[int], k: int) -> int:
    ans = 0
    minHeap = nums.copy()
    heapq.heapify(minHeap)

    while len(minHeap) > 1 and minHeap[0] < k:
      x = heapq.heappop(minHeap)
      y = heapq.heappop(minHeap)
      heapq.heappush(minHeap, min(x, y) * 2 + max(x, y))
      ans += 1

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.