3375. Minimum Operations to Make Array Values Equal to K

EasyArrayHash Table

Problem Description

You are given an integer array nums and an integer k. An integer h is called valid if all values in the array that are strictly greater than h are identical. For example, if nums = [10, 8, 10, 8], a valid integer is h = 9 because all nums[i] > 9 are equal to 10. However, 5 is not a valid integer for this array.

You are allowed to perform the following operation on nums:

Select an integer h that is valid for the current values in nums.
For each index i where nums[i] > h, set nums[i] to h.

The task is to return the minimum number of operations required to make every element in nums equal to k. If it is impossible to make all elements equal to k, return -1.

Intuition

The key insight in solving this problem is to realize that the elements of the array which are greater than k need to be reduced to k. To do this, we need a measure of whether the operation can be performed and how many such operations are necessary.

Initially, we iterate over the array and perform a check:

If any element in the array is less than k, it is impossible to make all elements equal to k, so we should immediately return -1.

During the iteration, we keep track of the minimum number in the array, mi, and populate a set, s, with the unique elements of nums. The idea here is:

If k is greater than or equal to the minimum number of the array and all numbers greater than k are identical after potentially multiple operations, then it is possible to reduce all numbers to k.

The minimum number of operations needed corresponds to the number of unique elements in the array (len(s)), minus one if k is equal to the minimum element (mi) because no reduction operation on k itself is needed.

Solution Approach

To solve the problem, we employ the following approach:

Check for Impossibility: Iterate through the array nums and check if any number is less than k. If such a number is found, it is impossible to make all elements equal to k, and we return -1.
Track Unique Numbers: Use a set s to track unique numbers in the array. This helps us count how many different values we need to potentially adjust.
Determine Minimum Value: As we iterate over nums, also keep track of the minimum number, mi. This helps in determining if k is already covered by the smallest number in the array.
Calculate Operations: Once the iteration is complete, calculate the number of operations needed. The operations are the number of unique elements (len(s)) that need to be adjusted to reach k. Reduce this count by one (len(s) - int(k == mi)) if k is the minimum number, since k doesn't require reduction.

This algorithm primarily uses a single pass through the array to determine feasibility and then calculates the number of different values needing adjustment. The use of a set efficiently helps in keeping track of distinct numbers, ensuring an optimal calculation of necessary operations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Given the array nums = [5, 9, 7, 9] and k = 7, we need to determine the minimum number of operations to make all elements in nums equal to k.

Check for Impossibility: Iterate through the array nums to determine if any element is less than k. In this example, all elements are greater than or equal to k, so it's feasible to make all elements equal to k.
Track Unique Numbers: Create a set s to track unique numbers in nums. As we iterate through nums, the unique numbers we find are {5, 7, 9}.
Determine Minimum Value: During the iteration, also keep track of the minimum number in the array, mi. For nums = [5, 9, 7, 9], the minimum is mi = 5.
Calculate Operations: Finally, calculate the minimum operations needed to make all elements equal to k. The number of unique elements in the set s is 3. Since k is not equal to mi (7 ≠ 5), we don't reduce the operation count. Thus, the number of operations required is len(s) = 3.

However, after careful consideration, notice that elements greater than k (which are 9) need to be reduced to 7 in one operation while numbers already equal to k (or less, that aren't part of an operation due to being non-greater) remain unchanged, resulting in one operation overall.

Therefore, the correct minimal number of operations required in this context is 1.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minOperations(self, nums: List[int], k: int) -> int:
6        # Initialize a set to store unique numbers
7        unique_numbers = set()
8        # Initialize the minimum number as infinity to find the minimum in the list
9        min_number = inf
10      
11        # Iterate over each number in the list
12        for num in nums:
13            # If the number is less than k, it's impossible to have k distinct numbers >= k
14            if num < k:
15                return -1
16            # Update the minimum number if the current number is smaller
17            min_number = min(min_number, num)
18            # Add the current number to the set of unique numbers
19            unique_numbers.add(num)
20      
21        # Calculate the result by getting the count of unique numbers
22        # Subtract 1 only if k is equal to the smallest number found
23        return len(unique_numbers) - int(k == min_number)
24

1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5    public int minOperations(int[] nums, int k) {
6        // Create a new HashSet to track unique elements from the array nums
7        Set<Integer> uniqueElements = new HashSet<>();
8        // Initialize minElement with a large value using bitwise shift
9        int minElement = 1 << 30;
10      
11        // Iterate through each element in the nums array
12        for (int element : nums) {
13            // If an element is less than k, it's not possible to reach k with operations
14            if (element < k) {
15                return -1;
16            }
17            // Update minElement to the smallest value encountered in the array
18            minElement = Math.min(minElement, element);
19            // Add the current element to the set of unique elements
20            uniqueElements.add(element);
21        }
22      
23        // Calculate the number of unique elements needed to reach k
24        // Subtract 1 from the size if the smallest element is exactly k
25        return uniqueElements.size() - (minElement == k ? 1 : 0);
26    }
27}
28

1#include <vector>
2#include <unordered_set>
3#include <climits>
4#include <algorithm>
5
6class Solution {
7public:
8    int minOperations(std::vector<int>& nums, int k) {
9        std::unordered_set<int> unique_elements; // Set to track unique elements
10        int min_value = INT_MAX; // Initialize minimum value to maximum integer value
11
12        // Iterate over each element in the nums vector
13        for (int number : nums) {
14            // If any number is less than k, the operation cannot be completed
15            if (number < k) {
16                return -1; // Return -1 indicating failure
17            }
18
19            // Update the minimum encountered value
20            min_value = std::min(min_value, number);
21          
22            // Insert element into the set to track unique numbers
23            unique_elements.insert(number);
24        }
25
26        // Calculate the result by subtracting 1 if the minimum value equals k
27        return unique_elements.size() - (min_value == k);
28    }
29};
30

1// Function to determine the minimum operations needed
2function minOperations(nums: number[], k: number): number {
3    // Initialize a set to keep track of unique numbers
4    const uniqueNumbers = new Set<number>();
5
6    // Variable to track the minimum number encountered
7    let minimumNumber = Infinity;
8
9    // Iterate over each number in the input array
10    for (const number of nums) {
11        // If any number is less than k, return -1 as it's not possible
12        if (number < k) {
13            return -1;
14        }
15
16        // Add the number to the set of unique numbers
17        uniqueNumbers.add(number);
18
19        // Update the minimum number if the current number is smaller
20        minimumNumber = Math.min(minimumNumber, number);
21    }
22
23    // Calculate size adjustment based on minimum number being equal to k
24    const adjustment = (minimumNumber === k ? 1 : 0);
25
26    // Return the size of the set minus the adjustment
27    return uniqueNumbers.size - adjustment;
28}
29

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the number of elements in the nums list. This is because the code iterates through the entire list once to perform operations such as checking conditions, updating a set, and finding the minimum value.

The space complexity of the code is O(n) in the worst case. This occurs when all elements in nums are unique and need to be added to the set s. The set s will store each unique element, requiring additional space proportional to the number of unique elements.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know