How do you solve Two Out of Three on LeetCode?

Two Out of Three (LeetCode #2032) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashMap allows for efficient counting of occurrences across multiple arrays.

What is the brute force solution for Two Out of Three?

The brute force approach for Two Out of Three is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each element in the arrays against every other element to see if it appears in at least two of the three arrays. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Two Out of Three?

Two Out of Three uses the following concepts: Array, Hash Table, Bit Manipulation. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Two Out of Three?

Think about using data structures that can help you count or track occurrences. Always consider edge cases and test your solution against them. Explain your thought process clearly to the interviewer as you work through the problem.

What are common mistakes when solving Two Out of Three?

Failing to handle duplicates correctly in the result. Not considering edge cases where no numbers appear in at least two arrays.

#2032

Two Out of Three

Easy

ArrayHash TableBit ManipulationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a HashMap allows us to count occurrences of each number across the three arrays efficiently. This way, we can determine which numbers appear in at least two arrays in a single pass.

⚙️

Algorithm

5 steps

1Step 1: Create a HashMap to count occurrences of each number.
2Step 2: Iterate through each array and update the count in the HashMap.
3Step 3: Create a result list to store numbers that appear at least twice.
4Step 4: Iterate through the HashMap and add keys with a count of 2 or more to the result list.
5Step 5: Return the result list.

solution.py10 lines

1def twoOutOfThree(nums1, nums2, nums3):
2    from collections import defaultdict
3    count = defaultdict(int)
4    for num in nums1:
5        count[num] += 1
6    for num in nums2:
7        count[num] += 1
8    for num in nums3:
9        count[num] += 1
10    return [num for num, cnt in count.items() if cnt > 1]

ℹ

Complexity note: The time complexity is O(n) because we make a single pass through each of the three arrays to count occurrences. The space complexity is O(n) due to the HashMap storing counts of potentially all unique elements.

1Using a HashMap allows for efficient counting of occurrences across multiple arrays.
2Understanding how to leverage data structures can significantly improve performance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.