Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

There is no choice about which elements an operation removes: it always deletes the first three remaining elements, or all of them if fewer remain. Therefore the minimum number of operations is the first point in this forced sequence where all remaining frequencies are at most one.

Approach

Store the remaining sequence in a queue representation and build a frequency map. Before each operation, scan the map for any count greater than one. If none exists, return the operations performed so far.

Otherwise remove up to three elements from the front, decreasing their frequencies. If the sequence becomes empty during these removals, return the current operation count plus one immediately; an empty array is distinct. After a complete group of three removals, increment the count and check again.

The implementation rescans the frequency-map keys after each operation, rather than maintaining a separate duplicate counter, which accounts for its stated running time.

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        d = deque((nums))
        map = defaultdict(int)
        for x in d: map[x] += 1
        count = 0

        while True:
            # 1. check for duplicatre values in the map
            next = False
            for k in map:
                if map[k] > 1:
                    next = True
                    break
            if not next: return count

            # 2. pop 3 left elements and add 1 to the count
            for i in range(3):
                curr = d.popleft()
                if not d: return count + 1
                map[curr] -= 1
            count += 1

Complexity analysis

Let n = nums.length and u be the number of distinct values. Time: O(n + n * u) because both versions build one frequency map and rescan its keys after each group of three queue removals. Auxiliary space: O(n).