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
def findDifference(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 on the order of 10^6 scans of up to 1000 items each. It passes only because the constraints are small and does not scale.
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, which halves the search interval on every comparison.
import bisect
from typing import List
def findDifference(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 each array to a set once, then subtract in both directions.
from typing import List
def findDifference(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 involves distinct values and membership across collections, translate it into set operations: 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 express the whole answer in one line.