3779. Minimum Number of Operations to Have Distinct Elements

MediumArrayHash Table

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Using a hash set while scanning from right to left finds the earliest duplicate, determining how many front elements to remove.

Open in Flowchart

Intuition

The process described in the problem keeps removing the first three elements until the remaining array has no duplicates. A natural question is: at which point does the array finally become duplicate-free?

Notice that each operation removes elements from the front of the array, so the array is always a suffix of the original nums. This means the final duplicate-free array must be some suffix nums[k..]. Our goal is to find the smallest prefix that we need to remove so that the rest of the array contains only distinct values.

To find this point efficiently, we can think about it from the end of the array. If we scan from right to left and collect elements into a set, the first time we encounter a value that is already in the set, we know this is the last position that causes a duplicate. Let this position be index i. Everything from nums[0..i] must be removed to guarantee that the remaining elements are all distinct.

Since each operation removes exactly three elements (or fewer at the very end), removing the first i + 1 elements requires ⌊i / 3⌋ + 1 operations. We add 1 because the operation count is rounded up — even a single leftover element requires one full operation.

If we finish scanning the entire array without finding any duplicate, then nums is already distinct from the start, so the answer is simply 0.

Solution Approach

Solution 1: Hash Table + Reverse Traversal

We traverse the array nums in reverse order and use a hash table st to record the elements we have already seen.

The steps are as follows:

Initialize an empty hash set st.
Iterate over the indices i from len(nums) - 1 down to 0:
- If nums[i] is already in the hash table st, it means a duplicate exists, and all elements in nums[0..i] must be removed. The number of operations required is ⌊i / 3⌋ + 1, so we return this value immediately.
- Otherwise, add nums[i] to the hash table st and continue to the next element.
If the traversal completes without finding any duplicate, then all elements in the array are already distinct, no operations are needed, and we return 0.

The reason reverse traversal works is that the first duplicate we hit from the right marks the boundary index i — every element before and including i must be discarded to make the suffix duplicate-free. Dividing i by 3 (integer division) and adding 1 converts the count of removed elements into the number of three-element operations.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums. The hash table stores at most n distinct elements, and we make a single pass over the array.

Example Walkthrough

Let's trace through the solution with a small example: nums = [4, 11, 2, 2, 5, 4].

Goal: Find the smallest prefix we must remove so that the remaining suffix contains only distinct values, then convert that into a count of three-element operations.

Step 1 — Set up the reverse scan.

We initialize an empty hash set st = {} and walk from the last index down to the first. The intuition is that the rightmost duplicate we encounter marks the boundary: everything at or before that index has to go.

Step 2 — Iterate from right to left.

Step	Index `i`	`nums[i]`	Already in `st`?	Action
1	5	4	No	Add `4` → `st = {4}`
2	4	5	No	Add `5` → `st = {4, 5}`
3	3	2	No	Add `2` → `st = {4, 5, 2}`
4	2	2	Yes	Duplicate found at `i = 2`! Stop here.

Step 3 — Interpret the boundary.

At i = 2, the value 2 is already in st (we saw the second 2 at index 3). This tells us the suffix nums[3..] = [2, 5, 4] is fully distinct, but nums[0..2] = [4, 11, 2] must be removed to eliminate the duplicate 2.

Step 4 — Convert removed elements into operations.

We need to remove the first i + 1 = 3 elements. Each operation strips three elements from the front, so:

⌊i / 3⌋ + 1 = ⌊2 / 3⌋ + 1 = 0 + 1 = 1

Result: 1 operation.

Verification by simulation:

Start: [4, 11, 2, 2, 5, 4] — contains duplicates (2 and 4).
Operation 1: remove first three → [2, 5, 4] — all distinct. Stop.

The simulation confirms exactly 1 operation, matching our formula.

A quick second example to show the rounding: suppose the boundary index were i = 3 (meaning the first 4 elements must be removed). Then ⌊3 / 3⌋ + 1 = 1 + 1 = 2 operations — the first operation clears three elements, and a second operation is still required to clear that single leftover element, which is why we always add 1.

Solution Implementation

1class Solution:
2    def minOperations(self, nums: List[int]) -> int:
3        # Track distinct values encountered while scanning from the right.
4        seen_values = set()
5
6        # Iterate from the last index back to the first.
7        for index in range(len(nums) - 1, -1, -1):
8            current_value = nums[index]
9
10            # A duplicate means the prefix up to (and including) this index
11            # must be removed. Removing in groups of 3 elements from the front,
12            # the number of operations needed is (index // 3) + 1.
13            if current_value in seen_values:
14                return index // 3 + 1
15
16            # Record the value as seen.
17            seen_values.add(current_value)
18
19        # No duplicates found; the array is already valid, so no operations needed.
20        return 0
21

1class Solution {
2    /**
3     * Returns the minimum number of operations needed so that the array
4     * contains only distinct elements.
5     *
6     * Each operation removes the first 3 elements from the array (or all
7     * remaining elements if fewer than 3 are left). We scan from the end of
8     * the array toward the front, collecting seen values into a set. As soon
9     * as we encounter a duplicate at index i, every element from index 0..i
10     * must be removed, because the duplicate proves the prefix is not yet
11     * all-distinct. Removing that prefix takes ceil((i + 1) / 3) operations,
12     * which equals i / 3 + 1 using integer arithmetic.
13     */
14    public int minOperations(int[] nums) {
15        // Tracks values seen so far while scanning from right to left.
16        Set<Integer> seen = new HashSet<>();
17
18        // Walk backward through the array.
19        for (int i = nums.length - 1; i >= 0; --i) {
20            // add() returns false if the value is already present (a duplicate).
21            if (!seen.add(nums[i])) {
22                // The prefix nums[0..i] must be removed; compute operation count.
23                return i / 3 + 1;
24            }
25        }
26
27        // No duplicates found, so no operations are required.
28        return 0;
29    }
30}
31

