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 <= 10001 <= nums[i] <= 10^51 <= k <= 10^5The input is generated such that an answer always exists.
Hints for Minimum Operations to Exceed Threshold Value II
Hint 1
You never gain by merging anything other than the two smallest values.
Hint 2
A min-heap gives you both in O(log n) and puts the result back just as cheaply.
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
- Heapify
numsas a min-heap. - While the root is below
k, pop twice, push2 * min + max, and count the operation. - 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 opsJava
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