# Two Out of Three
**Difficulty:** EASY
[External](https://leetcode.com/problems/two-out-of-three)
Canonical: https://scaleengineer.com/dsa/problems/two-out-of-three
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
**Companies:** [Info Edge](https://scaleengineer.com/companies/info-edge), [Booking.com](https://scaleengineer.com/companies/booking.com)
---
## Problem
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. You may return the values in **any** order_. 

**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`

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem statement into code. It compares every element of each array with every element of the other two arrays to find common numbers. A `HashSet` is used to collect the results to ensure the final list contains only distinct values.
**Time:** O(N1*N2 + N1*N3 + N2*N3), where N1, N2, and N3 are the lengths of the arrays. This is because we perform three separate double-loop comparisons. · **Space:** O(K), where K is the number of unique values present in at least two arrays. This space is used by the `HashSet`. In the worst case, K can be up to 100, given the constraints.
**Pros:** Simple to understand and implement.; Requires minimal auxiliary data structures besides the result set.
**Cons:** Very inefficient for larger arrays, with a time complexity that grows quadratically with the input sizes.; Performs many redundant comparisons.
### Explanation
The brute-force method involves a straightforward, albeit inefficient, comparison strategy. We initialize a `HashSet` to store the final distinct numbers, which prevents duplicates in the output. The core of the algorithm consists of three separate double-loop blocks. The first block compares every element in `nums1` with every element in `nums2`. If a common element is found, it's added to the result set. The second and third blocks do the same for the pairs (`nums1`, `nums3`) and (`nums2`, `nums3`). This exhaustive checking ensures that any number present in at least two of the arrays is captured. Finally, the contents of the set are converted into a list to be returned.

```java
import java.util.*;

class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Set<Integer> resultSet = new HashSet<>();

        for (int n1 : nums1) {
            for (int n2 : nums2) {
                if (n1 == n2) {
                    resultSet.add(n1);
                    break; // Optimization: move to next n1 once a match is found
                }
            }
        }

        for (int n1 : nums1) {
            for (int n3 : nums3) {
                if (n1 == n3) {
                    resultSet.add(n1);
                    break;
                }
            }
        }

        for (int n2 : nums2) {
            for (int n3 : nums3) {
                if (n2 == n3) {
                    resultSet.add(n2);
                    break;
                }
            }
        }

        return new ArrayList<>(resultSet);
    }
}
```
### Algorithm
- Create a `HashSet<Integer>` called `resultSet` to store the final distinct numbers.
- Use a pair of nested loops to iterate through `nums1` and `nums2`. If an element from `nums1` matches an element from `nums2`, add it to `resultSet`.
- Repeat the nested loop comparison for `nums1` and `nums3`.
- Repeat the nested loop comparison for `nums2` and `nums3`.
- The `HashSet` automatically handles duplicate entries, so a number is stored only once even if it's found multiple times.
- Finally, convert the `resultSet` into an `ArrayList` and return it.

## Using Hash Sets
This approach improves upon the brute-force method by using hash sets to achieve constant-time lookups on average. We first convert the input arrays into sets to handle duplicates and enable fast searching, then iterate through the sets to find common elements.
**Time:** O(N1 + N2 + N3), where N1, N2, and N3 are the lengths of the arrays. Creating the sets and iterating through them takes linear time relative to the total number of elements. · **Space:** O(U1 + U2 + U3), where U1, U2, and U3 are the number of unique elements in each array. This space is required to store the three hash sets and the result set.
**Pros:** Significantly faster than the brute-force approach with a linear time complexity.; Conceptually clear, modeling the problem using set intersections.
**Cons:** Uses extra space to store up to three additional sets, which can be significant if the arrays contain many unique elements.
### Explanation
To optimize the search for common elements, we can use `HashSet`s. The first step is to convert each of the three input arrays (`nums1`, `nums2`, `nums3`) into a corresponding `HashSet` (`set1`, `set2`, `set3`). This process has two benefits: it automatically removes duplicate values within each original array, and it provides O(1) average time complexity for checking the existence of an element.

Once the sets are created, we can find the numbers that appear in at least two of them. We initialize a `resultSet` to store our final list of numbers. We iterate through `set1` and add any number to `resultSet` that is also found in `set2` or `set3`. Then, we iterate through `set2` and add any number to `resultSet` that is also found in `set3`. This second check completes the logic, as the `set1`/`set2` intersection has already been covered. Finally, we convert the `resultSet` into a list.

```java
import java.util.*;

class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Set<Integer> set1 = new HashSet<>();
        for (int n : nums1) set1.add(n);

        Set<Integer> set2 = new HashSet<>();
        for (int n : nums2) set2.add(n);

        Set<Integer> set3 = new HashSet<>();
        for (int n : nums3) set3.add(n);

        Set<Integer> resultSet = new HashSet<>();
        for (int n : set1) {
            if (set2.contains(n) || set3.contains(n)) {
                resultSet.add(n);
            }
        }
        for (int n : set2) {
            if (set3.contains(n)) {
                resultSet.add(n);
            }
        }

        return new ArrayList<>(resultSet);
    }
}
```
### Algorithm
- Create three `HashSet<Integer>`s, `set1`, `set2`, and `set3`, by iterating through `nums1`, `nums2`, and `nums3` respectively. This removes duplicates within each array and allows for fast lookups.
- Initialize an empty `HashSet<Integer>` called `resultSet` to store the final answer.
- Iterate through each number `num` in `set1`. For each number, check if it is present in `set2` or `set3` using the `contains()` method. If it is, add `num` to `resultSet`.
- Iterate through each number `num` in `set2`. Check if it is present in `set3`. If it is, add `num` to `resultSet`. (The check against `set1` is already covered in the previous step).
- Convert the `resultSet` to an `ArrayList` and return it.

## Optimized Counting with Array and Bitmasking
This is the most efficient approach, leveraging the problem's constraint that all numbers are between 1 and 100. We can use a fixed-size array as a direct-access map to track which arrays each number appears in, using bitmasking to store this information compactly and efficiently.
**Time:** O(N1 + N2 + N3). We iterate through each of the three arrays once, and then iterate through the fixed-size `masks` array (101 elements), which is a constant time operation. · **Space:** O(1). We use a fixed-size array of 101 integers, which is constant space. The space for the result list is not counted in the complexity analysis.
**Pros:** Extremely efficient with O(1) space complexity.; Optimal time complexity, linear in the total number of elements.; Fast due to direct array access and efficient bitwise operations.
**Cons:** This approach is highly specific to the problem's constraints, particularly the limited range of integer values (1-100). It is not a general-purpose solution for arbitrary integer ranges.
### Explanation
Given that the input numbers are constrained to the range [1, 100], we can use a simple array as a frequency map instead of a hash map, which eliminates hashing overhead and improves performance. This approach uses bitmasking to cleverly track the presence of a number across the three arrays in a single integer.

We start by creating an integer array `masks` of size 101. Each index `i` in this array corresponds to the number `i`. We then iterate through each of the input arrays. For each number `n` in `nums1`, we set the first bit of `masks[n]`. For each `n` in `nums2`, we set the second bit of `masks[n]`. For each `n` in `nums3`, we set the third bit. We use the bitwise OR operator (`|=`) to ensure we don't unset previously set bits.

After populating the `masks` array, a number `i` is present in at least two arrays if the value `masks[i]` has at least two bits set. For example, if a number is in `nums1` and `nums2`, its mask will be `1 | 2 = 3` (binary `011`). An efficient way to check if a number has more than one bit set is to use the expression `(mask & (mask - 1)) != 0`. We iterate from 1 to 100, apply this check to each mask, and add the corresponding number to our result list if it passes.

```java
import java.util.*;

class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        int[] masks = new int[101];
        
        for (int n : nums1) {
            masks[n] |= 1;
        }
        
        for (int n : nums2) {
            masks[n] |= 2;
        }
        
        for (int n : nums3) {
            masks[n] |= 4;
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= 100; i++) {
            // A number has more than one bit set if (n & (n-1)) is not zero.
            if ((masks[i] & (masks[i] - 1)) != 0) {
                result.add(i);
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Create an integer array `masks` of size 101, initialized to all zeros. The index `i` will represent the number `i`.
- Assign a unique bit to each array: bit 0 (value 1) for `nums1`, bit 1 (value 2) for `nums2`, and bit 2 (value 4) for `nums3`.
- Iterate through `nums1`. For each number `n`, set the 0th bit in `masks[n]` using bitwise OR: `masks[n] |= 1`.
- Iterate through `nums2`. For each number `n`, set the 1st bit: `masks[n] |= 2`.
- Iterate through `nums3`. For each number `n`, set the 2nd bit: `masks[n] |= 4`.
- After processing all arrays, initialize an empty `result` list.
- Iterate from `i = 1` to `100`. For each `i`, check the mask `masks[i]`. If the mask has more than one bit set, it means the number `i` appeared in at least two arrays. A simple check for this is `(mask & (mask - 1)) != 0`.
- If the condition is true, add `i` to the `result` list.
- Return the `result` list.

# Solutions
### Java

```java
class Solution { public List < Integer > twoOutOfThree ( int [] nums1 , int [] nums2 , int [] nums3 ) { int [] s1 = get ( nums1 ), s2 = get ( nums2 ), s3 = get ( nums3 ); List < Integer > ans = new ArrayList <>(); for ( int i = 1 ; i <= 100 ; ++ i ) { if ( s1 [ i ] + s2 [ i ] + s3 [ i ] > 1 ) { ans . add ( i ); } } return ans ; } private int [] get ( int [] nums ) { int [] s = new int [ 101 ]; for ( int num : nums ) { s [ num ] = 1 ; } return s ; } }
```

### CPP

```cpp
class Solution { public: vector < int > twoOutOfThree ( vector < int >& nums1 , vector < int >& nums2 , vector < int >& nums3 ) { auto get = []( vector < int >& nums ) { vector < int > cnt ( 101 ); for ( int & v : nums ) cnt [ v ] = 1 ; return cnt ; }; auto s1 = get ( nums1 ), s2 = get ( nums2 ), s3 = get ( nums3 ); vector < int > ans ; for ( int i = 1 ; i <= 100 ; ++ i ) { if ( s1 [ i ] + s2 [ i ] + s3 [ i ] > 1 ) { ans . emplace_back ( i ); } } return ans ; } };
```

### Python

```python
class Solution : def twoOutOfThree ( self , nums1 : List [ int ], nums2 : List [ int ], nums3 : List [ int ] ) -> List [ int ]: s1 , s2 , s3 = set ( nums1 ), set ( nums2 ), set ( nums3 ) return [ i for i in range ( 1 , 101 ) if ( i in s1 ) + ( i in s2 ) + ( i in s3 ) > 1 ]
```