Find the Difference of Two Arrays

Easy
599.

Find the Difference of Two Arrays

Find the Difference of Two Arrays is an easy coding problem on arrays and hash table, asked in Amazon and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[][]}
 */
var findDifference = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 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

Hints for Find the Difference of Two Arrays

  1. Hint 1

    The word distinct is the whole problem — a set on each side removes the duplicates for free.

  2. Hint 2

    Membership tests are what make this linear; scanning the other array per element is O(n·m).

  3. 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

  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)]

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