Minimum Operations to Exceed Threshold Value II

Medium
1008.

Minimum Operations to Exceed Threshold Value II

MediumArrayHeap (Priority Queue)SimulationAmazonGoogleFlipkart

Minimum Operations to Exceed Threshold Value II is a medium coding problem on arrays, simulation and heap, asked in Amazon, Google and Flipkart interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Exceed Threshold Value II — Solution

Minimum Operations to Exceed Threshold Value II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Exceed Threshold Value II is a medium coding problem on arrays, simulation and heap, asked in Amazon, Google and Flipkart interviews.

  • Difficulty: Medium
  • Topics: Arrays, Simulation, Heap
  • Asked at: Amazon, Google, Flipkart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Minimum Operations to Exceed Threshold Value II

  1. Hint 1

    You never gain by merging anything other than the two smallest values.

  2. Hint 2

    A min-heap gives you both in O(log n) and puts the result back just as cheaply.

  3. Hint 3

    Stop as soon as the heap's minimum reaches k — everything else is already at least that.

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

Java

public static int minOperations(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int v : nums) heap.add(v);
    int ops = 0;
    while (heap.size() > 1 && heap.peek() < k) {
        int x = heap.poll();
        int y = heap.poll();
        heap.add(x * 2 + y);
        ops++;
    }
    return ops;
}

C++

int minOperations(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap(nums.begin(), nums.end());
    int ops = 0;
    while ((int) heap.size() > 1 && heap.top() < k) {
        int x = heap.top(); heap.pop();
        int y = heap.top(); heap.pop();
        heap.push(x * 2 + y);
        ops++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Heaps and Priority Queues