Find the Difference of Two Arrays — Easy Problem & Solution

Problem statement

Given two integer arrays nums1 and nums2, return a list answer of size 2 where:

• answer[0] holds every distinct value present in nums1 but not in nums2;
• answer[1] holds every distinct value present in nums2 but not in nums1.

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

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

1. Build s1 from nums1 and s2 from nums2; duplicates disappear here.
2. Walk s1 and keep every value s2 is missing — that is answer[0].
3. Walk s2 and keep every value s1 is missing — that is answer[1].
4. 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 3 twice 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)]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy