# Minimum Number of Operations to Make Elements in Array Distinct
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-elements-in-array-distinct)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-elements-in-array-distinct
**Data structures:** Array, Hash Table
---
## Problem
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 <= 100`
* `1 <= nums[i] <= 100`

# Approaches
## Brute Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `startIndex` is greater than or equal to the array length, it means the array becomes empty. An empty array is distinct, so we return `ops`.
*   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 `ops` for which the remaining subarray is distinct is our answer.

## Optimized Single-Pass Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `HashSet` to store elements of the current suffix being examined.
*   Iterate from `i = nums.length - 1` down to `0`.
*   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 index `i + 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 is `ceil(k / 3)`, which can be calculated with integer arithmetic as `(k + 2) / 3`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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 0

```

### CPP

```cpp
class 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;
  }
};

```