Problem

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.

Examples

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 * 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • 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.

Solution

Method 1 - Using the minheap

The problem involves performing a series of operations on a list of integers to ensure that all its elements are greater or equal to k. The operation involves merging the two smallest numbers according to a specific formula. This is a variant of the “smallest element merging problem”, which often requires efficient selection of the smallest elements. A good strategy for this is to use a min-heap.

  1. Min-Heap for Efficiency:
    • Use a min-heap (also known as a priority queue) to keep track of the smallest elements efficiently. A min-heap allows us to extract the smallest elements in O(log n) time.
    • Build a min-heap from the input array nums in O(n) time.
  2. Iterative Combination:
    • Repeatedly extract the two smallest elements from the heap.
    • Combine them into a new number using the formula: result = min(x, y) * 2 + max(x, y)
  3. Stopping Condition:
    • Continue performing the operation until:
      • The heap has fewer than two elements, OR
      • All elements in the heap are greater than or equal to k.
  4. Edge Cases:
    • If all elements are already greater than or equal to k initially, no operations are needed.
    • If it is impossible to make all elements >= k (e.g., starting with one element less than k), return -1.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution {
    public int minOperations(int[] nums, int k) {
        // Create a min-heap
        PriorityQueue<Long> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.add((long)num);
        }

        int ops = 0;
        while (heap.size() > 1) {
            long x = heap.poll();
            if (x >= k) {
                return ops;
            }

            long y = heap.poll();
            // Perform the operation
            long combined = x * 2 + y;
            heap.add(combined);
            ops++;
        }

        // Check if the last element is >= k
        return heap.peek() >= k ? ops : -1;
    }
}
Python
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        # Convert array into a heap
        heapify(nums)
        ops: int = 0
        
        while len(nums) > 1:
            # Get the two smallest elements
            x: int = heappop(nums)
            if x >= k:
                return ops
            
            y: int = heappop(nums)
            # Perform the operation
            combined: int = x * 2 + y
            # Insert the combined value back
            heappush(nums, combined)
            ops += 1

        # Check if the last element is >= k
        return ops if nums[0] >= k else -1

Complexity

  • ⏰ Time complexity: O(n log n). Extracting the smallest elements and inserting back into the heap takes O(log n) time. In the worst case, we may perform O(n) operations.
  • 🧺 Space complexity: O(n) as the heap requires O(n) additional space.