Leetcode 2879 Solution

2870. Minimum number of Operations to make Array Empty

#Medium #Hash #Quotient_remain

You are given a 0-indexed array nums consisting of positive integers.

There are two types of operations that you can apply on the array any number of times:

Choose two elements with equal values and delete them from the array.
Choose three elements with equal values and delete them from the array.

Return the minimum number of operations required to make the array empty, or -1 if it is not possible.

Example 1:

• Input: nums = [2,3,3,2,2,4,2,3,4]
• Output: 4
• Explanation: We can apply the following operations to make the array empty:
  • Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4].
  • Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4].
  • Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4].
  • Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = [].
    It can be shown that we cannot make the array empty in less than 4 operations.

python

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        count_dict = Counter(nums)
        op = 0
        for k,v in count_dict.items():
            if v == 1:
                return -1
            op += v // 3
            if v % 3:
                op += 1
        return op

The main idea of this problem algorithm is that except the number only appeared once, every number can be divided to 3. And the left is 2, so all you need to do is adding 1.

That's all. But the idea is quite not easy to come up with. Use hash table and easy add