3396. Minimum-Number-Of-Operations-To-Make-Elements-In-Array-Distinct

This one was a bit tricky to understand at first, especially for an easy problem.

The hint gives a ‘suggestion’ saying the problem space is so small that a brute force approach is viable.

So my initial solution was just to iterate through the numbers in steps of 3 and check if the remaining numbers were distinct. Then I would return the number of iterations I had to do.

class Solution(object):
    def minimumOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def check_unique(start):
            seen = set()
            for num in nums[start:]:
                if num in seen:
                    return False
                seen.add(num)
            return True

        res = 0
        for i in range(0, len(nums), 3):
            if check_unique(i):
                return res
            res += 1
        return res

However, I realized that there is a much simpler solution which is to iterate backwards. We can iterate through the array backwards until we hit a number that we have already seen. Then we know that we want to remove the length 3 subset that includes that number.

We are able to easily calculate the number of iterations we need to remove that number by taking the index and dividing it by 3. If we get through the entire list without finding a duplicate number, we can simply return 0.

class Solution(object):
    def minimumOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        seen = set()
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] in seen:
                return i // 3 + 1
            seen.add(nums[i])

        return 0

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 11m 44s