LeetCode 2032 - Two Out of Three

The problem asks us to identify all distinct integers that appear in at least two out of three given integer arrays. The input consists of three arrays nums1, nums2, and nums3, each containing integers in the range [1, 100].

leetcodeeasyarrayhash-tablebit-manipulation

LeetCode Problem 2032

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Bit Manipulation

Solution

Problem Understanding

The problem asks us to identify all distinct integers that appear in at least two out of three given integer arrays. The input consists of three arrays nums1, nums2, and nums3, each containing integers in the range [1, 100]. The output is an array of integers that occur in at least two arrays, and the order of the output does not matter.

The key points are: values must be distinct in the output, and each value only counts once per array (duplicates in a single array do not increase the count). The constraints tell us that each array is small (maximum length 100), and the values themselves are also bounded between 1 and 100. This means we can safely use hash-based structures or bit masks without worrying about performance or memory.

Edge cases to consider include arrays with completely disjoint elements, arrays where all elements are the same, arrays containing duplicates, and arrays with minimal length of 1.

Approaches

The brute-force approach is to iterate through each element of the arrays and count the occurrences across arrays using nested loops. For each element in nums1, we check if it exists in nums2 or nums3, and repeat similarly for nums2 and nums3. After counting, we add the value to the result if it appears in at least two arrays. This approach is correct, but it requires multiple linear searches for each element, which could be inefficient even for small arrays.

The optimal approach leverages sets or hash tables to store distinct values from each array and then count how many sets contain each number. We can convert each array into a set to remove duplicates within that array. Then, we iterate through all possible numbers from the union of these sets and count how many sets contain each number. If a number appears in two or more sets, it is added to the result. This reduces redundant comparisons and ensures uniqueness naturally.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n) Check each element against every array, slow for larger inputs
Optimal O(n) O(n) Use sets to count array occurrences, handles uniqueness efficiently

Algorithm Walkthrough

  1. Convert nums1, nums2, and nums3 into sets, named set1, set2, and set3. This removes duplicates within the same array and allows for O(1) membership checking.
  2. Initialize an empty list result to store the output.
  3. Compute the union of all three sets to get all distinct numbers across the arrays.
  4. Iterate over each number in the union. For each number, count how many of the three sets contain it.
  5. If a number is present in at least two sets, append it to result.
  6. Return result.

Why it works: converting arrays to sets ensures each number is counted only once per array. Iterating over the union guarantees we check all possible candidates without missing any. Counting set membership directly gives the number of arrays each value appears in. Any value appearing in at least two sets is guaranteed to meet the problem condition.

Python Solution

from typing import List

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        set1, set2, set3 = set(nums1), set(nums2), set(nums3)
        result = []
        
        for num in set1 | set2 | set3:
            count = (num in set1) + (num in set2) + (num in set3)
            if count >= 2:
                result.append(num)
        
        return result

In the implementation, we first convert each input list into a set to remove duplicates. We then compute the union of all three sets, which gives us every number that occurs in any array. For each number, we use boolean membership checks (num in setX) that evaluate to True or False, which we sum to get the total number of arrays containing that number. If this count is two or more, we add the number to the result list. The approach is simple, readable, and efficient.

Go Solution

func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) []int {
    set1, set2, set3 := make(map[int]bool), make(map[int]bool), make(map[int]bool)
    for _, n := range nums1 {
        set1[n] = true
    }
    for _, n := range nums2 {
        set2[n] = true
    }
    for _, n := range nums3 {
        set3[n] = true
    }

    result := []int{}
    seen := make(map[int]bool)
    
    for n := range set1 {
        if (set2[n] || set3[n]) && !seen[n] {
            result = append(result, n)
            seen[n] = true
        }
    }
    for n := range set2 {
        if set3[n] && !seen[n] {
            result = append(result, n)
            seen[n] = true
        }
    }
    
    return result
}

In Go, we use map[int]bool to simulate sets since Go does not have a native set type. We populate three maps for the three arrays. Then we iterate over each map to check if a number exists in at least two maps, using a separate seen map to ensure we only append distinct numbers. The logic mirrors the Python approach but requires explicit handling for uniqueness in the result.

Worked Examples

Example 1

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]

Step set1 set2 set3 Union Count of num Result
1 {1,2,3} {2,3} {3} {1,2,3} 1:1, 2:2, 3:3 [2,3]

Output: [2,3]

Example 2

Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]

Union: {1,2,3}

Counts: 1 → 2, 2 → 2, 3 → 2

Result: [1,2,3]

Example 3

Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]

Union: {1,2,3,4,5}

Counts: all < 2

Result: []

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each array is converted to a set in O(n), union is O(n), iterating over union is O(n)
Space O(n) Sets and result list store distinct values, at most O(n) where n is total elements

The time complexity is linear with respect to the total number of elements across the three arrays, and space is proportional to the number of distinct values.

Test Cases

# Provided examples
assert set(Solution().twoOutOfThree([1,1,3,2], [2,3], [3])) == {2,3}  # nums1 and nums2 share 2, 3 in all
assert set(Solution().twoOutOfThree([3,1], [2,3], [1,2])) == {1,2,3}  # each number appears in 2 arrays
assert set(Solution().twoOutOfThree([1,2,2], [4,3,3], [5])) == set()   # no number appears in 2 arrays

# Edge cases
assert set(Solution().twoOutOfThree([1], [1], [1])) == {1}             # all arrays identical
assert set(Solution().twoOutOfThree([1], [2], [3])) == set()           # completely disjoint arrays
assert set(Solution().twoOutOfThree([1,2,3], [3,4,5], [5,6,1])) == {1,3,5}  # overlapping subsets
assert set(Solution().twoOutOfThree([1]*100, [1]*50, [2]*100])) == {1} # duplicates in arrays
Test Why
[1,1,3,2], [2,3], [3] Standard overlap, multiple occurrences in a single array
[3,1], [2,3], [1,2] Each value appears in exactly two arrays
[1,2,2], [4,3,3], [5] No overlaps
[1], [1], [1] All identical arrays, minimal size
[1], [2], [3] Completely disjoint arrays, minimal size
[1,2,3], [3,4,5], [5,6,1] Partial overlaps across arrays
`[1]*