Minimum Number of Operations to Make Elements in Array Distinct
EasyPrompt
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:
- Remove 3 elements from the beginning of the array. If the array has fewer than 3 elements, remove all remaining elements.
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:
- In the first operation, the first 3 elements are removed, resulting in the array
[4, 2, 3, 3, 5, 7]. - In the second operation, the next 3 elements are removed, resulting in the array
[3, 5, 7], which has distinct elements.
Therefore, the answer is 2.
Example 2:
Input: nums = [4,5,6,4,4]
Output: 2
Explanation:
- In the first operation, the first 3 elements are removed, resulting in the array
[4, 4]. - In the second operation, all remaining elements are removed, resulting in an empty array.
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] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We can try performing zero operations, check if the array is distinct. If not, we try one operation, check the resulting subarray, and so on. We continue this process, incrementing the number of operations, until we find the first number of operations that results in an array with distinct elements. Since we are looking for the minimum number of operations, the first time we satisfy the condition, we have found our answer.
Algorithm
- Iterate through the number of possible operations,
ops, starting from 0. - For each
ops, calculate the starting index of the remaining subarray:startIndex = ops * 3. - If
startIndexis greater than or equal to the array length, it means the array becomes empty. An empty array is distinct, so we returnops. - Otherwise, we check if the subarray
nums[startIndex:]contains only distinct elements. - To check for distinctness, we can use a
HashSet. We iterate through the subarray, and if we encounter an element that's already in the set, the subarray is not distinct. - The first value of
opsfor which the remaining subarray is distinct is our answer.
Walkthrough
The algorithm iterates through the possible number of operations, k, starting from 0. For each k, it calculates how many elements would be removed (3 * k) and determines the resulting subarray. It then checks if this subarray has all unique elements. A helper function, isDistinct, can be used for this check, which typically involves using a HashSet to track seen elements. The loop continues until a distinct subarray is found, and the corresponding k is returned.
import java.util.HashSet;import java.util.Set; class Solution { public int minOperations(int[] nums) { int n = nums.length; // Iterate through the number of operations for (int ops = 0; ; ops++) { int startIndex = ops * 3; if (startIndex >= n) { // After 'ops' operations, the array becomes empty. // An empty array has distinct elements. return ops; } // Check if the subarray nums[startIndex...] has distinct elements. if (isDistinct(nums, startIndex)) { return ops; } } } // Helper function to check for distinct elements in a subarray private boolean isDistinct(int[] nums, int start) { Set<Integer> seen = new HashSet<>(); for (int i = start; i < nums.length; i++) { if (!seen.add(nums[i])) { // Found a duplicate, so not distinct return false; } } // No duplicates found return true; }}Complexity
Time
O(N^2), where N is the length of `nums`. The outer loop can run up to `N/3` times. In each iteration, the `isDistinct` function iterates over a subarray, which can have up to N elements. This results in a quadratic time complexity.
Space
O(N), where N is the number of elements in `nums`. The `HashSet` used to check for distinctness can store up to N elements in the worst case.
Trade-offs
Pros
It's straightforward to understand as it directly models the problem statement.
It's guaranteed to find the correct minimum number of operations.
Cons
This approach is inefficient because it repeatedly scans subarrays. For each potential number of operations, it re-evaluates a large portion of the array, leading to redundant work.
A more efficient approach is to rephrase the problem. Instead of finding the shortest prefix to remove, we can find the longest suffix that remains and is distinct. Once we identify the starting point of this suffix, we know exactly how many elements from the beginning of the array must be removed.
We can find this longest distinct suffix in a single pass by iterating from the end of the array. We use a HashSet to keep track of the elements we've encountered. The first time we see a duplicate element (from the right), we know where the distinct suffix must begin.
Algorithm
- The goal is to find the minimum number of operations, which means we want to find the shortest prefix to remove such that the remaining suffix has distinct elements.
- This is equivalent to finding the longest suffix that has distinct elements.
- We can find this longest distinct suffix by iterating through the array from right to left.
- Initialize an empty
HashSetto store elements of the current suffix being examined. - Iterate from
i = nums.length - 1down to0. - For each element
nums[i], try to add it to the set. If the element is already in the set, we have found a duplicate. This means the longest distinct suffix must start at indexi + 1. - The number of elements to remove is
i + 1. - If the loop completes without finding duplicates, the entire array is distinct, and we need to remove 0 elements.
- Once we have the number of elements to remove,
k, the minimum number of operations isceil(k / 3), which can be calculated with integer arithmetic as(k + 2) / 3.
Walkthrough
This optimized algorithm avoids the nested loops of the brute-force approach. It iterates through the array once, from right to left. A HashSet is used to detect duplicates. When the first duplicate is found at index i (while scanning from the right), we know that the longest possible suffix with distinct elements must start at index i + 1. Therefore, we need to remove i + 1 elements from the beginning of the array. If no duplicates are found after scanning the entire array, it means the array is already distinct, and 0 operations are needed. The number of operations is then calculated based on the number of elements that need to be removed.
import java.util.HashSet;import java.util.Set; class Solution { public int minOperations(int[] nums) { int n = nums.length; Set<Integer> seen = new HashSet<>(); int firstDuplicateIndex = -1; // Iterate from right to left to find the start of the non-distinct part for (int i = n - 1; i >= 0; i--) { if (!seen.add(nums[i])) { // This is the first duplicate we encounter from the right. // Any suffix starting at or before this index will not be distinct. firstDuplicateIndex = i; break; } } if (firstDuplicateIndex == -1) { // No duplicates found, the whole array is distinct. return 0; } // The longest distinct suffix starts at index `firstDuplicateIndex + 1`. // We need to remove all elements before it. int elementsToRemove = firstDuplicateIndex + 1; // Each operation removes 3 elements. // We need ceil(elementsToRemove / 3) operations. // This can be calculated as (elementsToRemove + 2) / 3 using integer division. return (elementsToRemove + 2) / 3; }}Complexity
Time
O(N), where N is the length of `nums`. The algorithm involves a single pass through the array.
Space
O(N), where N is the number of elements in `nums`. The `HashSet` can store up to N unique elements in the worst-case scenario where the entire array is distinct.
Trade-offs
Pros
Highly efficient with a linear time complexity, making it suitable for larger constraints.
Avoids redundant computations by scanning the array only once.
Cons
The logic of working backward from the end of the array might be slightly less intuitive at first glance compared to a direct simulation.
Solutions
Solution
class Solution {public int minimumOperations(int[] nums) { Set<Integer> s = new HashSet<>(); for (int i = nums.length - 1; i >= 0; --i) { if (s.contains(nums[i])) { return i / 3 + 1; } s.add(nums[i]); } return 0; }}class Solution: def minimumOperations(self, nums: List[int]) -> int: s = set() for i in range(len(nums) - 1, - 1, - 1): if nums[i] in s: return i // 3 + 1 s . add(nums[i]) return 0class Solution {public: int minimumOperations(vector<int> &nums) { unordered_set<int> s; for (int i = nums.size() - 1; ~i; --i) { if (s.contains(nums[i])) { return i / 3 + 1; } s.insert(nums[i]); } return 0; }};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.