Scale Engineer

Two Out of Three

Easy
#1850Time: 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.2 companies
Patterns
Bit Manipulation
Data structures
ArrayHash Table
Companies
Info EdgeBooking.com

Prompt

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

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> 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.

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.

Solutions

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 ; } }

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.

← Previous

Previous problem

Next →

Next problem