algoadvance

Leetcode 2869. Minimum Operations to Collect Elements

Problem Statement

You are given an array of integers, nums, and another array, elements. We would like to remove the minimum number of elements from nums such that all of the elements in elements are no longer in nums. If it’s not possible, return -1.

In other words, you want to find the smallest subset of nums such that removing it will exclude all the integers in elements from nums.

Clarifying Questions

  1. Are the elements of elements guaranteed to be present in nums?
    • If not, handling cases where an element of elements is not in nums would be necessary.
  2. Are the arrays sorted or unsorted?
    • Both arrays can be considered unsorted.
  3. Can the arrays contain duplicate elements?
    • Yes, nums can contain duplicate elements, and we have to consider them accordingly.
  4. What are the sizes of the arrays?
    • Let n be the length of nums, and m be the length of elements. We’ll assume minimal constraints where arrays can be reasonably large given typical problem constraints (e.g., 1 ≤ n, m ≤ 100,000).

Strategy

The strategy can be broken down into the following steps:

  1. Frequency Counting: Create a frequency count of elements to know how many times each element needs to be removed from nums.
  2. Pointer Technique: Use two pointers or window sliding techniques to find the smallest subarray in nums that contains all elements from elements with at least their required frequencies.

Code

Here is the C++ implementation following the described strategy:

#include <vector>
#include <unordered_map>
#include <iostream>

int minOperationsToCollectElementsOut(std::vector<int>& nums, std::vector<int>& elements) {
    std::unordered_map<int, int> elementCount, windowCount;
    
    // Count the frequency of elements in the `elements` array
    for (const auto& ele : elements) {
        elementCount[ele]++;
    }
    
    int required = elementCount.size(); // Number of unique elements we need to match
    int formed = 0; // Number of unique elements we have successfully matched
    
    int left = 0, right = 0;
    int minLen = nums.size() + 1;
    
    while (right < nums.size()) {
        int rtEle = nums[right];
        windowCount[rtEle]++;
        
        if (elementCount.count(rtEle) && windowCount[rtEle] == elementCount[rtEle]) {
            formed++;
        }
        
        while (left <= right && formed == required) {
            int ltEle = nums[left];
            
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
            }
            
            windowCount[ltEle]--;
            if (elementCount.count(ltEle) && windowCount[ltEle] < elementCount[ltEle]) {
                formed--;
            }
            left++;
        }
        
        right++;
    }
    
    return minLen == nums.size() + 1 ? -1 : minLen;
}

int main() {
    std::vector<int> nums = {1, 3, 5, 3, 1, 3, 7, 3};
    std::vector<int> elements = {1, 3};
    std::cout << "Minimum operations: " << minOperationsToCollectElementsOut(nums, elements) << std::endl;
    return 0;
}

Time Complexity

Hence, the overall time complexity is O(n + m).

This approach ensures that we are efficiently finding the smallest subarray in nums that contains all elements with the required frequency from elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI