Python 2032.py
class Solution:
def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
freq = defaultdict(int)
for n in set(nums1):
freq[n] += 1
for n in set(nums2):
freq[n] += 1
for n in set(nums3):
freq[n] += 1
for f in freq:
if freq[f] >= 2:
yield f
Difficulty
and has an acceptance rate of about 78% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Bit Manipulation
- Hash Table
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a method twoOutOfThree that receives three integer arrays. Its purpose is to identify all distinct values that appear in at least two of the three input collections. The method builds a frequency map that records how many of the three arrays contain each value, then lazily yields the qualifying numbers.
Core Logic
At the heart of the algorithm is a three-stage process: deduplicate each input list, update a shared counter, and emit values whose counter meets the threshold of two. The use of a generator (yield) means the caller can iterate over results without requiring an intermediate list.
def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
freq = defaultdict(int)
...
for f in freq:
if freq[f] >= 2:
yield f
Frequency Accumulation
The method first creates a defaultdict of integers to serve as the frequency table. For each of the three input arrays, it constructs a set to eliminate duplicate occurrences within the same array. Each unique element from the set increments its entry in the dictionary by one. This ensures that an element contributed at most once per source array, regardless of how many times it appears inside that array.
freq = defaultdict(int)
for n in set(nums1):
freq[n] += 1
for n in set(nums2):
freq[n] += 1
for n in set(nums3):
freq[n] += 1
Result Generation
After the frequency map is populated, the method iterates over its keys. Whenever a key’s count is two or greater, the value is produced via yield. Because yield creates a generator, the caller can consume results one by one, which is especially useful when only a subset of the output is needed.
for f in freq:
if freq[f] >= 2:
yield f
Edge Cases Handled
The algorithm gracefully manages several boundary conditions:
- Empty input arrays - If any of the three lists is empty, converting it to a set yields an empty collection, so no increments occur for that source. The remaining arrays are still processed correctly.
- All three arrays identical - Each distinct element will be added to the set three times, resulting in a frequency of three. Since three satisfies the “at least two” condition, every unique element is yielded exactly once.
- Elements appearing in exactly two arrays - The frequency for such elements becomes two, meeting the threshold, and they are emitted.
- Elements appearing in only one array - Their frequency remains one, so they are excluded from the output.
- Negative numbers and zero - The dictionary keys accept any hashable integer, so negative values and zero are treated identically to positive numbers.
- Large numeric ranges - Because the dictionary stores only distinct values that actually appear, the memory footprint scales with the number of unique elements rather than the numeric magnitude.
Performance Considerations
The implementation incorporates several optimizations that keep execution efficient:
- Deduplication via
set- By converting each input list to a set before counting, the algorithm avoids counting repeated occurrences within the same list. This reduces the number of dictionary updates, especially when an input contains many duplicates. - Constant-time updates with
defaultdict- The use of adefaultdict(int)eliminates the need for explicit existence checks before incrementing a counter, allowing each update to proceed in a single operation. - Lazy result production - Employing
yieldcreates a generator that produces values on demand. This avoids constructing an intermediate list of results, saving both time and memory when the caller consumes only part of the output or streams it directly. - Single pass over the frequency map - After the three accumulation loops, the method makes one linear scan of the dictionary keys to filter qualifying elements, ensuring that no extra passes over the original data are required.
ELI5 - Simplified Explanation
Imagine three buckets filled with colorful number blocks. The goal is to find all the numbers that appear in at least two of those buckets.
A special tally sheet starts out empty. First, look at the first bucket and pick out one of each number found inside, then put a mark next to that number on the tally sheet. Do the same thing for the second bucket and add another mark to the tally sheet if you see the same number again. Repeat this one more time for the third bucket.
After everything is marked, look at the tally sheet. Any number that has two or more marks next to it is a winner because it was found in at least two different buckets. You just point to those winning numbers to show them off.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Java | Python | TS | |||||
| WalkCCC | C++ | Java | Python | |||||||
| leetcode.ca | C++ | Java | Python | Go | Rust | TS | ||||
| Progiez | C++ | Java | Python | |||||||
| github | black-shadows | C++ | ||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| lkwq007 | Python | |||||||||
| muhammadfarhankt | Go | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| Progiez | C++, Java, Python | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| lkwq007 | Python | |||||||||
| muhammadfarhankt | Go | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java |
Videos
Solved On The Same Day
- problem 1995: Count Special Quadruplets
- problem 2022: Convert 1D Array Into 2D Array
- problem 2053: Kth Distinct String in an Array
- problem 2057: Smallest Index With Equal Value
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality