Minimum Number of Operations to Make Array Empty — LeetCode 2870 Python Solution

The problem

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.

Example

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:

Python solution

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        count = Counter(nums)
        ans = 0
        for c in count.values():
            if c == 1:
                return -1
            ans += (c + 2) // 3
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2870. Minimum Number of Operations to Make Array Empty is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems