3066. Minimum Operations to Exceed Threshold Value II

MediumView on LeetCode

Array Greedy Heap (Priority Queue)

Time: O(n log n)

Space: O(n)

Intuition

Minimum operations to exceed threshold k. Each op: remove two smallest, add their sum+min back. Use min-heap.

Algorithm

1Min-heap. While min < k: pop two smallest a,b. Push min(a,b)*2+max(a,b). Count ops.

Common Pitfalls

•Heap operation is pop two, push one. Continue until minimum element >= k.

3066.cs

// Approach: Min-heap; repeatedly pop two smallest, combine as 2*min+max, push back until all ≥ k.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public int MinOperations(int[] nums, int k)
    {
        int n = nums.Length;
        PriorityQueue<long, long> pq = new PriorityQueue<long, long>(new CustomComparer());
        for (int i = 0; i < nums.Length; i++)
            pq.Enqueue(nums[i], nums[i]);

        int cnt = 0;
        while (pq.Count >= 2 && pq.Peek() < k)
        {
            long val1 = pq.Dequeue();
            long val2 = pq.Dequeue();
            long newVal = Math.Min(val1, val2) * 2 + Math.Max(val1, val2);
            pq.Enqueue(newVal, newVal);
            cnt++;
        }

        return cnt;
    }
}

public class CustomComparer : IComparer<long>
{
    public int Compare(long x, long y)
    {
        return x.CompareTo(y);
    }
}

Was this solution helpful?