Find the Difference of Two Arrays — Problem & Solution
Find the Difference of Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find the Difference of Two Arrays is an easy coding problem on arrays and hash table, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0]holds every distinct value present innums1but not innums2;answer[1]holds every distinct value present innums2but not innums1.
Both lists must be sorted in ascending order. A list with nothing in it is returned as [].
Example 1
Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation: 1 and 3 are missing from nums2; 4 and 6 are missing from nums1.
Example 2
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation: Duplicates collapse: only the value 3 is unique to nums1, and nums2 adds nothing new.
Example 3
Input: nums1 = [5], nums2 = [5]
Output: [[],[]]
Constraints
1 <= nums1.length, nums2.length <= 1000-1000 <= nums1[i], nums2[i] <= 1000
Hints for Find the Difference of Two Arrays
Hint 1
The word distinct is the whole problem — a set on each side removes the duplicates for free.
Hint 2
Membership tests are what make this linear; scanning the other array per element is O(n·m).
Hint 3
Sort each result once at the end rather than keeping the sets ordered as you go.
How to solve Find the Difference of Two Arrays
Reduce both arrays to sets, then each answer is one filtered pass: keep the values of one set the other set does not contain.
Approach
- Build
s1fromnums1ands2fromnums2; duplicates disappear here. - Walk
s1and keep every values2is missing — that isanswer[0]. - Walk
s2and keep every values1is missing — that isanswer[1]. - Sort both lists ascending so the answer is unique.
Why it works
Set membership is exactly the predicate the statement asks about, and a set visits each distinct value once, so each element is reported at most once and no duplicate can survive.
Complexity
- Time —
O(n + m + k log k) where k is the answer size - Space —
O(n + m)
Pitfalls
- Returning duplicates — filtering the raw array instead of the set reports
3twice for[1,2,3,3]. - An empty side must still appear as
[]; dropping it gives a one-element answer.
Reference solution
Python
from typing import List
def findDifference(nums1: List[int], nums2: List[int]) -> List[List[int]]:
s1 = set(nums1)
s2 = set(nums2)
return [sorted(s1 - s2), sorted(s2 - s1)]Java
public static int[][] findDifference(int[] nums1, int[] nums2) {
TreeSet<Integer> s1 = new TreeSet<>();
TreeSet<Integer> s2 = new TreeSet<>();
for (int x : nums1) s1.add(x);
for (int x : nums2) s2.add(x);
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
for (int x : s1) { if (!s2.contains(x)) left.add(x); }
for (int x : s2) { if (!s1.contains(x)) right.add(x); }
int[][] out = new int[2][];
out[0] = new int[left.size()];
for (int i = 0; i < left.size(); i++) out[0][i] = left.get(i);
out[1] = new int[right.size()];
for (int i = 0; i < right.size(); i++) out[1][i] = right.get(i);
return out;
}C++
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
vector<int> left, right;
for (int x : s1) { if (!s2.count(x)) left.push_back(x); }
for (int x : s2) { if (!s1.count(x)) right.push_back(x); }
return { left, right };
}JavaScript
var findDifference = function(nums1, nums2) {
var s1 = {}, s2 = {};
for (var i = 0; i < nums1.length; i++) s1[String(nums1[i])] = true;
for (var j = 0; j < nums2.length; j++) s2[String(nums2[j])] = true;
var left = [], right = [];
for (var k in s1) { if (s2[k] !== true) left.push(Number(k)); }
for (var m in s2) { if (s1[m] !== true) right.push(Number(m)); }
left.sort(function(a, b) { return a - b; });
right.sort(function(a, b) { return a - b; });
return [left, right];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets