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 Make Array Values Equal to K

Number: 3621

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and an integer k, you want to make every element in nums equal to k by repeatedly performing the following operation:

  1. Choose an integer h that is valid for the current nums. An integer h is valid if all numbers strictly greater than h in nums are identical.
  2. For every index i where nums[i] > h, set nums[i] = h. Return the minimum number of operations required to make every element equal to k. If it is impossible, return -1.

Key Insights

  • If any element in nums is less than k then it is impossible to reach k because the operations can only decrease values.
  • The operations work by “merging” higher numbers into a lower common value. In an optimal strategy, the operations will reduce the distinct values (that are above k) one by one.
  • The minimum number of operations equals the number of distinct values in nums that are strictly greater than k.

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums (we scan the array to check for validity and collect distinct values). Space Complexity: O(n) in the worst case (to store the distinct values that are > k).

Solution

The idea is to first ensure that every element in nums is at least k. If not, return -1 since increasing a number is not allowed. Next, notice that in any valid operation, you can only "lower" numbers that are currently above some threshold h. It turns out that an optimal series of operations will reduce the distinct values that are strictly greater than k one by one until all numbers become k. Hence, the answer is simply the count of distinct numbers in nums that are greater than k.

Data structures used:

  • A set to collect distinct values greater than k.

Algorithmic steps:

  1. Traverse nums and check if any element is less than k; if found, return -1.
  2. Build a set containing all elements x where x > k.
  3. The size of this set (number of distinct values > k) is the minimum number of operations needed.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to get the minimum number of operations
def minOperations(nums, k):
    # Check if there is any element that is less than k.
    for num in nums:
        if num < k:
            return -1  # impossible if any element is smaller than k

    # Use a set to collect distinct elements greater than k
    distinct_greater = set()
    for num in nums:
        if num > k:
            distinct_greater.add(num)
    
    # The number of operations required equals the number of distinct elements greater than k.
    return len(distinct_greater)

# Example usage:
print(minOperations([5,2,5,4,5], 2))  # Expected output: 2
← Back to All Questions