Abstract / Summary

Given two integer arrays, find all elements that appear in both arrays, each appearing as many times as they show in both arrays.

Note

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

This problem is ranked as

and has an acceptance rate of about 60% (3+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Hash Table
• Sorting
• Two Pointers

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.

Overview

The provided implementation computes the intersection of two integer arrays, returning each common element as many times as it appears in both arrays. It builds a frequency table for the first array, then walks through the second array, collecting elements that still have a positive count in the table. The result preserves the multiplicity of intersecting values without requiring additional sorting or auxiliary structures beyond the frequency map.

Building the Frequency Table

The first phase creates a hash-based counter that records how many times each value occurs in the first input list. By using a defaultdict(int), the code avoids explicit existence checks when incrementing counts.

freq = defaultdict(int)
for a in nums1:
    freq[a] += 1

Each iteration updates the dictionary in constant time, ensuring that the table accurately reflects the multiplicity of every element in nums1.

Collecting Intersecting Elements

The second phase iterates over the second list. For each element, the code checks two conditions: the element must be present as a key in the frequency table, and its associated count must be greater than zero. When both hold, the element is appended to the result list and the stored count is decremented, guaranteeing that an element is emitted no more times than it appears in nums1.

result = []
for a in nums2:
    if a in freq and freq[a] > 0:
        result.append(a)
        freq[a] -= 1

The decrement step is crucial; it prevents over-counting when the same value appears multiple times in nums2 but fewer times in nums1.

Edge Cases Handled

When either input list is empty, the frequency table or the iteration loop simply produces no entries, and the function returns an empty list. Duplicate values are correctly managed because the frequency table tracks exact counts, and the decrement operation limits the number of times a duplicate can be added to the result. The algorithm also works with negative integers and zero, as the dictionary keys are the raw integer values without any transformation. Extremely large integer values pose no issue because Python’s integer type handles arbitrary precision, and the hash table stores them directly.

Performance Optimizations

The use of a hash map (defaultdict) provides constant-time average access for both incrementing counts and checking membership, eliminating the need for sorting or binary search. By decrementing the count in place, the code avoids a secondary data structure to remember which elements have already been matched. The result list is built incrementally, which is more efficient than concatenating strings or creating intermediate collections. Overall, the algorithm processes each input element exactly once, leading to a streamlined execution path.

Imagine there are two boxes filled with colorful toy blocks. Some blocks have the same shape, like a red square or a blue circle. The goal is to find out which blocks appear in both boxes and put them into a new container.

First, look through the first box and keep a tally of every single block shape found. Think of this like making a secret list where each number tells how many of a specific toy exist in that box.

After the list is ready, look at the second box one block at a time. For every block held in your hand, check the secret list to see if that same shape is inside the first box and if there are any left over to share. If the shape is on the list and at least one is available, put that block into the new container and cross one off the list so it cannot be used again. By the time every block in the second box has been checked, the new container holds all the matching pairs found in both groups.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

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

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#	JS	Java	Go	Rust			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++
	everthis				JS
	fartem								Ruby
	FelixFan1122			C#
	fpdjsns	C++
	Garvit244		Python
	halfrost						Go
	haoel	C++
	JoshCrozier				JS
	Krazune	C++
	linouk23	C++
	lkwq007		Python
	muhammadfarhankt						Go
	qiyuangong		Python
	ruoru							Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28					Java
	vli02									C
	withaarzoo	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, 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++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
Krazune	C++
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
withaarzoo	C++
XiaotaoGuo	C++
zfang399	C++

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