Minimum Operations to Make Array Values Equal to K - Video Solutions
Minimum Operations to Make Array Values Equal to K | Detailed Thought Process | Leetcode 3375 | MIK
Minimum Operations to Make Array Values Equal to K - Video Solution
Watch 10 video solutions for Minimum Operations to Make Array Values Equal to K, a easy level problem involving Array, Hash Table. This walkthrough by codestorywithMIK has 6,578 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
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.
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. |