Skip to main content
Talentd

Minimum Operations to Exceed Threshold Value II - Solution & Explanation

MediumArrayHeap (Priority Queue)Simulation15 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums, and an integer k.

In one operation, you will:

  • Take the two smallest integers x and y in nums.
  • Remove x and y from nums.
  • Add min(x, y) * 2 + max(x, y) anywhere in the array.

Note that you can only apply the described operation if nums contains at least two elements.

Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.

 

Example 1:

Input: nums = [2,11,10,1,3], k = 10
Output: 2
Explanation: In the first operation, we remove elements 1 and 2, then add 1 * 2 + 2 to nums. nums becomes equal to [4, 11, 10, 3].
In the second operation, we remove elements 3 and 4, then add 3 * 2 + 4 to nums. nums becomes equal to [10, 11, 10].
At this stage, all the elements of nums are greater than or equal to 10 so we can stop.
It can be shown that 2 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.

Example 2:

Input: nums = [1,1,2,4,9], k = 20
Output: 4
Explanation: After one operation, nums becomes equal to [2, 4, 9, 3].
After two operations, nums becomes equal to [7, 4, 9].
After three operations, nums becomes equal to [15, 9].
After four operations, nums becomes equal to [33].
At this stage, all the elements of nums are greater than 20 so we can stop.
It can be shown that 4 is the minimum number of operations needed so that all elements of the array are greater than or equal to 20.

 

Constraints:

  • 2 <= nums.length <= 2 * 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109
  • The input is generated such that an answer always exists. That is, there exists some sequence of operations after which all elements of the array are greater than or equal to k.

Approach Overview

Problem Overview: You are given an array of integers and a threshold k. In one operation, take the two smallest values a and b, create a new value a * 2 + b, and insert it back into the structure. The goal is to make every value in the array at least k using the minimum number of operations.

Approach 1: Use a Min-Heap to Combine Numbers (Time: O(n log n), Space: O(n))

This problem naturally fits a heap (priority queue). Always combining the two smallest numbers produces the smallest possible new value, which keeps future operations flexible and minimizes the number of steps. Push all elements into a min-heap, repeatedly pop the two smallest values, compute a * 2 + b, and push the result back. Continue until the smallest element in the heap is at least k or the heap no longer has enough elements to combine.

The heap guarantees that each extraction of the smallest element runs in O(log n). Since each operation reduces the number of elements by one, the loop runs at most n times. This makes the overall complexity O(n log n). This approach is reliable, easy to implement, and directly models the problem's requirement to repeatedly access the smallest elements.

Approach 2: Greedy Strategy without Heap (Time: O(n log n), Space: O(n))

A heap is convenient but not strictly required. You can sort the initial array and simulate the merging process using two streams: one for unused original numbers and one for newly created values. Both streams stay sorted because every new value a * 2 + b is at least as large as the inputs used to create it. Each step picks the two smallest candidates from the fronts of these streams, similar to a merge process.

This approach relies on a greedy observation: combining the smallest available values always leads to the optimal sequence of operations. The initial sort costs O(n log n), and the simulation runs in linear time by advancing pointers through the arrays. In practice, this avoids the repeated heap push/pop operations while preserving the same logical behavior.

Recommended for interviews: The min-heap solution is the expected answer. Interviewers want to see that you immediately recognize the pattern of repeatedly extracting the smallest values and reach for a priority queue. Explaining the greedy reasoning first shows problem understanding, and implementing it with a heap demonstrates strong command of standard interview data structures.

Approach 1: Approach 1: Use a Min-Heap to Combine Numbers

This approach makes use of a min-heap to efficiently find and combine the smallest two elements in the array. By replacing these elements with their transformed value (according to the operation rules) and repeating the process, we can gradually increase the array's elements until all meet the threshold of k.

This Python solution uses the heapq module to handle the heap operations. We continue to extract two smallest elements, combine them, and push the result back into the heap. This continues until the smallest element is no longer less than k.

Code

PythonJavaC++JavaScriptC#

Python

Java

C++

JavaScript

C#

Complexity

Time Complexity: O(n log n), where n is the length of the input list because each heap operation (insertion/deletion) takes O(log n) and we do it potentially up to the whole list.
Space Complexity: O(n), used to store the heap.

Try this approach in the editor →

Approach 2: Approach 2: Greedy Strategy without Heap

For this approach, we can sort the array first and then simulate the operations directly on the list. This leverages a greedy strategy of always combining the smallest elements first to reach the target faster. Note that this approach may not be as optimal as the heap method in terms of complexity, but provides a straightforward way to visualize the problem.

This Python solution sorts the array first, then pops the two smallest elements each iteration to handle the combination operation, and then re-sorts the array if necessary.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n2 log n) in the worst case due to repeated sorting.
Space Complexity: O(1) additional space ignoring input array space.

Try this approach in the editor →

Approach 3: Priority Queue (Min Heap)

We can use a priority queue (min heap) to simulate this process.

Specifically, we first add the elements in the array to the priority queue pq. Then we continuously take out the two smallest elements x and y from the priority queue, and put min(x, y) * 2 + max(x, y) back into the priority queue. After each operation, we increase the operation count by one. We stop the operation when the number of elements in the queue is less than 2 or the smallest element in the queue is greater than or equal to k.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Use a Min-Heap to Combine Numbers

Time Complexity: O(n log n), where n is the length of the input list because each heap operation (insertion/deletion) takes O(log n) and we do it potentially up to the whole list.
Space Complexity: O(n), used to store the heap.

Approach 2: Greedy Strategy without Heap

Time Complexity: O(n2 log n) in the worst case due to repeated sorting.
Space Complexity: O(1) additional space ignoring input array space.

Priority Queue (Min Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap CombinationO(n log n)O(n)General case. Best when repeatedly accessing the two smallest values.
Greedy Two-Stream Simulation (No Heap)O(n log n)O(n)Useful when avoiding heap operations or when implementing a pointer-based simulation after sorting.

Video Solution

Minimum Operations to Exceed Threshold Value II |Easy Explanation | Leetcode 3066 | codestorywithMIK • codestorywithMIK • 6,646 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Exceed Threshold Value II easy or hard?
The problem is rated Medium on LeetCode. The challenge is recognizing the greedy pattern and choosing a priority queue to efficiently access the smallest values. Once the heap approach is identified, the implementation is relatively straightforward.
Minimum Operations to Exceed Threshold Value II Python/Java solution
Python solutions typically use heapq to maintain a min-heap, while Java implementations use PriorityQueue. Both follow the same logic: push all numbers into the heap, repeatedly pop the two smallest, compute a * 2 + b, push the result, and count operations until the smallest value reaches k.
How to solve Minimum Operations to Exceed Threshold Value II in O(n)?
A near-linear simulation can be built after sorting the array. Maintain two sorted streams: remaining original values and newly created values. At each step, pick the two smallest candidates from the stream fronts and generate the combined value. The simulation itself is O(n), though the initial sorting step still costs O(n log n).
What is the best approach for Minimum Operations to Exceed Threshold Value II?
The optimal approach uses a min-heap (priority queue). Insert all numbers into the heap, repeatedly extract the two smallest values, combine them using a * 2 + b, and push the result back. Continue until the smallest value is at least k. This approach runs in O(n log n) time because each heap insertion and removal costs O(log n).
Is Minimum Operations to Exceed Threshold Value II asked at Google/Amazon/Meta?
Problems involving repeated extraction of the smallest values with heaps are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem resemble the classic "Jesse and Cookies" or "combine smallest elements" heap problems frequently used to test priority queue knowledge.
What data structure is used in Minimum Operations to Exceed Threshold Value II?
The key data structure is a min-heap (priority queue). It allows efficient retrieval of the two smallest numbers in O(log n) time per operation. The heap ensures that each combination always uses the smallest available values, which is required for the greedy strategy to work correctly.
What is the time complexity of Minimum Operations to Exceed Threshold Value II?
The standard solution runs in O(n log n) time and O(n) space. Building the heap takes O(n), and each operation involves two heap pops and one push, each costing O(log n). Since at most n operations occur, the overall complexity becomes O(n log n).

Ready to solve this problem?

Practice Minimum Operations to Exceed Threshold Value II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Halve Array Sum