Problem Description

You have an integer array nums and need to make all elements in the array distinct (no duplicates).

To achieve this, you can perform a specific 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

An empty array is considered to have distinct elements.

Your task is to find the minimum number of operations needed to make all elements in the array distinct.

For example, if you have an array like [1, 2, 3, 4, 2], the last element 2 is a duplicate. To remove this duplicate, you need to remove elements from the beginning until you've removed the first occurrence of 2. Since you remove 3 elements at a time, you'd need to perform operations to remove the first few elements.

The solution works by traversing the array from right to left, keeping track of seen elements in a set. When a duplicate is found at position i, it means all elements from index 0 to i must be removed. The number of operations needed is ⌊i/3⌋ + 1 (since we remove 3 elements per operation, and any remainder requires one additional operation).

Intuition

The key insight is that we want to keep as many elements as possible while ensuring all remaining elements are distinct. Since we can only remove elements from the beginning of the array, we need to think about which elements we can keep at the end.

If we look at the array from right to left, we can identify the longest suffix (ending portion) of the array that contains all distinct elements. This suffix is what we want to preserve, and everything before it needs to be removed.

Why traverse from right to left? Because:

1. We can only remove from the beginning, so we want to keep elements at the end
2. As we traverse from right to left, we can track which elements we've seen using a set
3. The moment we encounter a duplicate (an element already in our set), we know that this element and everything before it must be removed

For example, in array [1, 2, 3, 4, 2]:

• Starting from the right: 2 is new, add to set
• 4 is new, add to set
• 3 is new, add to set
• 2 is already in the set! This means we need to remove everything from index 0 to 1 (the position of the first 2)

Once we know we need to remove all elements up to index i, the number of operations is calculated as ⌊i/3⌋ + 1 because:

• We remove 3 elements per operation
• If i+1 elements need to be removed, we need ⌊i/3⌋ complete operations of 3 elements
• Plus 1 more operation for any remaining elements (1 or 2 elements)

This greedy approach of keeping the maximum valid suffix ensures we perform the minimum number of operations.

Solution Approach

The solution implements a hash table with reverse traversal strategy to find the minimum operations needed.

Implementation Steps:

1. Initialize a hash set: Create an empty set s to track elements we've encountered while traversing from right to left.

2. Reverse traversal: Iterate through the array from the last index to the first using range(len(nums) - 1, -1, -1).

3. Check for duplicates: For each element nums[i]:

   • If nums[i] is already in the set s, it means we've found a duplicate
   • This duplicate and all elements before it (indices 0 to i) must be removed
   • Calculate the number of operations: i // 3 + 1
     • i // 3 gives us the number of complete 3-element removals
     • + 1 accounts for the final operation (removing 1, 2, or 3 elements)
   • Return this value immediately as we've found our answer

4. Add to set: If nums[i] is not in the set, add it to s and continue to the next element (moving leftward).

5. No duplicates found: If we complete the entire traversal without finding any duplicates, return 0 as no operations are needed.

Example walkthrough with nums = [1, 2, 3, 4, 2]:

• Start from index 4: nums[4] = 2, not in set, add 2 to set
• Index 3: nums[3] = 4, not in set, add 4 to set
• Index 2: nums[2] = 3, not in set, add 3 to set
• Index 1: nums[1] = 2, already in set!
• Return 1 // 3 + 1 = 0 + 1 = 1 operation needed

The time complexity is O(n) where n is the length of the array, and the space complexity is O(n) for the hash set in the worst case when all elements are distinct.

Example Walkthrough

Let's walk through the solution with the array nums = [5, 1, 2, 5, 3, 2].

Step 1: Initialize

• Create an empty set s = {}
• Start traversing from the rightmost element (index 5)

Step 2: Traverse from right to left

Index 5: nums[5] = 2

• 2 is not in set s
• Add 2 to set: s = {2}
• Continue

Index 4: nums[4] = 3

• 3 is not in set s
• Add 3 to set: s = {2, 3}
• Continue

Index 3: nums[3] = 5