1class Solution {
2public:
3    int minOperations(vector<int>& nums) {
4        // Track distinct elements we have seen so far while scanning from the end
5        unordered_set<int> seen;
6
7        // Iterate backwards; '~i' is true while i >= 0 (equivalent to i != -1)
8        for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
9            // If the current value already appeared later in the array,
10            // there is a duplicate that must be removed.
11            if (seen.contains(nums[i])) {
12                // Elements are removed 3 at a time from the front.
13                // Everything up to and including index i must be cleared,
14                // which requires ceil((i + 1) / 3) operations = i / 3 + 1.
15                return i / 3 + 1;
16            }
17
18            // Record the current value as seen.
19            seen.insert(nums[i]);
20        }
21
22        // No duplicates found; the array already contains all unique elements.
23        return 0;
24    }
25};
26

1/**
2 * Returns the minimum number of operations to make all array elements distinct.
3 * Each operation removes the first 3 elements (or all remaining if fewer than 3).
4 *
5 * @param nums - The input array of numbers.
6 * @returns The minimum number of operations required.
7 */
8function minOperations(nums: number[]): number {
9    // Set to track values seen while scanning from the end of the array.
10    const seen = new Set<number>();
11
12    // Traverse the array from right to left.
13    for (let i = nums.length - 1; i >= 0; i--) {
14        // If the current value already exists in the suffix, a duplicate is found.
15        // Everything from index 0 to i must be removed in groups of 3.
16        if (seen.has(nums[i])) {
17            // Number of operations: ceil((i + 1) / 3) == floor(i / 3) + 1.
18            return Math.floor(i / 3) + 1;
19        }
20
21        // Record the current value as seen.
22        seen.add(nums[i]);
23    }
24
25    // No duplicates found; the array is already distinct.
26    return 0;
27}
28

Time and Space Complexity

Time Complexity: O(n). The code iterates through the array nums from the end to the beginning in a single loop. In the worst case (when no duplicate is found early), it traverses all n elements once. Each iteration performs a membership check (nums[i] in st) and an insertion (st.add(nums[i])) into the set, both of which take O(1) on average. Therefore, the overall time complexity is O(n), where n is the length of the array nums.
Space Complexity: O(n). A set st is used to store the elements encountered during the traversal. In the worst case (when all elements are distinct), the set will hold up to n elements. Thus, the space complexity is O(n), where n is the length of the array nums.

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

Common Pitfalls

Pitfall 1: Misinterpreting the Boundary Index When Computing Operations

The most frequent mistake is getting the arithmetic wrong when converting the duplicate's index into the number of operations. Many people write index // 3 (forgetting the + 1) or use (index + 1) // 3 (treating it as "count of elements" rather than "an index that must be removed").

Why it's wrong: When a duplicate is found at index, all elements in nums[0..index] (inclusive) must be removed. That is index + 1 elements. Each operation removes exactly 3 elements (or fewer for the last partial group). The number of operations to remove the prefix is therefore:

$\left\lceil \frac{\text{index} + 1}{3} \right\rceil = \left\lfloor \frac{\text{index}}{3} \right\rfloor + 1$

The identity ⌈(i+1)/3⌉ = ⌊i/3⌋ + 1 holds for all non-negative integers i, which is exactly what the code uses.

Verification with concrete cases:

index	elements to remove (`index+1`)	correct ops	`index // 3 + 1`
0	1	1	1 ✓
2	3	1	1 ✓
3	4	2	2 ✓
5	6	2	2 ✓
6	7	3	3 ✓

Solution: Either trust the identity index // 3 + 1, or write the more self-documenting ceiling form to avoid confusion:

if current_value in seen_values:
    elements_to_remove = index + 1
    return (elements_to_remove + 2) // 3  # ceiling division

Pitfall 2: Misunderstanding Which Duplicate Stops the Scan (Direction Matters)

A subtle trap is reasoning about the problem with a left-to-right scan and stopping at the first duplicate found from the left. That gives the wrong answer because the goal is to find the largest boundary index that still has a duplicate behind it — equivalently, the position of the rightmost element whose value reappears later.

By scanning right-to-left, the first duplicate we encounter is the rightmost index i such that nums[i] equals some element in the suffix nums[i+1..]. Everything from 0 to i must go; the suffix after i is guaranteed distinct (because we only added distinct values to the set as we moved left). This is precisely the minimal prefix that must be removed.

Solution: Keep the reverse-traversal invariant intact. Do not convert this into a forward scan that returns on the first collision, and do not break early in a way that leaves a duplicate untracked in the suffix.

Pitfall 3: Returning `0` vs. Looping the Operation Manually

Some implementations literally simulate the process — slicing off three elements at a time and rebuilding a set each round — which is O(n²) in the worst case and risks off-by-one errors in the loop termination condition (empty array vs. no-duplicates condition).

Solution: The hash-set approach collapses the entire simulation into a single O(n) pass. Recognize that the answer depends only on the position of the last duplicate, so there is no need to actually mutate or slice the array.

Pitfall 4: Edge Cases — Empty or All-Distinct Arrays

Forgetting to handle the case where no duplicate exists leads to either a missing return 0 (falling off the function and implicitly returning None) or an incorrect non-zero answer.

Solution: Ensure the loop's fall-through explicitly returns 0. This correctly covers both the empty array (the loop body never executes) and the fully-distinct array (the loop completes without returning early).

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering