2215. Find the Difference of Two Arrays
Easy · solved 2026-10-01 · Open on LeetCode
hash-tablearray
Time O(n + m) · Space O(n + m)
How to get there
Only membership matters
1. Solve it by hand. For nums1 = [1, 2, 3, 3] and nums2 = [1, 1, 2, 2], take each value of nums1 and look for it in nums2: 1 is there, 2 is there, 3 is not, 3 is not. Two things go wrong at once: every lookup scans all of nums2, and 3 comes out twice.
2. Ask what the answer depends on. Only on which values each array contains. Order, position, and how often a value repeats change nothing. So each array can be reduced to its distinct values before comparing.
3. Pick the structure that answers “is x in there?” fast. A hashmap keyed by value does both jobs: writing a repeated value again leaves one key, which removes the duplicates, and a lookup takes constant time on average, where scanning the other array costs its whole length.
4. Compare key by key, in both directions. Loop over the keys of one map and keep those the other map lacks; then the same the other way round. Looping over keys rather than over the original array is what keeps each output list distinct.
The reusable recipe: when the answer depends only on whether values appear, reduce each collection to the keys of a hashmap and answer each question with a lookup.
Let the variables' meanings write the loops
| Variable | Always means |
|---|---|
in1, in2 |
their keys are the distinct values of nums1, nums2 read so far |
only1 |
the keys of in1 checked so far that are not in in2 |
only2 |
the keys of in2 checked so far that are not in in1 |
| Code | What happened | What it restores |
|---|---|---|
in1[x] = True |
one more value of nums1 was read |
it is a key; a repeat overwrites the same key, so nothing changes |
for x in in1: |
the comparison starts | each distinct value comes up exactly once |
if x not in in2: only1.append(x) |
one more key was checked | only1 holds it exactly when nums2 lacks it |
the same two lines with in2 and in1 swapped |
the other direction | only2 |
The True values are never read: only the keys matter, so the map acts as a set written out by hand.
The method carries over: say what each map’s keys stand for, then every loop either adds the next key or checks one, and nothing else.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| Nested scan | O(n · m) | O(n + m) | For each value, scan the other array for it; keep a list of values already output to skip repeats. |
| Sort and merge | O(n log n + m log m) | O(n + m) | Sort both arrays, then walk them together the way merge sort does, skipping repeats. |
| Two hashmaps (chosen) | O(n + m) | O(n + m) | Each array’s values become keys; a key is kept when the other map lacks it. |
| Set difference | O(n + m) | O(n + m) | set(nums1) - set(nums2) and the reverse: the same lookups, done by the set type. |
| Presence array | O(n + m + R) | O(R) | The values lie in −1000…1000, so a list of R = 2001 flags records which appear. |
The hashmaps make each check a constant-time lookup while every step stays written out. The presence array needs no hashing, but works only because the problem bounds the values.
solution.py
class Solution:
def findDifference(self, nums1: list[int], nums2: list[int]) -> list[list[int]]:
in1, in2 = {}, {}
for x in nums1:
in1[x] = True
for x in nums2:
in2[x] = True
only1 = []
for x in in1:
if x not in in2:
only1.append(x)
only2 = []
for x in in2:
if x not in in1:
only2.append(x)
return [only1, only2]Notes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.