Problem Overview
LeetCode 2215 asks you to find the difference of two integer arrays nums1 and nums2. You must return a list of two lists: the first contains all distinct integers in nums1 that are not present in nums2, and the second contains all distinct integers in nums2 that are not present in nums1.
The requirement that results be distinct is key — even if a value appears multiple times in one array, it should appear at most once in the output list. This immediately suggests set-based thinking: sets enforce uniqueness automatically and support fast membership testing.
The problem guarantees arrays of length up to 1000 with values in [-1000, 1000]. Any O(n*m) or O((n+m) log(n+m)) solution fits the constraints, but the set-based O(n+m) approach is both optimal and the most readable.
- Return [answer1, answer2] where answer1 = elements in nums1 not in nums2
- answer2 = elements in nums2 not in nums1
- All integers in each output list must be distinct — no duplicates allowed
- 1 <= nums1.length, nums2.length <= 1000 and -1000 <= values <= 1000
- The output lists can be returned in any order
Set Difference Approach
The cleanest solution converts both input arrays to sets immediately. Converting nums1 to set1 removes any duplicate values in nums1, and similarly for set2 from nums2. This one-time conversion takes O(n+m) time and O(n+m) space.
With two sets in hand, computing the answer is trivial: set1 - set2 (set difference) produces all elements that are in set1 but not in set2. This is exactly answer1. Likewise, set2 - set1 produces answer2. Converting each resulting set back to a list gives the final output.
The total complexity is O(n+m) for building the sets and O(n+m) for the two set differences (each difference is O(size of first operand)). Space is O(n+m) to store the sets and results. This is asymptotically optimal since you must read all input elements at least once.
Python One-Liner
In Python this is literally the mathematical set difference operation. You can write it as: return [list(set(nums1) - set(nums2)), list(set(nums2) - set(nums1))]. Python's set subtraction operator '-' does it in one expression per direction — no loops needed.
Why Sets Are Perfect
Sets are ideal for this problem because they solve two requirements simultaneously. First, converting an array to a set automatically removes all duplicates — since the output lists must contain distinct integers, this requirement is satisfied for free without any extra deduplication logic.
Second, set membership checking is O(1) average case using a hash table internally. When computing set1 - set2, for each element in set1 the runtime checks whether it exists in set2 in constant time. This is what enables the overall O(n+m) complexity instead of the O(n*m) that a naive nested-loop approach would require.
The mathematical elegance of sets also makes the code self-documenting: anyone reading set1 - set2 immediately understands it as the set-theoretic difference, not just an implementation detail.
- 1Convert nums1 to set1 — O(n), removes duplicates automatically
- 2Convert nums2 to set2 — O(m), removes duplicates automatically
- 3Compute diff1 = set1 - set2 — O(n), elements in nums1 not in nums2
- 4Compute diff2 = set2 - set1 — O(m), elements in nums2 not in nums1
- 5Return [list(diff1), list(diff2)] — convert back to lists for the output
Brute Force Alternative
A brute force approach iterates over every element in nums1 and for each one checks whether it appears anywhere in nums2 using a linear scan. Elements not found in nums2 are added to a result set (to keep uniqueness). Then the process repeats in reverse for nums2 vs nums1.
This nested loop approach is O(n*m) time — for each of the n elements in nums1, the inner loop scans up to m elements of nums2. With n=m=1000, that is up to 1,000,000 operations. While this passes the given constraints, it is wasteful compared to the O(n+m) set solution.
Converting nums2 to a set first reduces the inner lookup from O(m) to O(1), immediately collapsing the brute force into the set-based O(n+m) solution. This demonstrates why set conversion is always the right first move for array intersection or difference problems.
Problem Design Intent
This problem is designed to test set operations knowledge. The brute force nested loop approach is intentionally slow to motivate the set solution — converting to sets before any comparisons is the key insight that transforms O(n*m) into O(n+m) and makes the code significantly cleaner.
Walk-Through Example
Consider nums1=[1,2,3] and nums2=[2,4,6]. Step one: build set1={1,2,3} and set2={2,4,6}. Step two: compute set1 - set2 = {1,3} (elements in set1 not in set2 — 2 is in set2, so it is excluded). Step three: compute set2 - set1 = {4,6} (2 is in set1 so excluded, 4 and 6 are not). Return [[1,3],[4,6]].
Now consider a case with duplicates: nums1=[1,1,2,3] and nums2=[2,2,4,6]. After conversion, set1={1,2,3} and set2={2,4,6} — the duplicate 1 in nums1 and duplicate 2 in nums2 are collapsed. The differences are identical to the previous example: [[1,3],[4,6]]. The set conversion handled deduplication transparently.
An edge case: nums1=[1,2,3] and nums2=[1,2,3]. Then set1={1,2,3} and set2={1,2,3}. set1 - set2 = {} and set2 - set1 = {}. Return [[], []] — both output lists are empty because every element of each array appears in the other.
- 1nums1=[1,2,3], nums2=[2,4,6]: set1={1,2,3}, set2={2,4,6}
- 2set1 - set2 = {1,3} (2 is excluded — it is in set2)
- 3set2 - set1 = {4,6} (2 is excluded — it is in set1)
- 4Return [[1,3],[4,6]]
- 5With duplicates nums1=[1,1,2,3]: set1={1,2,3} — same result, duplicates handled automatically
Code Walkthrough: Python and Java
Python one-liner: return [list(set(nums1) - set(nums2)), list(set(nums2) - set(nums1))]. This is idiomatic Python — set() constructor converts the list and deduplicates, the minus operator performs set difference, and list() converts back. An explicit version with named variables: s1, s2 = set(nums1), set(nums2); return [list(s1 - s2), list(s2 - s1)].
Java solution using HashSet: create HashSet<Integer> set1 from Arrays.asList(nums1) and similarly set2. For answer1, clone set1 and call removeAll(set2) to remove elements present in set2. For answer2, clone set2 and call removeAll(set1). Convert each resulting set to a List<Integer> and return as a nested list. Alternatively use stream filter: set1.stream().filter(x -> !set2.contains(x)).collect(Collectors.toList()).
Both Python and Java solutions run in O(n+m) time and O(n+m) space. The dominant cost is the set construction. The set difference operations are O(n) and O(m) respectively. The space is O(n+m) for storing the two sets plus the output lists.
Return Lists Not Sets
The problem expects List<List<Integer>> in Java and list[list[int]] in Python — not sets. Always convert sets back to lists before returning. In Python use list(diff), in Java use new ArrayList<>(set). Returning sets directly will cause a type error or wrong output format.