Minimum Operations to Make Array Values Equal to K
EasyPrompt
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
hthat is valid for the current values innums. - For each index
iwherenums[i] > h, setnums[i]toh.
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 <= 1001 <= nums[i] <= 1001 <= k <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It iteratively finds the largest value in the array that is greater than k and performs an operation to reduce it. This is repeated until all values in the array are less than or equal to k. While conceptually straightforward, this method is less efficient because it requires multiple passes over the array.
Algorithm
- First, perform an initial check: iterate through the array
nums. If any elementnumis less thank, it's impossible to reach the target, so return -1. - Initialize an
operationscounter to 0. - Start a loop that continues as long as the maximum value in the array is greater than
k. - Inside the loop:
- Find the maximum value
max_valin the current array. - If
max_valis less than or equal tok, the process is complete, so break the loop. - Find the largest value
hin the array that is strictly less thanmax_val. If no such element exists (meaning all elements greater thankaremax_val), seth = k. - Increment the
operationscounter. - Iterate through the array and replace all occurrences of
max_valwithh. This simulates one operation.
- Find the maximum value
- After the loop terminates, return the total
operationscount.
Walkthrough
The algorithm begins by checking for an impossible scenario: if any element in nums is already smaller than k, we can never increase it to k, so we return -1. Otherwise, we enter a loop to perform the operations. In each iteration, we find the current maximum value, max_val. If this max_val is greater than k, we must reduce it. To do this, we find the next distinct value smaller than max_val in the array to use as our h. This choice of h guarantees validity because all elements greater than h will be identical (they will all be max_val). We then increment our operation count and update all instances of max_val to h. This process continues until the array's maximum value is no longer greater than k.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int minOperations(int[] nums, int k) { for (int num : nums) { if (num < k) { return -1; } } List<Integer> currentNums = new ArrayList<>(); for (int num : nums) { currentNums.add(num); } int operations = 0; while (true) { int maxVal = 0; for (int num : currentNums) { if (num > maxVal) { maxVal = num; } } if (maxVal <= k) { break; } operations++; int h = k; int nextMax = 0; for (int num : currentNums) { if (num < maxVal && num > nextMax) { nextMax = num; } } if (nextMax > k) { h = nextMax; } for (int i = 0; i < currentNums.size(); i++) { if (currentNums.get(i) == maxVal) { currentNums.set(i, h); } } } return operations; }}Complexity
Time
O(U * N), where N is the length of `nums` and U is the number of unique elements greater than `k`. In each of the U operations, we scan the array multiple times (to find max, next max, and update), leading to O(N) work per operation. In the worst case, U can be up to N, leading to O(N^2).
Space
O(N), where N is the number of elements in `nums`. This is because we create a mutable list to store the current state of the array. If the input array is modified in-place, the space complexity would be O(1).
Trade-offs
Pros
Directly models the problem statement, which can be easier to reason about initially.
Does not require complex data structures.
Cons
Inefficient due to repeated traversals of the array within a loop.
Finding the max and next-max value in each iteration adds significant overhead.
Modifying the array (or a copy) in each step is computationally expensive.
A more efficient approach is to sort the array. After sorting, all identical values are grouped together, and all values are ordered. This makes it easy to count the number of unique values greater than k by performing a single pass over the sorted array. Each such unique value corresponds to one required operation.
Algorithm
- First, check for the impossibility condition: iterate through
numsand if any elementnum < k, return -1. - Sort the
numsarray in non-decreasing order. - Initialize
operations = 0and a variablelast_val = -1to track the last unique value encountered. - Iterate through the sorted array from right to left (from index
n-1to0). - For each element
nums[i]:- If
nums[i] <= k, we can stop. Since the array is sorted, all subsequent elements will also be less than or equal tok. - If
nums[i] > kandnums[i]is not equal tolast_val, it means we have found a new, unique value level that needs an operation. Incrementoperationsand updatelast_val = nums[i].
- If
- Return the final
operationscount.
Walkthrough
The logic behind this approach is that each unique value greater than k represents a 'level' that must be flattened down to k. By sorting the array, we can easily identify these unique levels. The algorithm first handles the base case where any element is less than k, returning -1. Then, it sorts nums. A single pass from the end of the sorted array is sufficient to count the unique elements greater than k. We use a variable to keep track of the most recently seen value to avoid counting duplicates. For every new value we see that is greater than k, we increment our operation counter.
import java.util.Arrays; class Solution { public int minOperations(int[] nums, int k) { for (int num : nums) { if (num < k) { return -1; } } Arrays.sort(nums); int operations = 0; int lastVal = -1; for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] <= k) { break; } if (nums[i] > k && nums[i] != lastVal) { operations++; lastVal = nums[i]; } } return operations; }}Complexity
Time
O(N log N), where N is the length of `nums`. The sorting step is the dominant factor in the time complexity. The initial check and the final scan are both O(N).
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm used. For instance, Java's `Arrays.sort()` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
Trade-offs
Pros
Significantly more efficient than the simulation approach.
The logic is simple and clean after the initial sort.
Cons
The O(N log N) time complexity from sorting is not optimal.
Modifies the input array if sorted in-place, which might not be desirable in some contexts.
The most efficient approach recognizes that the problem is equivalent to counting the number of unique elements in the array that are strictly greater than k. Each such unique value requires one operation to be reduced. This can be solved in linear time using a hash set or, even better, a simple boolean array given the small range of values.
Algorithm
- First, iterate through
numsto check for the impossibility condition. If anynum < k, return -1. - Initialize a data structure to keep track of unique numbers. Given the constraint
nums[i] <= 100, a boolean arrayseenof size 101 is highly efficient. Initialize all its values tofalse. - Initialize
operations = 0. - Iterate through the
numsarray a second time. - For each
numinnums:- If
num > kandseen[num]isfalse, it means this is the first time we are encountering this unique value greater thank. - In this case, increment
operationsand mark this value as seen by settingseen[num] = true.
- If
- Return the total
operationscount.
Walkthrough
The core insight is that the minimum number of operations is exactly the number of unique values in nums that are greater than k. Each of these unique value 'levels' must be collapsed one by one until all values are k. The algorithm first ensures possibility by checking that no element is less than k. Then, it iterates through the array once, using a boolean array seen (acting as a frequency map for the small, fixed range of numbers) to keep track of the unique values greater than k. For each number num > k, if it hasn't been seen before, we increment an operation counter and mark it as seen. The final count is the answer.
class Solution { public int minOperations(int[] nums, int k) { // First pass: check for impossibility for (int num : nums) { if (num < k) { return -1; } } boolean[] seen = new boolean[101]; // Constraints: 1 <= nums[i] <= 100 int operations = 0; // Second pass: count unique elements greater than k for (int num : nums) { if (num > k) { if (!seen[num]) { operations++; seen[num] = true; } } } return operations; }}Complexity
Time
O(N), where N is the length of `nums`. The algorithm involves two separate, non-nested passes through the array, resulting in linear time complexity.
Space
O(C), where C is the range of possible values for `nums[i]`. Given the constraint `nums[i] <= 100`, C is a constant (101), making the space complexity O(1).
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1) due to the fixed, small range of input values.
Simple and easy to implement.
Cons
Requires extra space for the hash set or frequency array. However, given the problem's constraints, this space is constant and small.
Solutions
Solution
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); }}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 ; }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); }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.