3066. Minimum Operations to Exceed Threshold Value II

You are given a 0-indexed integer array nums, and an integer k.

In one operation, you will:

• Take the two smallest integers x and y in nums.
• Remove x and y from nums.
• Add min(x, y) * 2 + max(x, y) anywhere 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, there exists some sequence of operations after which all elements of the array are greater than or equal to k.

Approach 01:

#include <queue>
#include <vector>

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

        // Insert all elements into the min-heap
        for (const int num : nums)
            minHeap.push(num);

        // Process elements while the smallest element is less than the target
        while (minHeap.size() > 1 && minHeap.top() < target) {
            int smallest = minHeap.top();
            minHeap.pop();
            int secondSmallest = minHeap.top();
            minHeap.pop();

            // Merge the two smallest elements and push back into the heap
            minHeap.push(std::min(smallest, secondSmallest) * 2L + std::max(smallest, secondSmallest));
            ++operationCount;
        }

        return operationCount;
    }
};

import heapq

class Solution:
    def minOperations(self, nums, target):
        operationCount = 0
        minHeap = []

        # Insert all elements into the min-heap
        for num in nums:
            heapq.heappush(minHeap, num)

        # Process elements while the smallest element is less than the target
        while len(minHeap) > 1 and minHeap[0] < target:
            smallest = heapq.heappop(minHeap)
            secondSmallest = heapq.heappop(minHeap)

            # Merge the two smallest elements and push back into the heap
            heapq.heappush(minHeap, min(smallest, secondSmallest) * 2 + max(smallest, secondSmallest))
            operationCount += 1

        return operationCount

Time Complexity:

• Heap Construction:

  Building a min-heap from \( N \) elements takes \( O(N) \).

• Heap Operations:

  Each merge operation involves two extractions (\( O(\log N) \) each) and one insertion (\( O(\log N) \)).

• Number of Merges:

  In the worst case, we perform \( O(N) \) merge operations.

• Overall Time Complexity:

  \( O(N + N \log N) = O(N \log N) \).

Space Complexity:

• Heap Storage:

  The priority queue stores at most \( N \) elements, leading to \( O(N) \) space usage.

• Auxiliary Variables:

  A few integer variables are used, contributing \( O(1) \) extra space.

• Overall Space Complexity:

  \( O(N) \).