Problem 2870

(Last updated: )

Question statement

You are given a 0-indexed array $\texttt{nums}$ consisting of positive integers. There are two types of operations that you can apply to remove elements from the array. Return the minimum number of operations required to make the array empty, or -1 if it is not possible. The valid operations are:

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

Solution

Brute force + memoization suffices.

Main idea:

Suppose we have an element $i$ whose count is $n$ (this can be memoized using a dictionary). We have various cases:

  • If $n = 1$, then it is impossible to remove that element. So return -1.
  • If $n \pmod 3$ is $0$, then the optimal strategy is to remove three at a time $n/3$ times.
    $$\texttt{operations += } \frac{n}{3}$$
  • If $n \pmod 3$ is $2$, then the optimal strategy is to remove $2$ first. Now, $n-2 \pmod 3$ is $0$, so apply step 1.
    $$\texttt{operations += } 1 + \frac{n-2}{3}$$
  • If $n \pmod 3$ is $1$, then we keep removing in $3$’s until we hit $\texttt{count} = 4$, then we remove two at a time twice.
    $$\texttt{operations += } 2 + \frac{n-1}{3} - 1$$

More succinctly:

$$\texttt{operations += } \begin{cases} 1 + \frac{n - (n\pmod 3)}{3} & n\pmod 3 \neq 0 \\
\frac{n}{3} & n \pmod 3 = 0 \end{cases}$$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def minOperations(self, nums: List[int]) -> int:
    operations = 0
    dic = defaultdict(int)
    for i in nums:
        dic[i] += 1
    
    for i in dic:
        cnt = dic[i]
        if cnt == 1:
            return -1
        elif cnt % 3 == 0:
            operations += cnt//3
        else: 
            operations += 1 + (cnt - (cnt%3))//3
    return operations


Obeservation:

Time complexity: O($\texttt{len(nums)}$)

At the time of submission, the above solution passes leetcode submission cases in 548ms, beats 94.55% of users. It uses 31.2MB of memory, beating 10.3% of users.