LeetCode 3396 - Minimum Number of Operations to Make Elements in Array Distinct

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives us an integer array nums, and our goal is to make all remaining elements distinct. The only allowed operation is removing exactly 3 elements from the beginning of the array. If fewer than 3 elements remain, we remove everything that is left.

We need to determine the minimum number of such operations required so that the remaining array contains no duplicate values.

Another way to think about the problem is this:

After performing some number of operations, the remaining array is always a suffix of the original array.
Each operation removes the first 3 elements.
We want the earliest suffix that contains only unique elements.
The answer is how many groups of 3 elements must be removed to reach that suffix.

For example, consider:

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

If we remove the first 3 elements once, the remaining array becomes:

[4,2,3,3,5,7]

This still contains duplicates because 3 appears twice.

After removing another 3 elements:

[3,5,7]

Now all elements are distinct, so the answer is 2.

The constraints are very small:

1 <= nums.length <= 100
1 <= nums[i] <= 100

This tells us several important things:

Efficiency is not a major concern, even an O(n^2) solution is completely acceptable.
We can freely use hash sets for duplicate detection.
Simplicity and correctness are more important than advanced optimization.

There are several edge cases worth noticing immediately.

If the array already contains all distinct values, the answer is 0.

If duplicates remain even after most elements are removed, we may eventually remove the entire array. Since an empty array is considered distinct, this is always a valid final state.

Arrays with fewer than 3 elements are also important. Since one operation removes all remaining elements in that case, the implementation must correctly handle short arrays.

Approaches

Brute Force Approach

The brute force approach simulates every possible number of operations.

For each possible operation count:

Remove 3 * operations elements from the front.
Check whether the remaining suffix contains only distinct values.
Return the first operation count that satisfies the condition.

To check whether a suffix contains distinct values, we can insert elements into a hash set. If we encounter a value already in the set, the suffix contains duplicates.

This approach is correct because it examines all possible valid states in increasing order of operations. The first valid suffix must therefore correspond to the minimum number of operations.

Although this solution repeatedly scans suffixes, the constraints are tiny, so performance is still acceptable.

Optimal Approach

The key observation is that every operation removes exactly 3 elements from the front. Therefore, after k operations, the remaining array always starts at index:

3 * k

Instead of physically removing elements repeatedly, we can simply iterate through possible starting positions:

0, 3, 6, 9, ...

For each starting position, we test whether the suffix from that position onward contains only distinct elements.

The first valid suffix immediately gives the minimum number of operations.

This is effectively the same logical process as the brute force method, but implemented more cleanly and efficiently without modifying the array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly simulates removals and scans suffixes
Optimal	O(n²)	O(n)	Iterates over suffix starting points directly

Even though both complexities are technically the same because of the small constraints, the optimal version is cleaner and avoids unnecessary array modifications.

Algorithm Walkthrough

Start with operations = 0.

This represents how many times we have removed 3 elements from the beginning. 2. Compute the starting index of the remaining suffix.

After operations removals, the remaining array starts at:

start = operations * 3

Check whether the suffix from start onward contains only distinct elements.

Use a hash set to track values we have already seen.

Iterate through the suffix:

If a value is not in the set, insert it.
If a value already exists in the set, duplicates remain, so this suffix is invalid.

If the suffix is distinct, return operations.

Since we test operation counts in increasing order, the first valid suffix automatically gives the minimum answer. 5. Otherwise, increment operations and repeat. 6. Eventually, the entire array may be removed.

An empty array is considered distinct, so the algorithm is guaranteed to terminate.

Why it works

The algorithm checks every possible array state that can result from valid operations. Since each operation removes exactly 3 elements from the front, every reachable state corresponds to a suffix beginning at index 3 * k.

By testing these suffixes in increasing order of k, the first suffix with all distinct elements must require the minimum number of operations.

Python Solution

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        operations = 0

        while True:
            start = operations * 3
            seen = set()
            distinct = True

            for i in range(start, n):
                if nums[i] in seen:
                    distinct = False
                    break
                seen.add(nums[i])

            if distinct:
                return operations

            operations += 1

The implementation follows the algorithm directly.

The variable operations tracks how many removal operations have been performed. From this, we compute the suffix starting index using operations * 3.

For each suffix, we use a hash set called seen to detect duplicates efficiently. As we iterate through the remaining elements:

If the current number is already in seen, duplicates exist.
Otherwise, we add the number to the set.

If we finish scanning the suffix without finding duplicates, we immediately return the current operation count.

The loop is guaranteed to terminate because eventually the suffix becomes empty, and an empty array always satisfies the distinct condition.

Go Solution

func minimumOperations(nums []int) int {
    n := len(nums)
    operations := 0

    for {
        start := operations * 3
        seen := make(map[int]bool)
        distinct := true

        for i := start; i < n; i++ {
            if seen[nums[i]] {
                distinct = false
                break
            }
            seen[nums[i]] = true
        }

        if distinct {
            return operations
        }

        operations++
    }
}

The Go implementation mirrors the Python logic closely.

Instead of Python's set, Go uses a map[int]bool to track seen values. The rest of the algorithm remains identical.

Go slices naturally handle cases where start >= n, because the inner loop simply does not execute, correctly treating the remaining suffix as empty and therefore distinct.

Integer overflow is not a concern because the input size is extremely small.

Worked Examples

Example 1

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

Initial state:

Operations	Start Index	Remaining Suffix	Distinct?
0	0	[1,2,3,4,2,3,3,5,7]	No

Duplicate detection:

1 added
2 added
3 added
4 added
2 already exists, duplicate found

Try one operation:

Operations	Start Index	Remaining Suffix	Distinct?
1	3	[4,2,3,3,5,7]	No

Duplicate detection:

4 added
2 added
3 added
next 3 is duplicate

Try two operations:

Operations	Start Index	Remaining Suffix	Distinct?
2	6	[3,5,7]	Yes

All values are unique, so the answer is:

Example 2

nums = [4,5,6,4,4]

Operations	Start Index	Remaining Suffix	Distinct?
0	0	[4,5,6,4,4]	No
1	3	[4,4]	No
2	6	[]	Yes

After two operations, the array becomes empty, which is considered distinct.

Answer:

Example 3

nums = [6,7,8,9]

Operations	Start Index	Remaining Suffix	Distinct?
0	0	[6,7,8,9]	Yes

The original array already contains distinct elements.

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Up to O(n/3) suffix checks, each scanning up to O(n) elements
Space	O(n)	Hash set stores at most all remaining elements

The algorithm repeatedly checks suffixes for duplicates. In the worst case, we may test several suffixes, and each test scans much of the array.

Because n <= 100, this complexity is easily fast enough.

The extra space comes from the hash set used for duplicate detection.

Test Cases

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        operations = 0

        while True:
            start = operations * 3
            seen = set()
            distinct = True

            for i in range(start, n):
                if nums[i] in seen:
                    distinct = False
                    break
                seen.add(nums[i])

            if distinct:
                return operations

            operations += 1

sol = Solution()

assert sol.minimumOperations([1,2,3,4,2,3,3,5,7]) == 2  # example 1
assert sol.minimumOperations([4,5,6,4,4]) == 2  # example 2
assert sol.minimumOperations([6,7,8,9]) == 0  # already distinct

assert sol.minimumOperations([1]) == 0  # single element
assert sol.minimumOperations([2,2]) == 1  # remove all remaining elements
assert sol.minimumOperations([1,2,1]) == 1  # one operation clears array
assert sol.minimumOperations([1,2,3]) == 0  # already distinct length 3
assert sol.minimumOperations([1,1,1,1]) == 1  # remaining suffix becomes distinct
assert sol.minimumOperations([5,5,5,5,5,5]) == 2  # requires removing entire array
assert sol.minimumOperations([1,2,3,4,5,6]) == 0  # all unique larger input
assert sol.minimumOperations([1,2,3,1,2,3]) == 1  # suffix after one removal is distinct

Test	Why
`[1,2,3,4,2,3,3,5,7]`	Validates repeated removals
`[4,5,6,4,4]`	Validates removing entire array
`[6,7,8,9]`	Already distinct case
`[1]`	Minimum array size
`[2,2]`	Short array with duplicates
`[1,2,1]`	Duplicate in small array
`[1,2,3]`	Distinct array of size 3
`[1,1,1,1]`	Duplicate-heavy input
`[5,5,5,5,5,5]`	Requires complete removal
`[1,2,3,4,5,6]`	Larger already-distinct array
`[1,2,3,1,2,3]`	Distinct suffix appears after one operation

Edge Cases

Array Already Distinct

An important edge case occurs when the original array already contains unique values. A buggy implementation might unnecessarily perform removals before checking the initial state.

For example:

[6,7,8,9]

The algorithm correctly checks the original suffix first, using operations = 0, and immediately returns 0.

Array Smaller Than Three Elements

Arrays with fewer than 3 elements can be tricky because one operation removes everything.

For example:

[2,2]

After one operation, the array becomes empty. Since an empty array is considered distinct, the correct answer is 1.

The implementation naturally handles this because once start >= n, the loop checking duplicates does not execute, and the suffix is treated as distinct.

Duplicate Values Remaining Near the End

Another subtle case occurs when duplicates remain even after most of the array has been removed.

For example:

[4,5,6,4,4]

After removing the first three elements, the remaining suffix is [4,4], which still contains duplicates. The algorithm must continue rather than stopping early.

The implementation correctly keeps testing larger starting indices until the suffix becomes distinct, eventually reaching the empty array.