• 5 is not in set s
• Add 5 to set: s = {2, 3, 5}
• Continue

Index 2: nums[2] = 2

• 2 is already in set s! (We saw it at index 5)
• This means we have a duplicate
• We need to remove all elements from index 0 to index 2 (that's 3 elements total)

Step 3: Calculate operations

• Elements to remove: indices 0, 1, 2 (three elements: [5, 1, 2])
• Number of operations = 2 // 3 + 1 = 0 + 1 = 1
• One operation removes all 3 elements from the beginning

Result: After 1 operation, the array becomes [5, 3, 2], which has all distinct elements.

Another Example: nums = [1, 1, 1, 1]

Index 3: nums[3] = 1, add to set: s = {1} Index 2: nums[2] = 1, already in set!

• Need to remove indices 0, 1, 2 (three elements)
• Operations = 2 // 3 + 1 = 0 + 1 = 1

After 1 operation, array becomes [1] with all distinct elements.

Edge Case Example: nums = [1, 2, 3, 4, 5, 1, 2]

Index 6: nums[6] = 2, add to set: s = {2} Index 5: nums[5] = 1, add to set: s = {1, 2} Index 4: nums[4] = 5, add to set: s = {1, 2, 5} Index 3: nums[3] = 4, add to set: s = {1, 2, 4, 5} Index 2: nums[2] = 3, add to set: s = {1, 2, 3, 4, 5} Index 1: nums[1] = 2, already in set!

• Need to remove indices 0, 1 (two elements)
• Operations = 1 // 3 + 1 = 0 + 1 = 1

After 1 operation (removing 2 elements), array becomes [3, 4, 5, 1, 2] with all distinct elements.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array once from right to left, performing constant-time operations (set lookup and insertion) for each element.

The space complexity is O(n). In the worst case, when all elements in the array are unique, the set s will store all n elements from the array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Direction of Traversal

A common mistake is traversing the array from left to right instead of right to left. This approach fails because we need to preserve the rightmost occurrence of each element.

Incorrect approach:

def minimumOperations(self, nums: List[int]) -> int:
    seen = set()
    for i in range(len(nums)):  # Wrong: left to right
        if nums[i] in seen:
            # This finds the second occurrence, not optimal
            return (len(nums) - i - 1) // 3 + 1
        seen.add(nums[i])
    return 0

Why it fails: For nums = [1, 2, 1, 3], this would try to remove elements from position 2 onwards, but we actually need to remove from the beginning up to position 2.

2. Incorrect Operation Count Calculation

Another pitfall is miscalculating the number of operations needed when finding a duplicate at index i.

Common mistakes:

• Using i // 3 without adding 1 (forgets partial removal)
• Using (i + 1) // 3 (incorrectly counts elements to remove)
• Using i // 3 + (1 if i % 3 else 0) (overcomplicates the logic)

Correct formula: i // 3 + 1

• We need to remove elements from index 0 to i (inclusive)
• That's i + 1 elements total
• Operations needed = ⌈(i + 1) / 3⌉ = i // 3 + 1

3. Not Handling Edge Cases

Failing to consider edge cases can lead to runtime errors:

Edge cases to consider:

• Empty array: nums = [] → should return 0
• Single element: nums = [1] → should return 0
• All duplicates: nums = [1, 1, 1, 1] → needs proper handling

Robust solution:

def minimumOperations(self, nums: List[int]) -> int:
    if not nums:  # Handle empty array
        return 0
      
    seen_elements = set()
    for index in range(len(nums) - 1, -1, -1):
        if nums[index] in seen_elements:
            return index // 3 + 1
        seen_elements.add(nums[index])
    return 0

4. Using Wrong Data Structure

Using a list instead of a set for tracking seen elements causes inefficient lookups:

Inefficient:

seen_elements = []  # O(n) lookup time
if nums[index] in seen_elements:  # Slow for large arrays

Efficient:

seen_elements = set()  # O(1) average lookup time
if nums[index] in seen_elements:  # Fast