LeetCode 3779 - Minimum Number of Operations to Have Distinct Elements

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives us an integer array nums and defines a very specific operation: in one move, we remove the first three elements of the current array. If fewer than three elements remain, we remove everything that is left.

We continue performing this operation until one of two conditions becomes true:

The array becomes empty.
The remaining elements are all distinct, meaning there are no duplicate values.

The goal is to determine the minimum number of operations needed to satisfy either stopping condition.

A key detail is that we are not allowed to choose which elements to remove. The operation is fixed. We always remove elements from the front of the array in groups of three. This means the state of the array after k operations is completely determined. After k operations, the remaining array is simply:

nums[3 * k:]

The task therefore becomes finding the smallest number of operations such that the suffix of the array contains only distinct elements.

The constraints are important:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

Since the array can contain up to 100,000 elements, an inefficient simulation that repeatedly scans the remaining array from scratch could become too slow. We should aim for an algorithm close to O(n) time.

Several edge cases deserve attention immediately. If the array already contains only distinct elements, the answer should be 0. If all elements are duplicates and repeated removals eventually empty the array, we must count the exact number of operations. Arrays shorter than three elements also require care because a single operation removes everything.

Approaches

Brute Force Approach

The most direct idea is to simulate the process exactly as described.

At each step:

Check whether the current array contains duplicates.
If all elements are distinct, stop.
Otherwise, remove the first three elements and count one operation.

To check whether an array has duplicates, we can compare the length of the array with the size of a set built from it. If they match, all elements are distinct.

This approach is correct because it literally follows the problem statement. Every operation is deterministic, and we stop exactly when the required condition is met.

However, it is inefficient. Suppose the array has length n. At each operation, we rebuild a set for the remaining suffix, which costs O(n) in the worst case. Since we may perform roughly n / 3 operations, the total complexity becomes O(n²) in the worst case.

With n = 10^5, this is too slow.

Optimal Approach

The key observation is that after k operations, the remaining array is always:

nums[3 * k:]

Instead of simulating removals repeatedly, we can determine the largest valid suffix that contains only distinct elements.

We process the array from right to left, maintaining a hash set of elements we have already seen.

Why does this work?

If we scan from the end toward the beginning:

As long as we encounter new values, the suffix remains distinct.
The moment we encounter a duplicate value, we know the current suffix is no longer valid.
To eliminate this duplicate, we must remove enough elements from the front so that this index disappears.

If the duplicate occurs at index i, we need the smallest number of operations such that:

3 * operations > i

This gives:

operations = i // 3 + 1

Since we scan from right to left, the first duplicate we encounter determines the answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly rebuilds sets after every removal
Optimal	O(n)	O(n)	Single reverse traversal using a hash set

Algorithm Walkthrough

Optimal Algorithm

Create an empty hash set called seen.

This set tracks which values already exist in the suffix we are building from right to left. A hash set is ideal because membership checks and insertions are average-case O(1). 2. Traverse the array from right to left.

We iterate from index n - 1 down to 0. At every step, we consider whether adding the current number would break the distinctness of the suffix. 3. Check whether the current element already exists in seen.

If it does not exist, add it to seen. This means the suffix is still valid and contains distinct values. 4. If the element already exists, we found a duplicate.

This means the suffix starting at this index is no longer distinct. To fix it, we must remove enough elements from the front so that this duplicate index disappears.

Since each operation removes three elements, the minimum number of operations required is:

i // 3 + 1

If the traversal finishes without finding duplicates, return 0.

This means the original array already contains only distinct values.

Why it works

The algorithm maintains the invariant that seen always represents a suffix containing distinct elements. By scanning from right to left, we are effectively finding the longest suffix with unique elements.

The first duplicate encountered marks the earliest index that invalidates distinctness. Since operations only remove prefixes in chunks of three, we compute exactly how many operations are needed to remove that problematic index. Any smaller number of operations would leave the duplicate in the remaining array, so the answer is minimal.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        seen = set()

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] in seen:
                return i // 3 + 1

            seen.add(nums[i])

        return 0

The implementation follows the reverse traversal strategy exactly.

We begin by initializing an empty seen set. This set stores values already encountered in the suffix.

The loop moves from the last index toward the first. For each element, we check whether it already exists in seen.

If the value is already present, we immediately return:

i // 3 + 1

This formula calculates how many operations are required to remove index i, since each operation removes three elements.

If the value is not in the set, we insert it and continue.

If the loop finishes without detecting duplicates, the array was already distinct, so we return 0.

Go Solution

func minOperations(nums []int) int {
	seen := make(map[int]bool)

	for i := len(nums) - 1; i >= 0; i-- {
		if seen[nums[i]] {
			return i/3 + 1
		}

		seen[nums[i]] = true
	}

	return 0
}

The Go implementation mirrors the Python logic closely. Since Go does not have a built in hash set type, we use a map[int]bool to simulate one.

We traverse the slice from right to left and check membership using the map. Once a duplicate is found, we compute the required number of operations using integer division:

