Watch 10 video solutions for Minimum Number of Operations to Make Elements in Array Distinct, a easy level problem involving Array, Hash Table. This walkthrough by codestorywithMIK has 6,210 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums. You need to ensure that the elements in the array are distinct. To achieve this, you can perform the following operation any number of times:
Note that an empty array is considered to have distinct elements. Return the minimum number of operations needed to make the elements in the array distinct.
Example 1:
Input: nums = [1,2,3,4,2,3,3,5,7]
Output: 2
Explanation:
[4, 2, 3, 3, 5, 7].[3, 5, 7], which has distinct elements.Therefore, the answer is 2.
Example 2:
Input: nums = [4,5,6,4,4]
Output: 2
Explanation:
[4, 4].Therefore, the answer is 2.
Example 3:
Input: nums = [6,7,8,9]
Output: 0
Explanation:
The array already contains distinct elements. Therefore, the answer is 0.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You are given an integer array where one operation removes the first three elements. The goal is to determine the minimum number of operations required so that the remaining array contains only distinct values.
Approach 1: Brute Force Simulation (O(n^2) time, O(n) space)
The most direct strategy simulates each operation. Repeatedly remove the first three elements, then check whether the remaining array contains duplicates. The duplicate check can be done using a set while iterating through the remaining elements. In the worst case you perform about n/3 operations and scan the array each time, which leads to O(n^2) time complexity. This method works but wastes time repeatedly rechecking the same suffix.
Approach 2: Hash Table + Reverse Traversal (O(n) time, O(n) space)
A more efficient insight: only the final suffix matters. After k operations, the remaining array starts at index 3k. That suffix must contain only unique values. Instead of simulating removals, scan the array from right to left while storing seen values in a hash set. As soon as you encounter a duplicate, you know the valid unique suffix must start after that index.
Let start be the first index of this maximal unique suffix. To reach it using prefix removals of size three, you must delete at least start elements. The required number of operations becomes ceil(start / 3). This works because reverse traversal guarantees the suffix already contains unique elements, and the hash table provides constant-time membership checks while scanning the array.
The algorithm processes each element once and performs O(1) set lookups, giving O(n) time complexity and O(n) extra space for the set.
Recommended for interviews: The hash table + reverse traversal approach is what interviewers expect. The brute-force simulation shows you understand the rules of the operation, but recognizing that the answer depends only on the longest unique suffix demonstrates stronger problem-solving skills and leads to the optimal O(n) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(n) | Good for understanding the problem rules or small arrays |
| Hash Table + Reverse Traversal | O(n) | O(n) | Optimal approach for general cases and coding interviews |