How do you approach Intersection of Two Arrays II?

Use a hash map to count occurrences of each element in one array.

What is the time complexity of Intersection of Two Arrays II?

Time complexity: O(n + m). Space complexity: O(min(n, m)).

What are common mistakes on Intersection of Two Arrays II?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

gitGood.dev

← Back to problems

Intersection of Two Arrays II

EasyData Structures

Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2,2]

Example 2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [4,9]

Explanation: [9,4] is also accepted.

Constraints

- 1 <= nums1.length, nums2.length <= 1000 - 0 <= nums1[i], nums2[i] <= 1000

Intersection of Two Arrays II: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

Use a hash map to count occurrences of each element in one array.
Iterate through the second array and check if the element exists in the map.
Decrement the count when you add an element to the result.

The optimal approach

Show the approach: Hash Map

Count elements in the smaller array using a hash map, then iterate through the larger array, adding to result if count > 0.

Time: O(n + m)
Space: O(min(n, m))

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.