We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Exceed Threshold Value II

Number: 3332

Difficulty: Medium

Paid? No

Companies: Meta, Google, tcs

Problem Description

We are given a 0-indexed integer array nums and an integer k, and we can perform the following operation: select the two smallest integers x and y from nums, remove them, then insert the element (min(x, y) * 2 + max(x, y)) into nums. The goal is to determine the minimum number of operations required so that every element in the array is greater than or equal to k.

Key Insights

  • Use a min-heap to always extract the two smallest elements efficiently.
  • The operation uses the two smallest values to generate a value that is guaranteed to be at least as large as both, thus moving the array values towards meeting the threshold.
  • Continue combining the two smallest numbers until the smallest number in the heap is at least k.
  • Problem constraints guarantee that a solution exists.

Space and Time Complexity

Time Complexity: O(n log n), where n is the length of the array, due to heap operations performed until all elements meet the condition. Space Complexity: O(n) for storing the heap.

Solution

We initialize a min-heap with all the elements of the nums array. Then, while the smallest element in the heap is less than k, we remove the two smallest elements, compute the new element using the formula new = (smallest * 2 + next_smallest), and insert it back into the heap. We count each operation, and once the smallest element is at least k, we return the count of operations.

Code Solutions

import heapq

def minOperations(nums, k):
    # Create a min-heap from the nums array.
    heapq.heapify(nums)
    operations = 0
    
    # Process the heap until the smallest element reaches at least k.
    while len(nums) > 1 and nums[0] < k:
        # Pop the two smallest elements.
        x = heapq.heappop(nums)
        y = heapq.heappop(nums)
        
        # New value is computed as (min(x, y) * 2 + max(x, y)), here x is already the smallest.
        new_value = x * 2 + y
        heapq.heappush(nums, new_value)
        
        operations += 1
    
    # If the smallest element meets the condition, return the operation count.
    return operations if nums[0] >= k else -1

# Example usage:
print(minOperations([2, 11, 10, 1, 3], 10))
print(minOperations([1, 1, 2, 4, 9], 20))
← Back to All Questions