3375. Minimum Operations to Make Array Values Equal to K - Solution

The problem

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, but 5 is not a valid integer.

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.

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.

Example 1:

Input: nums = [5,2,5,4,5], k = 2

Output: 2

Explanation:

The operations can be performed in order using valid integers 4 and then 2.

Example 2:

Input: nums = [2,1,2], k = 2

Output: -1

Explanation:

It is impossible to make all the values equal to 2.

Example 3:

Input: nums = [9,7,5,3], k = 1

Output: 4

Explanation:

The operations can be performed using valid integers in the order 7, 5, 3, and 1.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 100

Approach overview

Problem Overview: You are given an integer array nums and a target value k. The goal is to determine the minimum number of operations needed so every element becomes exactly k. An operation effectively eliminates a value greater than k by converting all occurrences of that value to k. If any number is already smaller than k, the task becomes impossible because operations only reduce larger values to k.

Approach 1: Hash Set to Track Distinct Values ( O(n) time, O(n) space )

Start by scanning the array once. If you encounter any value smaller than k, immediately return -1 because no valid operation can increase values. For values greater than k, insert them into a set (or hash table). Each distinct value greater than k represents one required operation, since the operation reduces that specific value to k for all its occurrences. After processing the array, the answer equals the number of unique elements stored in the set.

The key insight: multiple occurrences of the same value can be handled in a single operation. Only the number of distinct values above k matters. A hash table or set provides constant‑time insertion and membership checks, making the solution linear.

Implementation is straightforward: iterate through the array, validate values relative to k, and track distinct values larger than k. Languages like Python, Java, and C++ all provide efficient built‑in hash set structures.

Recommended for interviews: The hash‑set approach is the expected solution. Interviewers want to see that you recognize two constraints quickly: values smaller than k make the task impossible, and duplicate values above k should only count once. Explaining this observation shows strong reasoning about hash-based deduplication and linear scans. Brute‑force counting without deduplication leads to incorrect results, so identifying the need for a set demonstrates the key insight.

Solution

According to the problem description, we can choose the second largest value in the current array as the valid integer h each time, and change all numbers greater than h to h. This minimizes the number of operations. Additionally, since the operation reduces the numbers, if there are numbers in the current array smaller than k, we cannot make all numbers equal to k, so we directly return -1.

We iterate through the array nums. For the current number x, if x < k, we directly return -1. Otherwise, we add x to the hash table and update the minimum value mi in the current array. Finally, we return the size of the hash table minus 1 (if mi = k, we need to subtract 1).

Time complexity is O(n), and space complexity is O(n), where n is the length of the array nums.

Python

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        s = set()
        mi = inf
        for x in nums:
            if x < k:
                return -1
            mi = min(mi, x)
            s.add(x)
        return len(s) - int(k == mi)

Java

class Solution {
    public int minOperations(int[] nums, int k) {
        Set<Integer> s = new HashSet<>();
        int mi = 1 << 30;
        for (int x : nums) {
            if (x < k) {
                return -1;
            }
            mi = Math.min(mi, x);
            s.add(x);
        }
        return s.size() - (mi == k ? 1 : 0);
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> s;
        int mi = INT_MAX;
        for (int x : nums) {
            if (x < k) {
                return -1;
            }
            mi = min(mi, x);
            s.insert(x);
        }
        return s.size() - (mi == k);
    }
};

JavaScript

function minOperations(nums, k) {
    const s = new Set([k]);
    for (const x of nums) {
        if (x < k) return -1;
        s.add(x);
    }
    return s.size - 1;
}

TypeScript

function minOperations(nums: number[], k: number): number {
    const s = new Set<number>([k]);
    for (const x of nums) {
        if (x < k) return -1;
        s.add(x);
    }
    return s.size - 1;
}

func minOperations(nums []int, k int) int {
	mi := 1 << 30
	s := map[int]bool{}
	for _, x := range nums {
		if x < k {
			return -1
		}
		s[x] = true
		mi = min(mi, x)
	}
	if mi == k {
		return len(s) - 1
	}
	return len(s)
}

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashSet;

        let mut s = HashSet::new();
        let mut mi = i32::MAX;

        for &x in &nums {
            if x < k {
                return -1;
            }
            s.insert(x);
            mi = mi.min(x);
        }

        (s.len() as i32) - if mi == k { 1 } else { 0 }
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Hash Set (Count Distinct Values > k)	O(n)	O(n)	General case. Efficient for unsorted arrays and handles duplicates naturally.
Sorting + Unique Scan	O(n log n)	O(1) or O(n)	Useful when the array is already sorted or when avoiding hash structures.

Frequently asked questions

Is Minimum Operations to Make Array Values Equal to K easy or hard?

The problem is classified as Easy. The main challenge is recognizing that duplicates should only count once and that values smaller than k make the transformation impossible.

Minimum Operations to Make Array Values Equal to K Python/Java solution

Both Python and Java implementations follow the same idea: iterate through the array, check for values smaller than k, and add values greater than k to a set. The final answer is the set size. Python typically uses set(), while Java uses HashSet<Integer>.

How to solve Minimum Operations to Make Array Values Equal to K in O(n)?

Iterate through the array and check each value relative to k. If any value is smaller than k, return -1. Otherwise insert every value greater than k into a hash set. The number of unique elements in the set represents the minimum number of operations.

What is the best approach for Minimum Operations to Make Array Values Equal to K?

The optimal approach uses a hash set to track distinct numbers greater than k. Each unique value larger than k requires one operation, since all occurrences can be reduced together. If any number is smaller than k, the task is impossible. This solution runs in O(n) time and O(n) space.

Is Minimum Operations to Make Array Values Equal to K asked at Google/Amazon/Meta?

Problems involving hash tables and deduplication patterns frequently appear in interviews at companies like Amazon, Google, and Meta. This specific problem is relatively easy but tests whether you recognize when duplicates should be counted only once.

What data structure is used in Minimum Operations to Make Array Values Equal to K?

A hash set (or hash table) is the primary data structure. It stores distinct values greater than k so duplicate elements do not increase the operation count.

What is the time complexity of Minimum Operations to Make Array Values Equal to K?

The optimal hash set solution runs in O(n) time because the array is scanned once and each insertion into the set is O(1) on average. Space complexity is O(n) in the worst case if all elements greater than k are distinct.

Minimum Operations to Make Array Values Equal to K solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Minimum Operations to Make Array Values Equal to K solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems