Two Out of Three

Difficulty: Easy | Acceptance: 77.60% | Paid: No Topics: Array, Hash Table, Bit Manipulation

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

• Examples
• Constraints
• Hash Map Frequency Count
• Set Intersection
• Bit Manipulation / Fixed Array

Examples

Example 1:

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
Output: [3,2]
Explanation: The values that are present in at least two arrays are:
- 3, in all three arrays.
- 2, in nums1 and nums2.

Example 2:

Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
Output: [2,3,1]
Explanation: The values that are present in at least two arrays are:
- 2, in nums2 and nums3.
- 3, in nums1 and nums2.
- 1, in nums1 and nums3.

Example 3:

Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
Output: []
Explanation: No value is present in at least two arrays.

Constraints

1 <= nums1.length, nums2.length, nums3.length <= 100
1 <= nums1[i], nums2[j], nums3[k] <= 100

Hash Map Frequency Count

Intuition We can iterate through each array and use a hash map to track how many unique arrays each number appears in. If a number appears in at least two distinct arrays, we include it in our result.

Steps

• Initialize a hash map to store the count of distinct arrays a number appears in.
• Iterate through nums1, adding each number to the map with a count of 1 (if not already present).
• Iterate through nums2, incrementing the count for numbers already in the map, or adding them with a count of 1.
• Iterate through nums3, performing the same logic.
• Collect all keys from the map where the value is 2 or greater.
• Sort the result and return it.

from collections import Counter
from typing import List

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        # Convert lists to sets to remove duplicates within the same array
        set1 = set(nums1)
        set2 = set(nums2)
        set3 = set(nums3)
        
        # Count occurrences across the three sets
        freq = Counter(set1) + Counter(set2) + Counter(set3)
        
        # Filter numbers appearing in at least 2 arrays
        result = [num for num, count in freq.items() if count >= 2]
        
        return sorted(result)

Complexity

• Time: O(N log N) due to sorting, where N is the number of unique elements across all arrays.
• Space: O(N) to store the frequency map and sets.
• Notes: This approach is general-purpose and works for any range of numbers.

Set Intersection

Intuition Since we need elements present in at least two arrays, we can find the intersection of every pair of arrays (1&2, 2&3, 1&3) and take the union of these results.

Steps

• Convert nums1, nums2, and nums3 into sets to remove duplicates.
• Calculate the intersection of set1 and set2.
• Calculate the intersection of set2 and set3.
• Calculate the intersection of set1 and set3.
• Combine all three intersection sets into a single result set.
• Convert the result set to a list, sort it, and return.

from typing import List

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        set3 = set(nums3)
        
        # Union of all pairwise intersections
        result = set1 & set2 | set2 & set3 | set1 & set3
        
        return sorted(list(result))

Complexity

• Time: O(N log N) due to sorting.
• Space: O(N) to store the sets.
• Notes: Very readable and leverages built-in set operations effectively.

Bit Manipulation / Fixed Array

Intuition The problem constraints state that values are between 1 and 100. This small range allows us to use a fixed-size array of length 101. We can use bits to represent which array a number belongs to: bit 0 for nums1, bit 1 for nums2, and bit 2 for nums3.

Steps

• Initialize an integer array seen of size 101 with zeros.
• Iterate through nums1, setting the 1st bit (value 1) for each number: seen[x] |= 1.
• Iterate through nums2, setting the 2nd bit (value 2) for each number: seen[x] |= 2.
• Iterate through nums3, setting the 3rd bit (value 4) for each number: seen[x] |= 4.
• Iterate from 1 to 100. If seen[i] has at least 2 bits set (e.g., 3, 5, 6, or 7), add i to the result.
• Return the result (which is naturally sorted).

from typing import List

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        seen = [0] * 101
        
        for x in nums1:
            seen[x] |= 1
        for x in nums2:
            seen[x] |= 2
        for x in nums3:
            seen[x] |= 4
            
        result = []
        for i in range(1, 101):
            # Check if at least 2 bits are set
            # Valid combinations: 3 (011), 5 (101), 6 (110), 7 (111)
            if seen[i] in (3, 5, 6, 7):
                result.append(i)
                
        return result

Complexity

• Time: O(N) where N is the total number of elements across arrays. The final loop is constant time (100 iterations).
• Space: O(1) as the array size is fixed at 101 regardless of input size.
• Notes: This is the most optimal solution for the given constraints, avoiding sorting and hash map overhead.