Algorithms
Medium
2870
3094
Minimum Number of Operations to Make Array Empty
minimum-number-of-operations-to-make-array-empty
"""
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.

Example 2:

Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.


Constraints:

 * 2 <= nums.length <= 105
 * 1 <= nums[i] <= 106
"""
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        
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.

Example 2:

Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.


Constraints:

 * 2 <= nums.length <= 105
 * 1 <= nums[i] <= 106


Please complete the code below to solve above prblem:
```python
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [2,3,3,2,2,4,2,3,4] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [2,1,2,2,3,3] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [3,3] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [14,12,14,14,12,14,14,12,12,12,12,14,14,12,14,14,14,12,12] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [2,2,2,2,2,2,2,2,2] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [15,3,3,15,15,13,8,15,6,15,3,1,8,8,15] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [19,19,19,19,19,19,19,19,19,19,19,19,19] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [13,7,13,7,13,7,13,13,7] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [5,5] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [3,14,3,14,3,14,14,3,3,14,14,14,3,14,14,3,14,14,14,3] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [16,16,16,19,16,3,16,8,16,16,16,19,3,16,16] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [11,11,11,11,19,11,11,11,11,11,19,11,11,11,11,11,19] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [1,1,1,5,1,5,1,1,1,1,1,1,1] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [16,16,16,3,16,16,3] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [14,4,4,19,19] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [1,14,1,1,1] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [3,10,11,3,3,11,3,3,3,3,3,3,3,3,10,3,3,3] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [3,8,8,8,8,3,8,8,8,8,8,8,8,8] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [9,9,9] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [6,6,6,6,6,8,8,8,8,6,8,6,15,15,6,15,6,6] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [9,19,19,19,9,9,19,19,19,9,9,19,9,19,19,19] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [9,4,9,20,20,4,20] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [6,9,18,16,18,1,9,1,1,1,1,16,1,6,1,1,9,6] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [11,18,11,18,11,18,11] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [20,20,20,20,20] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [12,7,7] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [10,7,9,9,10,9,9,10,10,9,10,9,10,10] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [9,9,9,8,9,9,9,9,2,9,9,9,9,9] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [5,5,18,1,5,5] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [13,13,16,4,16,13,2,16,16,16,2,16,6,16,13,18,9] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [8,8,8,8,8,8,8,8,8,7,8,8,8,8,8,7,8] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [20,20,19,19,20,19,20,20,20,19,20,20,20,20,20,20,20,20,20] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [4,4,20,20,4,20,1,4,4,4,4,4,4,4,20,4,4] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [16,17,17,8,17,17,16,8,17,16,17] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [10,10,10,9,10,10,10,9,10,18,10,4,20,2,10,10] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [11,20,20,11,11,20,14,20,11,11,20,1] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [14,14,14,14,15,20,15] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [17,7,17,5,17,17,17,7,17,17,17,17,5,17,17,7,5] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [4,4,4,4,4,4,4,4,4] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [17,17] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [15,2,15,2,8,15,15,15,15,15,15,8,2] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [1,12,12,1,1,1,1,12,1] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [12,4,9,10,17,12,5,17,4,12,12,12,4,10,4] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [7,7,7,7,7,7,7,16,7,7,7,16,7,16,7,16,16,16,16,7] }
assert my_solution.minOperations(**test_input) == 8

test_input = { "nums": [20,20,20,20,19] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [13,13,13,13,13,13,13,13] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [15,12,18,18,15,15,15,12,12,12,12,12,12,15,18] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [14,14,14,1] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [2,2,2,2,2,2,8,2,8,2,2,2,2] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [10,16,6,6,10,6] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [18,17,3,18,6,13,3,6,14,6,15,3] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [15,15] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [9,9,9,9,9,9,9,9,9,9,9] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [11,4,4,18,11,12,18,18,12,4,4,12,4] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [2,5,20,20,5,20,20,16,20,20,20,20,20,20,3,20,20,20] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [12,13,13,13,12,13,13,13,13,13,11,13,13,13] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [1,1,1,1] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [10,10,10,10,3,10,10,3,10] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [7,14,7,7,2,2,7] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [1,10,1,10,1] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [11,11,11,11,11,11,11,11,11,11] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [13,13,13,13,13,13,13] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [19,19,19,19,18,19,15,7,19,19,15,5] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [2,12,12,12,17,12,12,12,12,12,12,12,12,12,12] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [19,16,19,19,16,16,16,16] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [15,15,15,15,15,15,11,13,15,15,11,15,13,15,11,13] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [15,16,16,15,16] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [9,7,14,9,14,7,7,9,9,9,9,9,9,14,14] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [12,16,5,5,7,10,2,16,12,7,2,12,5,16,2,11] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [18,13,13,18,18,13,13,18,13,13] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [4,4,8,10,8,10,19,19,19,19,8,8,19,4] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [1,18,14,16,14] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [7,7,7,7,3,7,7,3,7,7] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [13,13] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [6,11,6,8,6,13,17,14] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [10,2,2,10] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [19,17,17,17,17,17,17,17,19,19,19,17,19,17] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [4,16,12,7,16,16,16] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [11,11,11,11,11,11,11,11,11,11,11,11,11,11,11] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [6,6,6,13,6,18,13,18,5,18,12,3,12,12,18,6,18,3,18,6] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [4,4,3,3,4,4] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [11,11,11,11,9,11,9,9,11,11,9,9,11,11,9] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [16,16] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [4,4,4,4,4,4,4,4,4,4,4,4,4,4] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [17,16,16,17,16,16,16] }
assert my_solution.minOperations(**test_input) == 3

test_input = { "nums": [10,18,10,10] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [8,8] }
assert my_solution.minOperations(**test_input) == 1

test_input = { "nums": [8,6,6,6,8,8,6,8,8,6,8,6,8,8,6,6,6,8] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [15,14,20,15,20,14,14,14,20,14,20,20] }
assert my_solution.minOperations(**test_input) == 5

test_input = { "nums": [19,3,3,3,3,3,3,15,17,3,3,18,10,17,17,15,17,3,3] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [1,1,16,2,16,1,2,2,2,2,2,1,2,2,2,16] }
assert my_solution.minOperations(**test_input) == 6

test_input = { "nums": [1,1,4,4,4] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] }
assert my_solution.minOperations(**test_input) == 7

test_input = { "nums": [16,18,18,20] }
assert my_solution.minOperations(**test_input) == -1

test_input = { "nums": [2,2,2,20,15,2,20,15,2,15] }
assert my_solution.minOperations(**test_input) == 4

test_input = { "nums": [16,16,16,16,16] }
assert my_solution.minOperations(**test_input) == 2

test_input = { "nums": [1,14,14,14,14,1,14,14,1,14,14,14,14,1,14,14,1,14] }
assert my_solution.minOperations(**test_input) == 7