Minimum Operations to Exceed Threshold Value II

medium heap priority queue simulation

Problem

Given an array nums and an integer k, in one operation take the two smallest values x and y, remove them, and insert min(x, y) · 2 + max(x, y). Return the minimum number of operations needed so every element is ≥ k.

Inputnums = [2,11,10,1,3], k = 10

Output2

Combine 1 & 2 → 1·2+2 = 4, giving [4,11,10,3]. Combine 3 & 4 → 3·2+4 = 10, giving [10,11,10]. Now all ≥ 10.

nums (comma-separated)

k (threshold)

import heapq

def minOperations(nums, k):
    heap = nums[:]          # copy the array
    heapq.heapify(heap)     # build a min-heap in O(n)
    ops = 0
    # the smallest value lives at the root
    while heap[0] < k:
        x = heapq.heappop(heap)   # smallest
        y = heapq.heappop(heap)   # second smallest
        heapq.heappush(heap, min(x, y) * 2 + max(x, y))
        ops += 1
    return ops

function minOperations(nums, k) {
  // MinHeap: push, pop, peek; siftUp / siftDown keep order.
  const h = new MinHeap();
  for (const v of nums) h.push(v);
  let ops = 0;
  while (h.peek() < k) {
    const x = h.pop();        // smallest
    const y = h.pop();        // second smallest
    h.push(Math.min(x, y) * 2 + Math.max(x, y));
    ops++;
  }
  return ops;
}

int minOperations(int[] nums, int k) {
    // long because values can grow past int range
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int v : nums) pq.offer((long) v);
    int ops = 0;
    while (pq.peek() < k) {
        long x = pq.poll();          // smallest
        long y = pq.poll();          // second smallest
        pq.offer(Math.min(x, y) * 2 + Math.max(x, y));
        ops++;
    }
    return ops;
}

int minOperations(vector<int>& nums, int k) {
    // long long because values can grow past int range
    priority_queue<long long, vector<long long>, greater<>> pq;
    for (int v : nums) pq.push(v);
    int ops = 0;
    while (pq.top() < k) {
        long long x = pq.top(); pq.pop();   // smallest
        long long y = pq.top(); pq.pop();   // second smallest
        pq.push(min(x, y) * 2 + max(x, y));
        ops++;
    }
    return ops;
}

Explanation

Each operation always consumes the two smallest elements and pushes back a strictly larger value. A min-heap (priority queue) is the perfect structure: its root is always the current minimum, so we can grab the two smallest values in O(log n) each.

The key observation is the stopping condition. The array is "done" exactly when the smallest element is already ≥ k — if the minimum clears the threshold, everything else does too. So we only ever need to peek at the heap root: while heap[0] < k.

On each iteration we pop x (smallest) and y (second smallest), compute the combined value min(x, y) · 2 + max(x, y), push it back, and increment the operation counter. Because the smaller value is doubled, the new element is always larger than both, so the heap shrinks by one each round and the process terminates.

Why is this greedy choice optimal? Combining the two smallest values raises the minimum as cheaply as possible — any other pairing would leave at least one tiny element behind that still needs to be lifted later. Always attacking the current minimum guarantees the fewest operations.

One practical note: combined values can exceed 32-bit range (up to roughly 3 · 10⁹), so Java and C++ use 64-bit integers for the heap to avoid overflow.

Time: O(n log n) Space: O(n)