Problem 349

Abstract / Summary

Find the unique elements that appear in both arrays.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
10 lines | 272 bytes | submitted August 13, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.56 | σ = 0.79

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
50 links | 33 authors | 11 languages

Videos

7 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

7 similar problems

Solved On The Same Day

12 easy
13 solutions   August 13, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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