LeetCode 3396: Minimum Number of Operations to Make Elements in Array Distinct

 

Problem Description

You are given an integer array nums. The goal is to ensure all elements in the array are distinct. To achieve this, you can perform the following operation any number of times:

• Remove the first three elements from the array. If the array has fewer than three elements, remove all remaining elements.

Note: An empty array is considered to have distinct elements.

The task is to return the minimum number of operations required to make the array distinct.

Examples

Example 1

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

• Output: 2

• Explanation:

  1. Remove the first three elements: [4, 2, 3, 3, 5, 7]

  2. Remove the next three elements: [3, 5, 7], which is now distinct.

Example 2

• Input: nums = [4,5,6,4,4]

• Output: 2

• Explanation:

  1. Remove the first three elements: [4, 4]

  2. Remove the remaining elements to get an empty array.

Example 3

• Input: nums = [6,7,8,9]

• Output: 0

• Explanation: The array is already distinct, so no operations are needed.

Solution Approach

The goal is to determine the minimum number of operations needed to make the array distinct. Here's how we can achieve this:

Key Observations

1. If the array is already distinct, no operations are needed.

2. Duplicate elements must be removed to make the array distinct.

3. We are given a specific operation—removing the first three elements—which we can leverage to solve the problem efficiently.

Steps to Solve this problem

1. Track duplicate elements:

   • Use an auxiliary array temp of size 101 (since the values in nums are between 1 and 100) to count occurrences of each element as we traverse the array.

2. Find the last index where a duplicate occurs:

   • Traverse the array from right to left.

   • Use the temp array to track if a number has already been seen. If we encounter a duplicate, mark the index where duplicates end.

3. Calculate the required operations:

• The number of operations is determined by how many elements are part of the array up to the last_index. Divide last_index by 3 to determine the number of operations, and add 1 if there are leftover elements.

C++ Implementation

Below is the C++ code for this approach:

class Solution {
public:
    int minimumOperations(vector<int>& nums)
    {
        vector<int> temp(101, 0); // Array to track occurrences of elements
        int last_index = 0;

        // Traverse from right to left to find duplicates
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (temp[nums[i]] > 0) { // Duplicate found
                last_index = i + 1; // Update the last index
                break;
            }
            temp[nums[i]]++; // Mark the element as seen
        }

        // Calculate the number of operations
        if (last_index % 3 == 0) {
            return last_index / 3;
        } else {
            return last_index / 3 + 1;
        }
    }
};

---

Detailed Explanation of the above Code

Let’s break down the code:

1. Initialization:

   vector<int> temp(101, 0); // Array to track occurrences of elements
   int last_index = 0;

   • temp is an array of size 101 to keep track of whether a number has been seen before.

   • last_index keeps track of the position where duplicates end.

2. Finding Duplicates:

   for (int i = nums.size() - 1; i >= 0; i--) {
       if (temp[nums[i]] > 0) { // Duplicate found
           last_index = i + 1; // Update the last index
           break;
       }
       temp[nums[i]]++; // Mark the element as seen
   }

   • Traverse the array from right to left.

   • Use the temp array to check if an element has already been encountered. If yes, update last_index and break out of the loop.

3. Calculating Operations:

   if (last_index % 3 == 0) {
       return last_index / 3;
   } else {
       return last_index / 3 + 1;
   }

   • Divide last_index by 3 to determine how many operations are needed.

   • If there are leftover elements, add one additional operation.

---

Complexity Analysis

Time Complexity

• Traversing the Array: The loop runs once from right to left, which is O(n).

• Updating the Temp Array: Each update in the temp array is (1).

• Overall: O(n) , where is the length of the input array.

Space Complexity

• Temp Array: We use a fixed-size array of size 101, which is O(1).

• Overall: O(1).

---

Example

Let’s walk through Example 1 step by step:

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

1. Traverse the array from right to left, updating the temp array:

   • At i = 8: temp[7]++

   • At i = 7: temp[5]++

   • At i = 6: temp[3]++

   • At i = 5: temp[3] > 0, so last_index = 6 and break.

2. Calculate operations:

   • last_index = 6

   • Operations = 2

Output: 2