2870. Minimum Numbers of Operations to Make Array Empty - Explanation

Description

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 <= 100,000
1 <= nums[i] <= 1,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        def dfs(cur):
            if cur < 0:
                return float('inf')
            if cur == 0:
                return 0

            ops = min(dfs(cur - 2), dfs(cur - 3))
            return 1 + ops

        count = Counter(nums)
        res = 0
        for num, cnt in count.items():
            op = dfs(cnt)
            if op == float("inf"):
                return -1
            res += op

        return res

Time & Space Complexity

Time complexity: $O(n * 2 ^ m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums$ and $m$ is the average frequency of the array elements.

2. Dynamic Programming (Top-Down)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        cache = {}

        def dfs(num):
            if num < 0:
                return float("inf")
            if num in [2, 3]:
                return 1
            if num in cache:
                return cache[num]

            res = min(dfs(num - 2), dfs(num - 3))
            cache[num] = res + 1
            return cache[num]

        count = Counter(nums)
        res = 0
        for num, cnt in count.items():
            op = dfs(cnt)
            if op == float("inf"):
                return -1
            res += op

        return res

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums$ and $m$ is the average frequency of the array elements.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        count = Counter(nums)
        maxf = max(count.values())
        minOps = [0] * (maxf + 1)
        minOps[1] = float("inf")

        for i in range(2, maxf + 1):
            minOps[i] = minOps[i - 2]
            if i - 3 >= 0:
                minOps[i] = min(minOps[i], minOps[i - 3])
            if minOps[i] != float("inf"):
                minOps[i] += 1

        res = 0
        for num, cnt in count.items():
            op = minOps[cnt]
            if op == float("inf"):
                return -1
            res += op

        return res

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums$ and $m$ is the average frequency of the array elements.

4. Greedy

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        count = Counter(nums)
        res = 0

        for num, cnt in count.items():
            if cnt == 1:
                return -1
            res += math.ceil(cnt / 3)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$