README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3396.Minimum%20Number%20of%20Operations%20to%20Make%20Elements%20in%20Array%20Distinct/README_EN.md	1299	Weekly Contest 429 Q1	Array Hash Table

3396. Minimum Number of Operations to Make Elements in Array Distinct

中文文档

Description

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

Solutions

Solution 1: Hash Table + Reverse Traversal

We can traverse the array $\textit{nums}$ in reverse order and use a hash table $\textit{s}$ to record the elements that have already been traversed. When we encounter an element $\textit{nums}[i]$, if $\textit{nums}[i]$ is already in the hash table $\textit{s}$, it means we need to remove all elements from $\textit{nums}[0..i]$. The number of operations required is $\left\lfloor \frac{i}{3} \right\rfloor + 1$. Otherwise, we add $\textit{nums}[i]$ to the hash table $\textit{s}$ and continue to the next element.

After traversing, if no duplicate elements are found, the elements in the array are already distinct, and no operations are needed, so the answer is $0$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.

Python3

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

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

C++

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

Go

func minimumOperations(nums []int) int {
	s := map[int]bool{}
	for i := len(nums) - 1; i >= 0; i-- {
		if s[nums[i]] {
			return i/3 + 1
		}
		s[nums[i]] = true
	}
	return 0
}

TypeScript

function minimumOperations(nums: number[]): number {
    const s = new Set<number>();
    for (let i = nums.length - 1; ~i; --i) {
        if (s.has(nums[i])) {
            return Math.ceil((i + 1) / 3);
        }
        s.add(nums[i]);
    }
    return 0;
}