Python 0349.py
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
n1 = set(nums1)
n2 = set(nums2)
result = []
for a in n1:
if a in n2:
result.append(a)
return result
Difficulty
and has an acceptance rate of about 78% (2+ million submissions).
Typical patterns to solve this problem:
- Array
- Binary Search
- Hash Table
- Sorting
- Two Pointers
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 intersection method computes the set of distinct integers that appear in both input arrays nums1 and nums2. It returns these common values as a list without any particular ordering. The implementation relies on Python’s built-in set type to eliminate duplicates and to provide fast membership checks.
Key Steps
Convert the input arrays to sets
n1 = set(nums1)
n2 = set(nums2)
Both nums1 and nums2 may contain repeated elements. Converting each list to a set removes those repetitions, guaranteeing that each value is examined at most once in the subsequent loop. The conversion also prepares the data for constant-time membership queries.
Iterate over one set and test membership in the other
result = []
for a in n1:
if a in n2:
result.append(a)
The loop walks through every element a in the first set n1. For each element, the expression a in n2 checks whether the same value exists in the second set. Because n2 is a hash-based set, this containment test executes in constant time on average. When the test succeeds, the element is appended to the result list.
Return the collected common elements
return result
After the loop finishes, result holds all values that were present in both original arrays. The method returns this list directly to the caller.
Edge Cases Handled
The code gracefully manages several boundary conditions without additional logic. When either nums1 or nums2 is empty, converting an empty list to a set yields an empty set, causing the loop to execute zero times and the method to return an empty list. Duplicate values inside the original arrays are collapsed by the set conversion, so the output never contains repeated entries. The algorithm also works correctly when the inputs contain negative numbers, zero, or very large integers because the set operations are based on hash values rather than numeric ranges. If both input arrays consist of the same single element repeated many times, the conversion reduces them to a single-element set, and the loop adds that element once to the result.
Performance Optimizations
The primary optimization stems from the use of hash-based sets for both deduplication and membership testing. By eliminating duplicate entries up front, the algorithm avoids redundant comparisons that a naïve double-loop approach would incur. Membership checks (a in n2) are performed in constant time, which dramatically reduces the overall work compared with linear scans of a list. Building the result list incrementally with append avoids the overhead of repeatedly creating new list objects. The overall flow processes each distinct element of the first input exactly once, leading to an efficient execution profile even when the original arrays are large.
ELI5 - Simplified Explanation
Imagine there are two boxes filled with colorful building blocks labeled with different numbers. Some numbers appear in both boxes, while others are only in one.
First, the code takes all the blocks from the first box and puts them into a special tray that ignores any duplicates, so there is only ever one of each number. It does the exact same thing for the second box.
Next, a new empty basket is set out to collect the matching blocks. The code picks up every single block from the first tray one by one. It looks inside the second tray to see if it has the same number. If the number is hiding in both trays, it gets placed into the new basket. After checking every block, the basket holds all the numbers that both boxes shared.
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++ | Python | Java | TS | |||||||
| WalkCCC | C++ | Python | Java | |||||||||
| leetcode.ca | C++ | Python | C# | Java | JS | Go | PHP | TS | ||||
| LeetcodeHelp | C++ | Python | Java | |||||||||
| MemoryLimitExceeded | C++ | Python | ||||||||||
| Progiez | C++ | Python | Java | |||||||||
| github | BigEggStudy | C# | ||||||||||
| black-shadows | C++ | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| chenyanzhe | C++ | |||||||||||
| Dijkstra-Edu | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JS | |||||||||||
| fartem | Ruby | |||||||||||
| FelixFan1122 | C# | |||||||||||
| halfrost | Go | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| muhammadfarhankt | Go | |||||||||||
| pruthvikp | Python | |||||||||||
| qiyuangong | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| varunu28 | Java | |||||||||||
| XiaotaoGuo | C++ | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Python, Java | |||||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, PHP, Python, Python, TypeScript | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++, C++ | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| chenyanzhe | C++ | |||||||||||
| Dijkstra-Edu | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JavaScript | |||||||||||
| fartem | Ruby | |||||||||||
| FelixFan1122 | C# | |||||||||||
| halfrost | Go | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| muhammadfarhankt | Go | |||||||||||
| pruthvikp | Python | |||||||||||
| qiyuangong | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| varunu28 | Java | |||||||||||
| XiaotaoGuo | C++ | |||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 350: Intersection of Two Arrays II
- problem 1213: Intersection of Three Sorted Arrays
- problem 2085: Count Common Words With One Occurrence
- problem 2215: Find the Difference of Two Arrays
- problem 2248: Intersection of Multiple Arrays
- problem 2540: Minimum Common Value
- problem 3002: Maximum Size of a Set After Removals
Solved On The Same Day
- problem 342: Power of Four
- problem 344: Reverse String
- problem 345: Reverse Vowels of a String
- problem 350: Intersection of Two Arrays II
- problem 387: First Unique Character in a String
- problem 412: Fizz Buzz
- problem 414: Third Maximum Number
- problem 434: Number of Segments in a String
- problem 448: Find All Numbers Disappeared in an Array
- problem 485: Max Consecutive Ones
- problem 504: Base 7
- problem 507: Perfect Number
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