Problem Informations

• Problem Index: 3396
• Problem Link: Minimum Number of Operations to Make Elements in Array Distinct
• Topics: Array, Hash Table

Problem 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 \leq nums.length \leq 100$
• $1 \leq nums[i] \leq 100$

Intuition

The problem requires making all elements in the array distinct by removing three elements from the start of the array until no duplicates remain. The challenge is to determine the minimum number of such operations required. Intuitively, if we encounter a duplicate, we might already have performed enough removals that guarantee subsequent duplicates won’t affect the distinct nature of the remaining array. Hence, if we find a duplicate while iterating through the array from the end to the beginning, the operations to reach that point give us the result.

Approach

The approach involves using a boolean vector to track numbers that have already appeared as we iterate through the input array nums from back to front. Here’s a detailed step-by-step explanation of the algorithm:

1. Initialization: Create a boolean vector isPresent of size 105 initialized to false. This vector serves to mark which numbers have been encountered, taking advantage of the problem constraint that numbers in nums range between 1 and 100.

2. Iterate Backwards: Start traversing the array nums from the last element to the first. This reverse traversal allows us to determine the last position of any duplicate quickly.

3. Check Presence: For each element, check if it has already been marked as present in isPresent. If it is, this means a duplicate element has been found.

4. Calculate Operations: Upon finding a duplicate, calculate the minimum operations required to make the array distinct by using the formula i / 3 + 1, where i is the current index position from the end. The division by 3 accounts for the number of three-element removals needed to reach that index, with the +1 signifying the operation in progress.

5. Mark Element: If the number is not a duplicate, mark it in isPresent as seen, and continue to the next element.

6. Return Zero: If all elements are traversed without encountering a duplicate, this means the array is already distinct from the start, and no operations are needed. Hence, return 0.

By employing this reverse iteration strategy, the algorithm efficiently calculates the minimum number of operations without needing to modify the array multiple times, ensuring an optimal solution.

Code

C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        // Create a boolean vector to track the existence of numbers in the array.
        // The size is set to 105 to cover the possible range of numbers [1, 100].
        vector<bool> isPresent(105, false);

        // Traverse the array from the end to the beginning.
        for (int i = nums.size() - 1; i >= 0; i--) {
            // If the number is already seen, calculate and return the number of operations.
            if (isPresent[nums[i]]) {
                return i / 3 + 1;
            }
            // Mark the number as seen.
            isPresent[nums[i]] = true;
        }

        // If all elements are distinct, no operations are needed.
        return 0;
    }
};

Python

class Solution:
    def minimumOperations(self, nums):
        # Create a boolean list to track the existence of numbers in the array.
        # The size is set to 105 to cover the possible range of numbers [1, 100].
        isPresent = [False] * 105

        # Traverse the array from the end to the beginning.
        for i in range(len(nums) - 1, -1, -1):
            # If the number is already seen, calculate and return the number of operations.
            if isPresent[nums[i]]:
                return i // 3 + 1
            # Mark the number as seen.
            isPresent[nums[i]] = True

        # If all elements are distinct, no operations are needed.
        return 0

Complexity

• Time complexity: The time complexity of the given algorithm is $O(n)$, where $n$ is the length of the array nums. This is because the algorithm iterates through the nums array once from the last element to the first element, checking and marking each element in the isPresent vector. The processing within each iteration (checking and marking an element) takes constant time, resulting in an overall time complexity of $O(n)$.

• Space complexity: The space complexity is $O(1)$. This is because the additional space used by the algorithm does not depend on the input size, n. The vector isPresent is a fixed-size vector of length 105, which is independent of the size of nums. Hence, the space complexity is constant, or $O(1)$.