Minimum Number of Operations to Make Array Empty - Video Solutions
Minimum Numbers of Operations to Make Array Empty - Leetcode 2870 - Python
Minimum Number of Operations to Make Array Empty - Video Solution
Watch 10 video solutions for Minimum Number of Operations to Make Array Empty, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by NeetCodeIO has 16,949 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 1051 <= nums[i] <= 106
Note: This question is the same as 2244: Minimum Rounds to Complete All Tasks.
Approach Overview
Problem Overview: You are given an array of integers. In one operation, you can remove either 2 or 3 equal values from the array. The goal is to empty the array using the minimum number of operations. If any value appears only once, the task becomes impossible because no operation removes a single element.
Approach 1: Frequency Count Approach (O(n) time, O(n) space)
The key observation is that operations only depend on how many times each value appears. Build a frequency map using a hash table and process each distinct number independently. For a value appearing f times, the optimal strategy is to remove as many triplets as possible since they eliminate more elements per operation. The minimum operations become ceil(f / 3), except when f = 1, which immediately makes the answer -1. Implementation involves iterating through the array once, storing counts in a hash map, then computing the operations per frequency. This approach relies heavily on hash table counting and works in linear time.
Approach 2: Greedy Pair-First Strategy (O(n) time, O(n) space)
A greedy variation focuses on avoiding the problematic remainder case when the frequency leaves a single element. After counting occurrences, check the remainder when dividing by three. If f % 3 == 0, use only triplet removals. If f % 3 == 2, one pair plus the rest triplets works. The tricky case is f % 3 == 1. Removing only triplets would leave one element, so you convert one triplet into two pairs instead. That adjustment keeps the array removable while still minimizing operations. This greedy reasoning ensures the minimal number of operations while scanning frequencies from the array counts stored in the map. The logic mirrors many greedy problems where a local adjustment prevents an invalid leftover state.
Recommended for interviews: The frequency counting approach combined with the greedy formula is what interviewers expect. It demonstrates recognition that the problem reduces to independent frequency groups rather than element positions. A brute force simulation of removals would be inefficient and unnecessary. Explaining why the remainder 1 case converts a triplet into two pairs shows deeper greedy reasoning and usually earns full credit.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count Approach | O(n) | O(n) | General case. Clean and direct solution using hash map counting. |
| Greedy Pair-First Strategy | O(n) | O(n) | When explaining the remainder logic in interviews and avoiding leftover single elements. |