algoadvance

Leetcode 2032. Two Out of Three

Problem Statement

You are given three integer arrays nums1, nums2, and nums3, and you need to return a list of integers that appear in at least two out of the three arrays.

Clarifying Questions

1. What is the range of values that the integers in the arrays can take?
   • The integers can be from -100 to 100.
2. Can the arrays contain duplicate values?
   • Yes, the arrays can contain duplicate values, but for the solution, we’re only interested in the distinct values.
3. What is the expected output format?
   • The output should be a list of integers that appear in at least two out of the three arrays, and the order of the integers does not matter.
4. What is the maximum length of each array?
   • Each array can have up to 100 elements.

Strategy

1. Use sets to handle distinct elements efficiently since sets automatically handle duplicates.
2. Create a dictionary to count the occurrences of each number across the arrays.
3. Traverse through each array and update the dictionary count for each number.
4. Extract the numbers that appear in at least two different arrays based on the dictionary counts.

Steps:

1. Convert each nums1, nums2, and nums3 into sets to remove duplicates within each array.
2. Use a dictionary to count the occurrences of each number across the three sets.
3. Iterate through each set and update the dictionary counts.
4. Collect numbers that appear in at least two sets.

Time Complexity

• Converting each array to a set takes O(n) time, where n is the number of elements in the array.
• Updating counts in the dictionary takes O(m), where m is the total number of distinct elements across all three sets.
• Therefore, the overall time complexity is O(n + m).

Code

#include <vector>
#include <unordered_set>
#include <unordered_map>

std::vector<int> twoOutOfThree(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3) {
    // Convert input arrays to sets to remove duplicates within each array.
    std::unordered_set<int> set1(nums1.begin(), nums1.end());
    std::unordered_set<int> set2(nums2.begin(), nums2.end());
    std::unordered_set<int> set3(nums3.begin(), nums3.end());
    
    // Dictionary to count occurrences across the three sets
    std::unordered_map<int, int> count_map;
    
    // Update count_map for each number in the sets
    for (int num : set1) {
        count_map[num]++;
    }
    
    for (int num : set2) {
        count_map[num]++;
    }
    
    for (int num : set3) {
        count_map[num]++;
    }
    
    // Result vector
    std::vector<int> result;
    
    // Collect numbers that appear in at least two of the three sets
    for (const auto& pair : count_map) {
        if (pair.second >= 2) {
            result.push_back(pair.first);
        }
    }
    
    return result;
}

In this code:

• We first convert each array to a set to ensure all elements within the arrays are distinct.
• We then use an unordered_map to count how many sets each number appears in.
• Finally, we collect numbers that appear in at least two sets and return them as the result.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?