You are given a 0-indexed integer array nums, and an integer k.
In one operation, you will:
x and y in nums.x and y from nums.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 * 1051 <= nums[i] <= 1091 <= k <= 109k.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.
Java
C++
JavaScript
C#
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.
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.
C++
Time Complexity: O(n2 log n) in the worst case due to repeated sorting.
Space Complexity: O(1) additional space ignoring input array space.
| Approach | Complexity |
|---|---|
| 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. |
| Approach 2: Greedy Strategy without Heap | Time Complexity: O(n2 log n) in the worst case due to repeated sorting. |
Minimum Operations to Exceed Threshold Value II | Leetcode 3066 • Techdose • 3,650 views views
Watch 9 more video solutions →Practice Minimum Operations to Exceed Threshold Value II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor