3066. Minimum Operations to Exceed Threshold Value II

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/minimum-operations-to-exceed-threshold-value-ii
• topics: Heap

Description

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.

Idea

• Heap

Code

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