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:
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.
This approach leverages the frequency count of each number to determine the minimum number of operations needed. We will iterate over the frequency list and for each number, calculate the possible number of operations (either removing two or three elements at a time).
We first use Counter from collections to get the frequency of each number in the array. Then, for each frequency, we calculate how many pairs or triples can be removed. We need at least pairs to remove numbers, so if a number appears only once in the list, we return -1. Otherwise, we take the integer division by 3 to count the full groups of 3 elements and add one more operation if there's a remainder. This approach results in efficient calculations to find the minimum operations.
C++
Java
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, as we are iterating through the array and frequencies. Space Complexity: O(n) for storing the frequency count.
This approach targets optimizing operations by prioritizing pair removals wherever possible, then triples. The main idea is to use as many pair removals as possible, and only use triples to fill gaps that pairs cannot cover fully.
Using Counter for frequency counts, we iterate through controlling operations greedily by continuously subtracting 3 (for triples) unless only a single pair remains. This logic ensures minimal operations by prioritizing large removals over small ones unless strictly necessary.
C++
Java
C#
JavaScript
Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map.
| Approach | Complexity |
|---|---|
| Frequency Count Approach | Time Complexity: O(n), where n is the length of the array, as we are iterating through the array and frequencies. Space Complexity: O(n) for storing the frequency count. |
| Greedy Pair-First Strategy | Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map. |
Minimum Numbers of Operations to Make Array Empty - Leetcode 2870 - Python • NeetCodeIO • 16,100 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make Array Empty with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor