2032. Two Out of Three - Solution

Q: Is Two Out of Three easy or hard?

Two Out of Three is classified as an Easy problem. The challenge mainly tests understanding of sets, hash tables, and duplicate handling. Once you recognize that duplicates inside the same array must be ignored, the solution becomes straightforward.

Q: How to solve Two Out of Three in O(n)?

Use three sets to remove duplicates from each array. Track element presence using a hash map or frequency array. Increment the count for each number appearing in a set, and collect numbers with a count of at least two. Since every element is processed once, the total runtime is linear.

Q: What is the best approach for Two Out of Three?

The most practical approach uses sets combined with a hash map. Convert each array into a set to remove duplicates, then count how many arrays contain each value. Any number appearing in at least two sets is added to the result. This runs in O(n + m + k) time with hash lookups.

Q: Is Two Out of Three asked at Google/Amazon/Meta?

Problems involving set intersections and hash-based counting frequently appear in interviews at companies like Amazon and Meta. While this exact question may vary, the pattern of deduplicating arrays and counting occurrences across collections is common in coding interviews.

Q: What data structure is used in Two Out of Three?

The primary data structures are hash sets and hash maps. Sets ensure duplicates inside a single array are ignored, while a hash map tracks how many arrays contain each value. Some implementations replace the map with a frequency array when the number range is limited.

Q: What is the time complexity of Two Out of Three?

The optimal solution runs in O(n + m + k) time, where n, m, and k are the lengths of the three arrays. Each array is processed once to build sets and update counts. Hash map operations are O(1) on average, keeping the overall complexity linear.

Q: Two Out of Three Python or Java solution approach?

Both Python and Java implementations typically convert arrays into sets and use a dictionary or HashMap to count occurrences. Iterate through each set and increment the count for its elements. Finally, return all numbers whose count is at least two.

The 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

Approach overview

Problem Overview: You receive three integer arrays nums1, nums2, and nums3. The task is to return all distinct values that appear in at least two of the arrays. Duplicates inside the same array should not inflate the count; only presence across different arrays matters.

Approach 1: Using Sets to Store Unique Elements and Count Occurrences (Time: O(n + m + k), Space: O(n + m + k))

The most common solution uses set structures to remove duplicates inside each array first. Convert each array into a set, then track how many arrays contain each number using a hash map. Iterate through each set and increment a counter for its elements. Any value with a count of at least two appears in two or more arrays and belongs in the result.

This approach works well because set lookups and insertions are O(1) on average. By eliminating duplicates early, you avoid incorrectly counting repeated numbers from the same array. The technique relies heavily on hash table behavior and is the most readable solution for interviews.

Approach 2: Using Frequency Arrays (Time: O(n + m + k), Space: O(U))

If the value range is reasonably bounded, a frequency array can replace the hash map. First convert each input array into a set so duplicates inside one array are ignored. Then maintain a frequency array where the index represents a value and the stored number represents how many arrays contain it. Traverse the three sets and increment the frequency for each value.

After processing all sets, iterate through the frequency structure and collect numbers with frequency ≥ 2. This avoids hashing overhead and can be slightly faster in languages where array access is cheaper than map operations. The tradeoff is extra memory proportional to the maximum possible value, which may not be ideal for large ranges. This approach still relies on concepts from array processing and counting techniques often seen in bit manipulation or frequency problems.

Recommended for interviews: The set + hash map method is what most interviewers expect. It demonstrates that you handle duplicates correctly and leverage constant‑time hash lookups. Mentioning the frequency-array optimization shows deeper understanding of tradeoffs when the input range is known. Both run in linear time, but the hash-based approach is safer when constraints are large or unknown.

Approach 1: Using Sets to Store Unique Elements and Count Occurrences

To solve the problem, we'll use sets to capture unique elements from each array, then count the total appearances of each element across all arrays. Finally, we'll select elements that appear in at least two arrays.

The approach involves converting each array into a set to fetch distinct elements. We then use a dictionary (or map) to track the frequency of each element appearing across the three sets.

Python

def twoOutOfThree(nums1, nums2, nums3):
    sets = [set(nums1), set(nums2), set(nums3)]
    counter = {}
    for s in sets:
        for num in s:
            if num in counter:
                counter[num] += 1
            else:
                counter[num] = 1
    return [num for num, count in counter.items() if count >= 2]

Java

import java.util.*;

public class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Set<Integer> set1 = new HashSet<>(), set2 = new HashSet<>(), set3 = new HashSet<>();
        for (int num : nums1) set1.add(num);
        for (int num : nums2) set2.add(num);
        for (int num : nums3) set3.add(num);
        Map<Integer, Integer> countMap = new HashMap<>();
        for (Integer num : set1) countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        for (Integer num : set2) countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        for (Integer num : set3) countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() >= 2) result.add(entry.getKey());
        }
        return result;
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

std::vector<int> twoOutOfThree(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3) {
    std::unordered_set<int> set1(nums1.begin(), nums1.end());
    std::unordered_set<int> set2(nums2.begin(), nums2.end());
    std::unordered_set<int> set3(nums3.begin(), nums3.end());
    std::unordered_map<int, int> countMap;

    for (auto num : set1) countMap[num]++;
    for (auto num : set2) countMap[num]++;
    for (auto num : set3) countMap[num]++;

    std::vector<int> result;
    for (auto pair : countMap) {
        if (pair.second >= 2) result.push_back(pair.first);
    }

    return result;
}

JavaScript

function twoOutOfThree(nums1, nums2, nums3) {
    const sets = [new Set(nums1), new Set(nums2), new Set(nums3)];
    const counter = {};

    for (const s of sets) {
        for (const num of s.values()) {
            counter[num] = (counter[num] || 0) + 1;
        }
    }

    return Object.keys(counter).filter(num => counter[num] >= 2).map(Number);
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

bool twoOrMore(int *array1, int size1, int *array2, int size2, int *array3, int size3, int num) {
    int count = 0;
    int arrays[3][2] = {{array1, size1}, {array2, size2}, {array3, size3}};
    for (int i = 0; i < 3; i++) {
        int *arr = (int *)arrays[i][0];
        int len = arrays[i][1];
        if (bsearch(&num, arr, len, sizeof(int), compare) != NULL) {
            count++;
            if (count == 2) return true;
        }
    }
    return false;
}

int* twoOutOfThree(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* returnSize) {
    int arr1[101] = {0};
    int result[101], index = 0;

    for(int i = 0; i < nums1Size; i++) arr1[nums1[i]]++;
    for(int i = 0; i < nums2Size; i++) arr1[nums2[i]]++;
    for(int i = 0; i < nums3Size; i++) arr1[nums3[i]]++;

    for(int i = 1; i <= 100; i++) {
        if(arr1[i] >= 2) {
            result[index++] = i;
        }
    }

    *returnSize = index;
    int* res = (int*)malloc(index * sizeof(int));
    for(int i = 0; i < index; i++) res[i] = result[i];
    return res;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> TwoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        var set3 = new HashSet<int>(nums3);

        var countMap = new Dictionary<int, int>();

        foreach (var num in set1) {
            if (!countMap.ContainsKey(num)) countMap[num] = 0;
            countMap[num] += 1;
        }
        foreach (var num in set2) {
            if (!countMap.ContainsKey(num)) countMap[num] = 0;
            countMap[num] += 1;
        }
        foreach (var num in set3) {
            if (!countMap.ContainsKey(num)) countMap[num] = 0;
            countMap[num] += 1;
        }

        var result = new List<int>();
        foreach (var kvp in countMap) {
            if (kvp.Value >= 2) result.Add(kvp.Key);
        }

        return result;
    }
}

The function twoOutOfThree creates sets for each input list to get unique values from them. It uses a dictionary to count how many sets each element appears in. Finally, it returns a list of elements that appear in at least two sets.

Complexity

