TL;DR
Two set differences — O(n + m) time, O(n + m) space.
Approach 1 — Brute force
For each element of one array, linearly scan the other array for membership, and linearly scan the output so far to avoid emitting duplicates.
from typing import List
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
def diff(a: List[int], b: List[int]) -> List[int]:
out: List[int] = []
for x in a:
if x not in b and x not in out:
out.append(x)
return out
return [diff(nums1, nums2), diff(nums2, nums1)]
Complexity: O(n · m) time (every in on a list is a linear scan), O(n + m) space for the output. At n = m = 1000 this is ~10^6 scans of up to 1000 items each — it passes here only because the constraints are tiny, and it collapses the moment they grow.
Approach 2 — Sort one side, binary search into it
The insight: the expensive part of the brute force is the linear membership scan. If the other array is sorted, membership drops to O(log m) via binary search — the classic divide-and-conquer lookup that halves the search interval on every comparison.
import bisect
from typing import List
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
def missing_from(source: List[int], other: List[int]) -> List[int]:
other_sorted = sorted(other)
result: List[int] = []
for x in set(source):
i = bisect.bisect_left(other_sorted, x)
if i == len(other_sorted) or other_sorted[i] != x:
result.append(x)
return result
return [missing_from(nums1, nums2), missing_from(nums2, nums1)]
Walkthrough on nums1 = [1,2,3], nums2 = [2,4,6], first half:
other_sorted = [2,4,6]; distinct sources: {1, 2, 3}.x = 1: bisect_left → 0, other_sorted[0] = 2 != 1 → missing, keep 1.x = 2: bisect_left → 0, other_sorted[0] = 2 → present, drop.x = 3: bisect_left → 1, other_sorted[1] = 4 != 3 → missing, keep 3.
First list: [1, 3] (as a set-iteration order; any order is accepted). Symmetrically the second list is [4, 6].
Complexity: O((n + m) log(n + m)) time dominated by the two sorts, O(n + m) space.
Approach 3 — Hash sets and set difference
The insight: deduplication and O(1) membership are both exactly what a hash set provides, and “in A but not in B” is the set-difference operator itself. Convert once, subtract twice.
from typing import List
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
s1, s2 = set(nums1), set(nums2)
return [list(s1 - s2), list(s2 - s1)]
Walkthrough on nums1 = [1,2,3,3], nums2 = [1,1,2,2]:
s1 = {1, 2, 3} — the duplicate 3 collapses on construction.s2 = {1, 2} — duplicates collapse likewise.s1 - s2 = {3}; s2 - s1 = {} (empty set).- Answer:
[[3], []].
Complexity: O(n + m) time on average, O(n + m) space. Each set difference visits each element of its left operand once with O(1) probes into the right.
Common pitfalls
- Forgetting to deduplicate:
[1,2,3,3] vs [1,1,2,2] must yield [3], not [3,3] — build sets before comparing, not after.
- Computing only one direction — the answer is asymmetric and needs both
s1 - s2 and s2 - s1.
- Assuming a particular output order: sets are unordered in Python, and LeetCode accepts any order here; don’t burn time sorting unless a judge demands it.
- Writing
s1 ^ s2 (symmetric difference) — that merges both directions into one set, losing which array each value came from.
Pattern takeaway
When a problem talks about distinct values and membership across collections, translate it straight into set algebra: construction deduplicates, and difference/intersection/union replace hand-rolled loops. The general Arrays & Hashing rule applies — any “is x in that other collection?” inner loop should become a hash lookup — and Python’s set operators let you say the whole answer in one expression.