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.
We can traverse the array nums in reverse order and use a hash table s to record the elements that have already been traversed. When we encounter an element nums[i], if nums[i] is already in the hash table s, it means we need to remove all elements from nums[0..i]. The number of operations required is \left\lfloor \frac{i}{3} \right\rfloor + 1. Otherwise, we add nums[i] to the hash table s and continue to the next element.
After traversing, if no duplicate elements are found, the elements in the array are already distinct, and no operations are needed, so the answer is 0.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| 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 |
Minimum Number of Operations to Make Elements in Array Distinct | 2 Approaches | Leetcode 3396 | MIK • codestorywithMIK • 6,210 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make Elements in Array Distinct with our built-in code editor and test cases.
Practice on FleetCode