Skip to content

3779. Minimum Number of Operations to Have Distinct Elements

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.

 

Example 1:

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

Output: 1

Explanation:

In the first operation, we remove the first three elements. The remaining elements [6, 5, 8] are all distinct, so we stop. Only one operation is needed.

Example 2:

Input: nums = [2,2]

Output: 1

Explanation:

After one operation, the array becomes empty, which meets the stopping condition.

Example 3:

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

Output: 0

Explanation:

All elements in the array are distinct, therefore no operations are needed.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Hash Table + Reverse Traversal

We can traverse the array \(\textit{nums}\) in reverse order and use a hash table \(\textit{st}\) to record the elements we have already traversed. When we traverse to element \(\textit{nums}[i]\), if \(\textit{nums}[i]\) is already in the hash table \(\textit{st}\), it means we need to remove all elements in \(\textit{nums}[0..i]\), and 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{st}\) and continue to traverse the next element.

After the traversal is complete, if no duplicate elements are found, then all elements in the array are already distinct, no operations are needed, and the answer is \(0\).

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

1
2
3
4
5
6
7
8
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        st = set()
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] in st:
                return i // 3 + 1
            st.add(nums[i])
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minOperations(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for (int i = nums.length - 1; i >= 0; --i) {
            if (!st.add(nums[i])) {
                return i / 3 + 1;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_set<int> st;
        for (int i = nums.size() - 1; ~i; --i) {
            if (st.contains(nums[i])) {
                return i / 3 + 1;
            }
            st.insert(nums[i]);
        }
        return 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func minOperations(nums []int) int {
    st := make(map[int]struct{})
    for i := len(nums) - 1; i >= 0; i-- {
        if _, ok := st[nums[i]]; ok {
            return i/3 + 1
        }
        st[nums[i]] = struct{}{}
    }
    return 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function minOperations(nums: number[]): number {
    const st = new Set<number>();
    for (let i = nums.length - 1; i >= 0; i--) {
        if (st.has(nums[i])) {
            return Math.floor(i / 3) + 1;
        }
        st.add(nums[i]);
    }
    return 0;
}

Comments