Why use sets instead of checking the other array directly?

Searching an array for each value is O(n · m). A hash set answers "is x in it?" in O(1) on average, so the whole job is O(n + m). The sets also remove duplicates, which the answer must not contain.

Do duplicates appear in the answer?

No. The answer lists distinct integers, so [1, 2, 3, 3] against [1, 1, 2, 2] gives [[3], []]: 3 is reported once. Iterating over the set rather than the original array handles this automatically.

Does the order of the answer matter?

No. LeetCode accepts the integers in each list in any order, which is why iterating a hash set, whose order is unspecified, is fine.

Can it be done with set difference operators?

Yes. In Python, [list(set1 - set2), list(set2 - set1)] does the same thing in one line. The loops in the template show what that operator does underneath.

Find the Difference of Two Arrays

List the distinct values that appear in only one of two arrays by turning each into a hash set and checking every value against the other set.

EasySolve on LeetCode

Problem Understanding

Find the Difference of Two Arrays (LeetCode 2215): given two integer arrays nums1 and nums2, return a list answer of two lists. answer[0] holds the distinct integers in nums1 that are not in nums2, and answer[1] the distinct integers in nums2 that are not in nums1. Either list may be in any order.

Examples: [1, 2, 3], [2, 4, 6] → [[1, 3], [4, 6]]; [1, 2, 3, 3], [1, 1, 2, 2] → [[3], []].

The Intuition: Ask the Set

Every value needs one question answered: is it in the other array? A hash set answers that in O(1), and it also drops the duplicates the answer is not allowed to have.

Make two sets. One per array.
Scan set1. Anything set2 lacks goes into answer[0].
Scan set2. Anything set1 lacks goes into answer[1].

It is the membership test from Contains Duplicate, run against a second set instead of the values seen so far.

Interactive Walkthrough

SET LOOKUPS · O(1) EACH

BUILD THE SETS

set1

set2

answer[0]

[ ]

answer[1]

[ ]

Put each array into a set: {1, 2, 3} and {2, 4, 6}

Is 1 in set2? No

Free preview: the first 4 of 12 steps

nums1

nums2

The filled cell is the value being looked up. When the other set has it too, that copy is outlined and the value is greyed out; values in only one set turn green. Try Example 2 to see duplicates collapse.

Dry Run Table

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

Scan	x	In the other set?	answer
set1	1	no	[[1], []]
set1	2	yes	[[1], []]
set1	3	no	[[1, 3], []]
set2	2	yes	[[1, 3], []]
set2	4	no	[[1, 3], [4]]
set2	6	no	[[1, 3], [4, 6]]

Answer: [[1, 3], [4, 6]].

The Solution Template

Two hash sets and two scans. The C version uses a boolean table indexed by value + 1000, since LeetCode limits the values to -1000..1000.

Find the Difference of Two Arrays Code

1var findDifference = function(nums1, nums2) {
2    const set1 = new Set(nums1), set2 = new Set(nums2);
3    const only1 = [], only2 = [];
4    for (const x of set1) {
5        if (!set2.has(x)) {
6            only1.push(x);
7        }
8    }
9    for (const x of set2) {
10        if (!set1.has(x)) {
11            only2.push(x);
12        }
13    }
14    return [only1, only2];
15};

Edge Cases & Common Mistakes

Scanning the arrays instead of the sets: a value repeated in nums1 would be added to the answer more than once.
Identical sets: [1, 2] and [2, 1, 1] hold the same values, so both lists are empty.
Negative values: fine for hash sets; a lookup table needs an offset, as in the C version.
Nested loops: checking each value against the whole other array is O(n · m) and gives up what the set buys.

Summary

Turn both arrays into hash sets, keep the values of set1 missing from set2 and the values of set2 missing from set1. O(n + m) time and space.

More practice: DSA interview questions with answers · patterns cheat sheet

Contains Duplicate

Unique Number of Occurrences