Minimum Operations to Exceed Threshold Value II — Medium Problem & Solution

Problem statement

In one operation you take the two smallest values x and y in nums, remove both, and add min(x, y) * 2 + max(x, y) back.

Return the minimum number of operations needed until every value in nums is at least k. The input guarantees this is reachable.

Example 1

Input: nums = [2,11,10,1,3], k = 10
Output: 2
Explanation: `1,2` become 4; then `3,4` become 10, leaving `[10,10,11]`.

Example 2

Input: nums = [1,1,2,4,9], k = 20
Output: 4
Explanation: Four merges take the array to `[33]`.

Example 3

Input: nums = [1,2], k = 3
Output: 1
Explanation: One merge gives 4.

Constraints

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 10^5
• 1 <= k <= 10^5
• The input is generated such that an answer always exists.

How to solve Minimum Operations to Exceed Threshold Value II

Greedily merge the two smallest values with a min-heap, counting operations until the heap's smallest value reaches k.

Approach

1. Heapify nums as a min-heap.
2. While the root is below k, pop twice, push 2 * min + max, and count the operation.
3. Return the count.

Why it works

The two smallest are always the right pair to merge: any value below k must eventually be consumed, and consuming it alongside the next-smallest is the cheapest way to lift it, since the result grows with whatever it is paired against. Checking only the root is enough — a heap's minimum reaching k means every element has.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• min(x, y) * 2 + max(x, y) is not symmetric — doubling the larger value gives a different, wrong result.
• The merged value goes back into the heap and can be merged again.
• Re-sorting the whole array after each merge is O(n² log n) and needlessly slow.

Reference solution

Python

import heapq
from typing import List

def minOperations(nums: List[int], k: int) -> int:
    heap = nums[:]
    heapq.heapify(heap)
    ops = 0
    while len(heap) > 1 and heap[0] < k:
        x = heapq.heappop(heap)
        y = heapq.heappop(heap)
        heapq.heappush(heap, x * 2 + y)
        ops += 1
    return ops

JavaScript

var minOperations = function(nums, k) {
    var heap = nums.slice();
    var sift = function(j) {
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < heap.length && heap[l] < heap[s]) s = l;
            if (r < heap.length && heap[r] < heap[s]) s = r;
            if (s === j) break;
            var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
            j = s;
        }
    };
    var push = function(v) {
        heap.push(v);
        var i = heap.length - 1;
        while (i > 0) {
            var p = (i - 1) >> 1;
            if (heap[p] <= heap[i]) break;
            var t = heap[p]; heap[p] = heap[i]; heap[i] = t;
            i = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) { heap[0] = last; sift(0); }
        return top;
    };
    for (var i = Math.floor(heap.length / 2) - 1; i >= 0; i--) sift(i);
    var ops = 0;
    while (heap.length > 1 && heap[0] < k) {
        var x = pop(), y = pop();
        push(x * 2 + y);
        ops++;
    }
    return ops;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium