Two Out of Three
EasyPrompt
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 <= 1001 <= nums1[i], nums2[j], nums3[k] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a
HashSet<Integer>calledresultSetto store the final distinct numbers. - Use a pair of nested loops to iterate through
nums1andnums2. If an element fromnums1matches an element fromnums2, add it toresultSet. - Repeat the nested loop comparison for
nums1andnums3. - Repeat the nested loop comparison for
nums2andnums3. - The
HashSetautomatically handles duplicate entries, so a number is stored only once even if it's found multiple times. - Finally, convert the
resultSetinto anArrayListand return it.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create three
HashSet<Integer>s,set1,set2, andset3, by iterating throughnums1,nums2, andnums3respectively. This removes duplicates within each array and allows for fast lookups. - Initialize an empty
HashSet<Integer>calledresultSetto store the final answer. - Iterate through each number
numinset1. For each number, check if it is present inset2orset3using thecontains()method. If it is, addnumtoresultSet. - Iterate through each number
numinset2. Check if it is present inset3. If it is, addnumtoresultSet. (The check againstset1is already covered in the previous step). - Convert the
resultSetto anArrayListand return it.
Walkthrough
To optimize the search for common elements, we can use HashSets. 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.
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); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create an integer array
masksof size 101, initialized to all zeros. The indexiwill represent the numberi. - Assign a unique bit to each array: bit 0 (value 1) for
nums1, bit 1 (value 2) fornums2, and bit 2 (value 4) fornums3. - Iterate through
nums1. For each numbern, set the 0th bit inmasks[n]using bitwise OR:masks[n] |= 1. - Iterate through
nums2. For each numbern, set the 1st bit:masks[n] |= 2. - Iterate through
nums3. For each numbern, set the 2nd bit:masks[n] |= 4. - After processing all arrays, initialize an empty
resultlist. - Iterate from
i = 1to100. For eachi, check the maskmasks[i]. If the mask has more than one bit set, it means the numberiappeared in at least two arrays. A simple check for this is(mask & (mask - 1)) != 0. - If the condition is true, add
ito theresultlist. - Return the
resultlist.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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 ; } };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 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.