Today’s problem

https://leetcode.com/problems/minimum-operations-to-exceed-threshold-value-ii/description

Intuition

Do what the question ask using heap.

Approach

1. Get the minimum two from the list using heap.
2. Put back value $2 * min(x, y) + max(x, y)$ to the heap.
3. If the value you get is all larger or equal to k, then it is all done.

Complexity

• Time complexity: $O(N\times log(N))$, N is the length of the sequence.

• Space complexity: $O(1)$, by using heapify, there is no external storage.

Code

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