Minimum Operations to Make Array Values Equal to K Solution
Minimum Operations to Make Array Values Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Operations to Make Array Values Equal to K is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and an integer k.
Call an integer h valid if every element of nums that is strictly greater than h has the same value. (For nums = [10,8,10,8], h = 9 is valid because every element above 9 is 10, but h = 5 is not.)
In one operation you choose a valid h and set every element greater than h to h.
Return the minimum number of operations needed to make every element equal to k, or -1 if it cannot be done.
Example 1
Input: nums = [6,3,6,4], k = 3
Output: 2
Explanation: Lower the `6`s to `4` (h = 4 is valid), then lower the `4`s to `3`.
Example 2
Input: nums = [4,1,4], k = 2
Output: -1
Explanation: Operations only lower values, so the `1` can never become `2`.
Example 3
Input: nums = [7,7,7], k = 7
Output: 0
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 100
Hints for Minimum Operations to Make Array Values Equal to K
Hint 1
An operation can only decrease values. What does that say about an element already below
k?Hint 2
A valid
hcan only touch the elements equal to the current maximum, and the best it can do is bring them down to the next distinct value (or tok).Hint 3
So every distinct value above
kcosts exactly one operation.
How to solve Minimum Operations to Make Array Values Equal to K
Since h is valid only when everything above it is one value, each operation can flatten just the current maximum level. Each distinct value greater than k therefore needs its own operation, and lowering to the next distinct value achieves exactly that count.
Approach
- If any element is smaller than
k, return-1— nothing can raise it. - Otherwise collect the distinct values strictly greater than
kin a set. - Return the size of that set.
Why it works
Each operation merges the top level into a lower one, reducing the number of distinct values above k by at most one — any lower h would have two different values above it and be invalid. Choosing h as the next distinct value (or k for the last level) achieves a reduction of exactly one each time, so the count of distinct values above k is both a lower bound and achievable.
Complexity
- Time —
O(n) - Space —
O(V) with V = 100 possible values
Pitfalls
- Count distinct values above
k, not elements. - Values equal to
kneed no operation; values belowkmake the task impossible.
Reference solution
Python
from typing import List
def minOperations(nums: List[int], k: int) -> int:
if min(nums) < k:
return -1
return len({v for v in nums if v > k})Java
public static int minOperations(int[] nums, int k) {
boolean[] seen = new boolean[101];
int distinct = 0;
for (int v : nums) {
if (v < k) return -1;
if (v > k && !seen[v]) {
seen[v] = true;
distinct++;
}
}
return distinct;
}C++
int minOperations(vector<int>& nums, int k) {
vector<bool> seen(101, false);
int distinct = 0;
for (int v : nums) {
if (v < k) return -1;
if (v > k && !seen[v]) {
seen[v] = true;
distinct++;
}
}
return distinct;
}JavaScript
var minOperations = function(nums, k) {
var seen = {};
var distinct = 0;
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
if (v < k) return -1;
if (v > k && !seen[v]) {
seen[v] = true;
distinct++;
}
}
return distinct;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets