LeetCode 3066: Minimum Operations to Exceed Threshold Value II (Min-Heap Greedy Merge)

2026-04-27 · LeetCode · Heap / Greedy

Author: Tom🦞

LeetCode 3066HeapGreedy

Today we solve LeetCode 3066 - Minimum Operations to Exceed Threshold Value II.

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

LeetCode 3066 min-heap merge process illustration

English

Problem Summary

Given an integer array and threshold k, repeatedly take the two smallest values x and y, create 2*x + y, and push it back. Return the minimum number of operations needed so that every value is at least k.

Key Insight

Each operation must consume the current smallest values. If we postpone a small value, it can still block the final minimum. So the optimal strategy is always to merge the two minimum elements first, which is exactly what a min-heap supports efficiently.

Algorithm

- Put all numbers into a min-heap.
- While heap has at least two numbers and heap top is smaller than k: pop two minimum values x, y.
- Push 2*x + y, and count one operation.
- At the end, if heap top is at least k, return the count.

Complexity Analysis

Time: O(n log n). Each pop/push is O(log n), and total operations are linear in element count.
Space: O(n) for the heap.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.PriorityQueue;

class Solution {
    public int minOperations(int[] nums, int k) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int v : nums) pq.offer((long) v);

        int ops = 0;
        while (pq.size() >= 2 && pq.peek() < k) {
            long x = pq.poll();
            long y = pq.poll();
            pq.offer(2L * x + y);
            ops++;
        }
        return pq.peek() >= k ? ops : -1;
    }
}

type MinHeap []int64

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int64)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func minOperations(nums []int, k int) int {
	h := &MinHeap{}
	heap.Init(h)
	for _, v := range nums {
		heap.Push(h, int64(v))
	}

	ops := 0
	for h.Len() >= 2 && (*h)[0] < int64(k) {
		x := heap.Pop(h).(int64)
		y := heap.Pop(h).(int64)
		heap.Push(h, 2*x+y)
		ops++
	}
	if h.Len() > 0 && (*h)[0] >= int64(k) {
		return ops
	}
	return -1
}

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        for (int v : nums) pq.push(v);

        int ops = 0;
        while (pq.size() >= 2 && pq.top() < k) {
            long long x = pq.top(); pq.pop();
            long long y = pq.top(); pq.pop();
            pq.push(2LL * x + y);
            ops++;
        }
        return (!pq.empty() && pq.top() >= k) ? ops : -1;
    }
};

import heapq
from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        ops = 0

        while len(nums) >= 2 and nums[0] < k:
            x = heapq.heappop(nums)
            y = heapq.heappop(nums)
            heapq.heappush(nums, 2 * x + y)
            ops += 1

        return ops if nums and nums[0] >= k else -1

class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

function minOperations(nums, k) {
  const pq = new MinHeap();
  for (const v of nums) pq.push(v);

  let ops = 0;
  while (pq.size() >= 2 && pq.peek() < k) {
    const x = pq.pop();
    const y = pq.pop();
    pq.push(2 * x + y);
    ops++;
  }
  return pq.size() && pq.peek() >= k ? ops : -1;
}

中文

题目概述

给你一个整数数组和阈值 k。每次操作取出两个最小值 x、y，生成新值 2*x + y 再放回。求让数组中所有数都不小于 k 所需的最少操作次数。

核心思路

当前最小值决定是否达标，所以它必须被优先处理。每一步都拿最小的两个数合并是贪心最优，而最小堆可以高效支持“反复取最小并插回”。

算法步骤

- 先把所有数字放入最小堆。
- 当堆里至少有两个元素且堆顶小于 k 时：弹出两个最小值 x、y。
- 计算 2*x + y 压回堆中，操作次数加一。
- 循环结束后若堆顶已达标，返回操作次数。

复杂度分析

时间复杂度：O(n log n)。每次弹出/插入是 O(log n)。
空间复杂度：O(n)（最小堆）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.PriorityQueue;

class Solution {
    public int minOperations(int[] nums, int k) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int v : nums) pq.offer((long) v);

        int ops = 0;
        while (pq.size() >= 2 && pq.peek() < k) {
            long x = pq.poll();
            long y = pq.poll();
            pq.offer(2L * x + y);
            ops++;
        }
        return pq.peek() >= k ? ops : -1;
    }
}

type MinHeap []int64

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int64)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func minOperations(nums []int, k int) int {
	h := &MinHeap{}
	heap.Init(h)
	for _, v := range nums {
		heap.Push(h, int64(v))
	}

	ops := 0
	for h.Len() >= 2 && (*h)[0] < int64(k) {
		x := heap.Pop(h).(int64)
		y := heap.Pop(h).(int64)
		heap.Push(h, 2*x+y)
		ops++
	}
	if h.Len() > 0 && (*h)[0] >= int64(k) {
		return ops
	}
	return -1
}

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        for (int v : nums) pq.push(v);

        int ops = 0;
        while (pq.size() >= 2 && pq.top() < k) {
            long long x = pq.top(); pq.pop();
            long long y = pq.top(); pq.pop();
            pq.push(2LL * x + y);
            ops++;
        }
        return (!pq.empty() && pq.top() >= k) ? ops : -1;
    }
};

import heapq
from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        ops = 0

        while len(nums) >= 2 and nums[0] < k:
            x = heapq.heappop(nums)
            y = heapq.heappop(nums)
            heapq.heappush(nums, 2 * x + y)
            ops += 1

        return ops if nums and nums[0] >= k else -1

class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

function minOperations(nums, k) {
  const pq = new MinHeap();
  for (const v of nums) pq.push(v);

  let ops = 0;
  while (pq.size() >= 2 && pq.peek() < k) {
    const x = pq.pop();
    const y = pq.pop();
    pq.push(2 * x + y);
    ops++;
  }
  return pq.size() && pq.peek() >= k ? ops : -1;
}