Minimum Number of Operations to Have Distinct Elements - Solution & Explanation
Problem Statement
You are given an integer array nums.
In one operation, you remove the first three elements of the current array. If there are fewer than three elements remaining, all remaining elements are removed.
Repeat this operation until the array is empty or contains no duplicate values.
Return an integer denoting the number of operations required.
Example 1:
Input: nums = [3,8,3,6,5,8]
Output: 1
Explanation:
In the first operation, we remove the first three elements. The remaining elements [6, 5, 8] are all distinct, so we stop. Only one operation is needed.
Example 2:
Input: nums = [2,2]
Output: 1
Explanation:
After one operation, the array becomes empty, which meets the stopping condition.
Example 3:
Input: nums = [4,3,5,1,2]
Output: 0
Explanation:
All elements in the array are distinct, therefore no operations are needed.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Approach Overview
Problem Overview: You are given an integer array. In one operation, you remove the first three elements from the array. The goal is to determine the minimum number of operations required so that the remaining array contains only distinct elements.
Approach 1: Brute Force Simulation (O(n^2) time, O(n) space)
Directly simulate the process. After every operation, remove the first three elements and check whether the remaining array contains duplicates. Duplicate detection can be done with a set by scanning the remaining elements. This approach repeatedly re-checks the array from scratch, which leads to quadratic behavior in the worst case. It works for small inputs but becomes inefficient when the array is large.
Approach 2: Hash Table + Reverse Traversal (O(n) time, O(n) space)
The key observation: operations only remove elements from the front. That means the suffix of the array remains untouched. Instead of simulating removals, scan the array from right to left and track elements in a hash set. While traversing, insert each value into the set. The first time you encounter a duplicate, that index marks the earliest position that must be removed to ensure the remaining suffix is distinct.
If the leftmost duplicate appears at index i, all elements from 0..i must eventually be removed. Since each operation removes three elements, the required number of operations is ceil((i + 1) / 3). If the reverse traversal completes without finding duplicates, the array is already distinct and the answer is 0.
This method relies on constant-time hash lookups from a hash table and a single pass through the array. Reverse traversal avoids unnecessary simulation and directly identifies the minimum prefix that must be removed. The technique is common in array problems where operations affect only the prefix or suffix.
Recommended for interviews: The hash table + reverse traversal approach. Brute force simulation shows understanding of the problem mechanics, but interviewers expect you to recognize that repeatedly re-checking the array is wasteful. A single reverse scan with a set demonstrates stronger algorithmic thinking and achieves optimal O(n) time.
Solution
We can traverse the array nums in reverse order and use a hash table st to record the elements we have already traversed. When we traverse to element nums[i], if nums[i] is already in the hash table st, it means we need to remove all elements in nums[0..i], and the number of operations required is \left\lfloor \frac{i}{3} \right\rfloor + 1. Otherwise, we add nums[i] to the hash table st and continue to traverse the next element.
After the traversal is complete, if no duplicate elements are found, then all elements in the array are already distinct, no operations are needed, and the answer is 0.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(n) | Good for understanding the operation process or very small arrays |
| Hash Table + Reverse Traversal | O(n) | O(n) | Optimal solution for general cases; avoids repeated scans and finds the earliest duplicate efficiently |
Video Solution
LeetCode 3779 🔥 Minimum Operations for Distinct Elements | Biweekly Contest 172 | HashMap Trick • Study Placement • 316 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Minimum Number of Operations to Have Distinct Elements easy or hard?
Minimum Number of Operations to Have Distinct Elements Python/Java solution
How to solve Minimum Number of Operations to Have Distinct Elements in O(n)?
What is the best approach for Minimum Number of Operations to Have Distinct Elements?
Is Minimum Number of Operations to Have Distinct Elements asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Operations to Have Distinct Elements?
What is the time complexity of Minimum Number of Operations to Have Distinct Elements?
Ready to solve this problem?
Practice Minimum Number of Operations to Have Distinct Elements with our built-in code editor and test cases.
Practice on FleetCode