i/3 + 1

There are no integer overflow concerns because indices are at most 10^5. Go slices naturally handle empty cases, so no extra checks are necessary.

Worked Examples

Example 1

Input:

nums = [3, 8, 3, 6, 5, 8]

We scan from right to left.

Index	Value	Seen Before?	Seen Set	Action
5	8	No	{8}	Continue
4	5	No	{8, 5}	Continue
3	6	No	{8, 5, 6}	Continue
2	3	No	{8, 5, 6, 3}	Continue
1	8	Yes	{8, 5, 6, 3}	Duplicate found

Duplicate found at index 1.

Required operations:

1 // 3 + 1 = 1

After removing the first three elements:

[6, 5, 8]

All remaining elements are distinct.

Answer: 1

Example 2

Input:

nums = [2, 2]

Index	Value	Seen Before?	Seen Set	Action
1	2	No	{2}	Continue
0	2	Yes	{2}	Duplicate found

Required operations:

0 // 3 + 1 = 1

Removing fewer than three elements means the whole array disappears.

Answer: 1

Example 3

Input:

nums = [4, 3, 5, 1, 2]

Index	Value	Seen Before?	Seen Set
4	2	No	{2}
3	1	No	{2, 1}
2	5	No	{2, 1, 5}
1	3	No	{2, 1, 5, 3}
0	4	No	{2, 1, 5, 3, 4}

No duplicates are found.

The array is already distinct.

Answer: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	The hash set may store every distinct element

The time complexity is linear because we traverse the array exactly once from right to left. Each set lookup and insertion is average-case O(1).

The space complexity is linear in the worst case because if all values are unique, the seen set stores every element.

Test Cases

sol = Solution()

assert sol.minOperations([3, 8, 3, 6, 5, 8]) == 1  # provided example with one removal
assert sol.minOperations([2, 2]) == 1  # provided example, array becomes empty
assert sol.minOperations([4, 3, 5, 1, 2]) == 0  # already distinct

assert sol.minOperations([1]) == 0  # single element is already distinct
assert sol.minOperations([7, 7]) == 1  # duplicate in short array
assert sol.minOperations([1, 2, 3]) == 0  # exactly three distinct elements
assert sol.minOperations([1, 1, 1]) == 1  # remove all three

assert sol.minOperations([1, 2, 3, 1]) == 1  # remove first three
assert sol.minOperations([1, 2, 3, 4, 1]) == 1  # duplicate resolved after one operation
assert sol.minOperations([1, 2, 3, 4, 5, 1]) == 1  # duplicate near front

assert sol.minOperations([1, 2, 1, 2, 1, 2]) == 2  # multiple removals needed
assert sol.minOperations([5, 5, 5, 5, 5]) == 1  # one removal leaves <= 2 elements

assert sol.minOperations([1, 2, 3, 4, 5, 6, 1]) == 1  # duplicate at start
assert sol.minOperations([1, 2, 3, 4, 5, 6, 7]) == 0  # all unique large suffix

Test	Why
`[3,8,3,6,5,8]`	Validates the first provided example
`[2,2]`	Tests short array removal
`[4,3,5,1,2]`	Confirms zero operations case
`[1]`	Minimum size input
`[7,7]`	Duplicate in size two array
`[1,2,3]`	Exactly three distinct elements
`[1,1,1]`	Entire array removed in one step
`[1,2,3,1]`	Duplicate resolved after one operation
`[1,2,3,4,1]`	Duplicate near opposite ends
`[1,2,1,2,1,2]`	Requires multiple removals
`[5,5,5,5,5]`	Heavy duplication
`[1,2,3,4,5,6,1]`	Duplicate at earliest index
`[1,2,3,4,5,6,7]`	Larger already-distinct input

Edge Cases

Array Already Contains Distinct Elements

An array such as:

[4, 3, 5, 1, 2]

requires zero operations. A buggy implementation might unnecessarily perform removals before checking uniqueness. Our solution handles this naturally because the reverse scan never encounters a duplicate, so it returns 0.

Array Length Less Than Three

Inputs like:

[2, 2]

are tricky because one operation removes the entire array, not exactly three elements. A naive implementation might incorrectly assume exactly three removals are required. Our formula:

i // 3 + 1

still works because any duplicate at index 0 or 1 requires one operation.

Multiple Duplicates Across the Array

Consider:

[1, 2, 1, 2, 1, 2]

There are many repeated values, and the correct answer is not determined by counting duplicates. What matters is the earliest duplicate that breaks the maximal distinct suffix. The reverse traversal correctly identifies the first problematic index and computes the minimal number of prefix removals needed.

Duplicate Near the Beginning

For an input like:

[1, 2, 3, 4, 5, 6, 1]

the duplicate involves the first and last elements. Since operations only remove from the front, removing one chunk of three eliminates the problematic first 1, leaving a distinct suffix. The algorithm correctly computes:

0 // 3 + 1 = 1

without simulating removals explicitly.