Minimum Number of Operations to Make Elements in Array Distinct

Leetcode Problem:

• Minimum Number of Operations to Make Elements in Array Distinct

Summary

• The problem is to find the minimum number of operations needed to make the elements in the array distinct
• The operation allowed is to remove 3 elements from the beginning of the array
• The goal is to return the minimum number of operations required to make all elements in the array distinct.

Approach

• The approach used is to first count the occurrences of each number in the array
• Then, if a number occurs more than once, we find the last occurrence of that number and calculate the minimum number of operations required to remove all occurrences of that number
• The minimum number of operations is calculated by dividing the last occurrence index by 3 and adding 1.

Complexity

• O(n) where n is the size of the array, because we are scanning the array once to count the occurrences of each number.

Explanation

• The code first initializes a count array `numberCnt` to keep track of the occurrences of each number in the array
• It then scans the array from the end to the beginning and increments the count of each number in the `numberCnt` array
• If a number occurs more than once, it updates the `lastIdx` variable to the last occurrence index of that number
• Finally, it calculates the minimum number of operations required by dividing the `lastIdx` by 3 and adding 1, and returns this value.

Solution Code:

class Solution {
public:
    int numberCnt[101];
    int minimumOperations(vector& nums) {
        int lastIdx = -1;
        for(int i = nums.size() - 1 ; i >= 0 ; i--){
            numberCnt[nums[i]]++;
            if(numberCnt[nums[i]] >= 2){
                lastIdx = i;
                break;
            }
        }
        if(lastIdx == -1) return 0;
        return lastIdx / 3 + 1;
    }
};