How do you approach Intersection of Two Arrays?

Duplicates inside one array don't matter - only membership does.

What is the time complexity of Intersection of Two Arrays?

Time complexity: O(n + m + k log k) - set construction plus sorting k common values. Space complexity: O(n + k) - the sets.

What are common mistakes on Intersection of Two Arrays?

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

EasyData Structures

Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique, and the result must be sorted in ascending order.

Note this differs from the "Intersection of Two Arrays II" variant: here duplicates are collapsed - each common value appears exactly once in the output.

Example 1

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

Output: [2]

Explanation: 2 is the only value present in both arrays; it appears once despite duplicates.

Example 2

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

Output: [4,9]

Explanation: Both 4 and 9 appear in each array. The result is sorted ascending.

Example 3

Input: nums1 = [1,2,3], nums2 = [4,5,6]

Output: []

Constraints

- 1 <= nums1.length, nums2.length <= 1000 - 0 <= nums1[i], nums2[i] <= 1000 - Return the result sorted in ascending order.

Intersection of Two Arrays: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 7 test cases (4 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

Duplicates inside one array don't matter - only membership does.
Convert one array to a set, then test each unique element of the other array against it.
Remember to sort the collected values ascending before returning (numeric sort, not lexicographic, in JavaScript).

The optimal approach

Show the approach: Two Hash Sets

Convert `nums1` to a set. Walk `nums2`, collecting into a result set every value that is also in the first set (the result set collapses duplicates from `nums2`). Finally, sort the result ascending. In JavaScript, remember `sort((a, b) => a - b)` - the default sort is lexicographic.

Time: O(n + m + k log k) - set construction plus sorting k common values
Space: O(n + k) - the sets

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.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

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.