LeetCode Solutions Blog

Two Out of Three

Number: 2159

Difficulty: Easy

Paid? No

Problem Description

Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays.

Key Insights

Convert each array into a set to eliminate duplicate values within the same array.
Use a hashmap or frequency counter to count the occurrence of each distinct number across the three sets.
Include the number in the result if its frequency is at least 2.
The ordering of output does not matter.

Space and Time Complexity

Time Complexity: O(n1 + n2 + n3) where n1, n2, and n3 are the lengths of the three arrays. Space Complexity: O(n1 + n2 + n3) for the sets and the frequency counter.

Solution

We start by converting each input array into a set to remove duplicates. Then, we use a hashmap (or dictionary) to count how many sets each distinct number appears in. Finally, we iterate through the hashmap and select the numbers that appear in at least two out of the three sets. This approach efficiently handles the task by reducing the number of elements to consider and directly counting their occurrences.

Code Solutions

# Function to find numbers present in at least two out of three arrays
def twoOutOfThree(nums1, nums2, nums3):
    # Convert lists to sets to eliminate duplicates within each array
    set1 = set(nums1)
    set2 = set(nums2)
    set3 = set(nums3)
    
    # Dictionary to count frequency of each number across the three sets
    frequency = {}
    
    # Increase count for numbers in set1
    for num in set1:
        frequency[num] = frequency.get(num, 0) + 1
    # Increase count for numbers in set2
    for num in set2:
        frequency[num] = frequency.get(num, 0) + 1
    # Increase count for numbers in set3
    for num in set3:
        frequency[num] = frequency.get(num, 0) + 1
    
    # Use list comprehension to gather numbers appearing at least twice
    result = [num for num, count in frequency.items() if count >= 2]
    return result

# Example usage
print(twoOutOfThree([1,1,3,2], [2,3], [3]))  # Output: [3,2] (order may vary)