Time Complexity: O(n), where n is the total number of elements across all input lists since we iterate through each element once.
Space Complexity: O(u), where u is the number of unique elements given the constraints.

Try this approach in the editor

Approach 2: Using Frequency Arrays

This method employs auxiliary arrays to record the presence frequency of elements. Given the constraint that elements are between 1 and 100, we can use a fixed-size frequency array to track how many of the three arrays contain any given element.

Python

def twoOutOfThree(nums1, nums2, nums3):
    freq = [0] * 101

    def mark(arr):
        local_set = set(arr)
        for num in local_set:
            freq[num] += 1

    mark(nums1)
    mark(nums2)
    mark(nums3)

    return [i for i in range(1, 101) if freq[i] >= 2]

Java

import java.util.*;

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

        markArray(nums1, freq);
        markArray(nums2, freq);
        markArray(nums3, freq);

        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= 100; i++) {
            if (freq[i] >= 2) result.add(i);
        }
        return result;
    }

    private void markArray(int[] nums, int[] freq) {
        Set<Integer> localSet = new HashSet<>();
        for (int num : nums) localSet.add(num);
        for (int num : localSet) freq[num]++;
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_set>

std::vector<int> twoOutOfThree(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3) {
    int freq[101] = {0};

    auto mark = [&](const std::vector<int>& nums) {
        std::unordered_set<int> localSet(nums.begin(), nums.end());
        for (int num : localSet) {
            freq[num]++;
        }
    };
    
    mark(nums1);
    mark(nums2);
    mark(nums3);

    std::vector<int> result;
    for (int i = 1; i <= 100; ++i) {
        if (freq[i] >= 2) {
            result.push_back(i);
        }
    }
    return result;
}

JavaScript

function twoOutOfThree(nums1, nums2, nums3) {
    const freq = new Array(101).fill(0);

    function mark(arr) {
        const localSet = new Set(arr);
        for (let num of localSet) {
            freq[num]++;
        }
    }

    mark(nums1);
    mark(nums2);
    mark(nums3);

    const result = [];
    for (let i = 1; i <= 100; i++) {
        if (freq[i] >= 2) {
            result.push(i);
        }
    }

    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> TwoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        int[] freq = new int[101];

        MarkArray(nums1, freq);
        MarkArray(nums2, freq);
        MarkArray(nums3, freq);

        var result = new List<int>();
        for (int i = 1; i <= 100; i++) {
            if (freq[i] >= 2) {
                result.Add(i);
            }
        }
        return result;
    }

    private void MarkArray(int[] nums, int[] freq) {
        var localSet = new HashSet<int>(nums);
        foreach (var num in localSet) {
            freq[num]++;
        }
    }
}

This Python solution uses a frequency array of size 101 to count how many times a number is present in the three arrays. By marking the frequency for unique elements in each list, the solution considers elements appearing in at least two arrays.

Complexity

Time Complexity: O(n), where n is the sum of lengths of nums1, nums2, and nums3.
Space Complexity: O(100), which is effectively O(1).

Try this approach in the editor

Approach 3: Array + Enumeration

We can first put each element of the arrays into an array, then enumerate each number i from 1 to 100, and check whether i appears in at least two arrays. If so, add i to the answer array.

The time complexity is O(n_1 + n_2 + n_3), and the space complexity is O(n_1 + n_2 + n_3). Here, n_1, n_2, n_3 are the lengths of the arrays nums1, nums2, and nums3, respectively.

TypeScript

function twoOutOfThree(nums1: number[], nums2: number[], nums3: number[]): number[] {
    const count = new Array(101).fill(0);
    new Set(nums1).forEach(v => count[v]++);
    new Set(nums2).forEach(v => count[v]++);
    new Set(nums3).forEach(v => count[v]++);
    const ans = [];
    count.forEach((v, i) => {
        if (v >= 2) {
            ans.push(i);
        }
    });
    return ans;
}

func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) (ans []int) {
	get := func(nums []int) (s [101]int) {
		for _, v := range nums {
			s[v] = 1
		}
		return
	}
	s1, s2, s3 := get(nums1), get(nums2), get(nums3)
	for i := 1; i <= 100; i++ {
		if s1[i]+s2[i]+s3[i] > 1 {
			ans = append(ans, i)
		}
	}
	return
}

Rust

use std::collections::HashSet;
impl Solution {
    pub fn two_out_of_three(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>) -> Vec<i32> {
        let mut count = vec![0; 101];
        nums1
            .into_iter()
            .collect::<HashSet<i32>>()
            .iter()
            .for_each(|&v| {
                count[v as usize] += 1;
            });
        nums2
            .into_iter()
            .collect::<HashSet<i32>>()
            .iter()
            .for_each(|&v| {
                count[v as usize] += 1;
            });
        nums3
            .into_iter()
            .collect::<HashSet<i32>>()
            .iter()
            .for_each(|&v| {
                count[v as usize] += 1;
            });
        let mut ans = Vec::new();
        count.iter().enumerate().for_each(|(i, v)| {
            if *v >= 2 {
                ans.push(i as i32);
            }
        });
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Sets to Store Unique Elements and Count Occurrences	Time Complexity: `O(n)`, where `n` is the total number of elements across all input lists since we iterate through each element once. Space Complexity: `O(u)`, where `u` is the number of unique elements given the constraints.
Using Frequency Arrays	Time Complexity: `O(n)`, where `n` is the sum of lengths of nums1, nums2, and nums3. Space Complexity: `O(100)`, which is effectively `O(1)`.
Array + Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Sets + Hash Map Counting	O(n + m + k)	O(n + m + k)	General case. Works for any value range and is the most common interview solution.
Frequency Array Counting	O(n + m + k)	O(U)	Useful when value range is small and predictable, making array indexing faster than hashing.

Frequently asked questions

Is Two Out of Three easy or hard?

Two Out of Three is classified as an Easy problem. The challenge mainly tests understanding of sets, hash tables, and duplicate handling. Once you recognize that duplicates inside the same array must be ignored, the solution becomes straightforward.

How to solve Two Out of Three in O(n)?

Use three sets to remove duplicates from each array. Track element presence using a hash map or frequency array. Increment the count for each number appearing in a set, and collect numbers with a count of at least two. Since every element is processed once, the total runtime is linear.

What is the best approach for Two Out of Three?

The most practical approach uses sets combined with a hash map. Convert each array into a set to remove duplicates, then count how many arrays contain each value. Any number appearing in at least two sets is added to the result. This runs in O(n + m + k) time with hash lookups.

Is Two Out of Three asked at Google/Amazon/Meta?

Problems involving set intersections and hash-based counting frequently appear in interviews at companies like Amazon and Meta. While this exact question may vary, the pattern of deduplicating arrays and counting occurrences across collections is common in coding interviews.

What data structure is used in Two Out of Three?

The primary data structures are hash sets and hash maps. Sets ensure duplicates inside a single array are ignored, while a hash map tracks how many arrays contain each value. Some implementations replace the map with a frequency array when the number range is limited.

What is the time complexity of Two Out of Three?

The optimal solution runs in O(n + m + k) time, where n, m, and k are the lengths of the three arrays. Each array is processed once to build sets and update counts. Hash map operations are O(1) on average, keeping the overall complexity linear.

Two Out of Three Python or Java solution approach?

Both Python and Java implementations typically convert arrays into sets and use a dictionary or HashMap to count occurrences. Iterate through each set and increment the count for its elements. Finally, return all numbers whose count is at least two.

Two Out of Three solution and explanation

The problem

Approach overview

Approach 1: Using Sets to Store Unique Elements and Count Occurrences

Approach 2: Using Frequency Arrays

Approach 3: Array + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Two Out of Three solution and explanation

The problem

Approach overview

Approach 1: Using Sets to Store Unique Elements and Count Occurrences

Approach 2: Using Frequency Arrays

Approach 3: Array + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems