Leetcode 2870: Minimum Number of Operations to Make Array Empty
You are given an array nums consisting of positive integers. You are allowed to perform two types of operations on the array any number of times: (1) Choose two elements that are the same and remove them from the array. (2) Choose three elements that are the same and remove them from the array. Your task is to return the minimum number of operations required to empty the array, or return -1 if it is not possible to empty the array using these operations.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of positive integers nums. You need to apply operations to empty the array.
Example: nums = [3, 1, 3, 3, 2, 2, 1, 2, 1]
Constraints:
• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106
Output: Return the minimum number of operations required to empty the array, or return -1 if it is not possible to empty the array.
Example: For input nums = [3, 1, 3, 3, 2, 2, 1, 2, 1], the output is 4.
Constraints:
Goal: The goal is to minimize the number of operations required to remove all elements from the array, using the two defined operations.
Steps:
• Count the frequency of each element in the array.
• For each element, check if its count can be divided into valid pairs or triples for removal.
• If any element has a count of 1, return -1 since it can't be removed.
• For other elements, calculate the number of operations required by grouping them in pairs or triples.
Goal: The solution should handle arrays with up to 100,000 elements efficiently.
Steps:
• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106
Assumptions:
• The array is non-empty and contains only positive integers.
• Input: For input nums = [3, 1, 3, 3, 2, 2, 1, 2, 1], the output is 4.
• Explanation: We can apply the operations in sequence to remove the elements and make the array empty in 4 operations.
Approach: The solution involves counting the frequency of each element in the array and then applying the operations as efficiently as possible to minimize the number of operations.
Observations:
• We need to group elements in pairs or triples to remove them efficiently.
• A simple approach is to count the frequency of each element and then determine how many operations are needed to remove all occurrences of that element.
Steps:
• First, count the occurrences of each element using a hashmap or frequency array.
• For each unique element, check if its count is either a multiple of 2 or 3. If not, return -1.
• For counts divisible by 3, perform the third operation, and for counts divisible by 2, perform the second operation.
Empty Inputs:
• The array will always have at least two elements.
Large Inputs:
• The algorithm should handle large arrays efficiently (up to 100,000 elements).
Special Values:
• If an element appears only once, it is impossible to remove it.
Constraints:
• The solution must account for arrays containing large numbers of repeated elements.
int minOperations(vector<int>& nums) {
unordered_map<int, int> m;
for (int n : nums)
++m[n];
int res = 0;
for (auto [_, cnt] : m) {
if (cnt == 1)
return -1;
res += cnt / 3 + (cnt % 3 > 0);
}
return res;
}
1 : Code Declaration
int minOperations(vector<int>& nums) {
Function declaration that takes a vector of integers as input, returning an integer result.
2 : Variable Initialization
unordered_map<int, int> m;
Initialize an unordered map to store the frequency of each element in the nums vector.
3 : Loop Setup
for (int n : nums)
Start a for-each loop to iterate over each element in the nums vector.
4 : Frequency Count
++m[n];
Increment the count for the current element in the unordered map m.
5 : Result Initialization
int res = 0;
Initialize the result variable to 0, which will hold the total number of operations.
6 : Map Iteration
for (auto [_, cnt] : m) {
Iterate through the unordered map, where _ represents the element (not used) and cnt represents its frequency.
7 : Condition Check
if (cnt == 1)
Check if the current frequency of the element is 1.
8 : Early Return
return -1;
If an element appears only once, return -1, as grouping is not possible.
9 : Result Calculation
res += cnt / 3 + (cnt % 3 > 0);
Calculate the number of operations for the current element by dividing its frequency by 3 and adding 1 if there is a remainder.
10 : Return Result
return res;
Return the final result, which is the total number of operations.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only need to traverse the array once to count element frequencies.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the frequency counts of each element.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus