Talentd
FleetCode
Make and follow sheets.Sign in

Find the Difference of Two Arrays solution and explanation

EasyArrayHash Table5 min read81.4% acceptanceUpdated 9 Apr 2026
Find the Difference of Two Arrays - Leetcode 2215 - PythonNeetCodeIO · 7:34 · 18K viewsWatch on YouTube
9 more videos on this problem
  1. Find the Difference of Two Arrays - Leetcode 2215 - PythonNeetCodeIO · 7:34 · 18K views
  2. Leetcode 2215 | Find the difference of two arrays | 20th from LC 75 | 90 days SE prepPepcoding · 3:51 · 4K views
  3. Leetcode | 2215. Find the Difference of Two Arrays | Easy | Java SolutionDeveloper Docs · 5:19 · 2K views
  4. Find the Difference of Two Arrays | Leetcode 2215 | 2 Approaches | Set | Maps Contest 286 🔥🔥Coding Decoded · 8:51 · 2K views
  5. Find the Difference of Two Arrays - LeetCode 2215 - Python #leetcode #leetcode75Deepti Talesra · 7:03 · 1K views
  6. Find the Difference of Two Arrays - Leetcode 2215Algorial · 3:52 · 1K views
  7. 💻Solving All LeetCode Problems with PYTHON 🐍 - 2215 Find the Difference of Two ArraysAlex Brou · 6:50 · 859 views
  8. 2215. Find the Difference of Two Arrays | JavaScript | LeetCode Daily ChallengeLeetCodeWithMonu · 13:44 · 849 views
  9. Find the Difference of Two Arrays - LeetCode 2215 - Python SolutionCode with Carter · 5:59 · 586 views
  10. 2215. Find the Difference of Two Arrays - Leetcode - Hashmap- C++ Tutorialcodetutorial4you · 9:22 · 532 views

The problem

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

  • answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
  • answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • -1000 <= nums1[i], nums2[i] <= 1000

Approach overview

Problem Overview: You are given two integer arrays nums1 and nums2. The task is to return two lists: elements that appear in nums1 but not in nums2, and elements that appear in nums2 but not in nums1. Each result must contain distinct values only.

This is essentially a set-difference problem. You compare the unique elements of both arrays and determine which values exist exclusively in one array. The challenge is avoiding duplicates while keeping the algorithm efficient.

Approach 1: Using Sorting to Solve the Problem (O(n log n) time, O(1) extra space)

This approach sorts both arrays first, then scans them to identify elements that appear in only one array. After sorting, you iterate through both arrays with two pointers. When values match, move both pointers. When one value is smaller, it means that value does not appear in the other array at that position, so it belongs in the result. Duplicate values are skipped during traversal to ensure the output only contains unique elements.

The main advantage is minimal extra memory usage since sorting allows comparison without additional hash structures. The tradeoff is the O(n log n) sorting cost. This approach is useful when memory is constrained or when the arrays are already sorted. Sorting-based comparisons are common patterns in array problems where duplicates must be handled carefully.

Approach 2: Using a HashMap for Efficient Lookup (O(n + m) time, O(n + m) space)

The optimal solution converts both arrays into hash sets. A set automatically removes duplicates and provides constant-time membership checks. First insert all elements from nums1 into a set and all elements from nums2 into another set. Then iterate through the first set and add elements not found in the second set to the result list. Repeat the same process in reverse for the second set.

The key insight is that hash lookups run in average O(1) time, so the comparison becomes linear overall. Building the sets costs O(n + m), and the difference checks also run in linear time. This approach is a classic application of hash tables for fast membership testing and is commonly used in problems involving deduplication and set operations on arrays.

Recommended for interviews: The hash-set approach is what interviewers typically expect. It demonstrates that you recognize the problem as a set-difference operation and can use constant-time lookups to reduce complexity to O(n + m). Discussing the sorting approach first can show baseline reasoning, but the hash-based solution signals stronger familiarity with common array + hash table optimization patterns.

Approach 1: Using Sorting to Solve the Problem

This approach involves first sorting the data to simplify the problem, allowing for efficient searching or manipulation afterwards. Sorting can often reduce the complexity of further operations by providing a clear ordering of elements.

Depending on the problem's specifics, sorting may allow for easier handling of duplicates or simplification of conditions. Note that the initial overhead of sorting is compensated by the reduced complexity of the subsequent operations.

def solve_problem(arr):
    arr.sort()
    # Further problem-specific logic goes here

arr = [5, 3, 8, 4, 2]
solve_problem(arr)
print(arr)
import java.util.Arrays;

public class Solution {
    public static void solveProblem(int[] arr) {
        Arrays.sort(arr);
        // Further problem-specific logic goes here
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        solveProblem(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
#include <iostream>
#include <vector>
#include <algorithm>

void solveProblem(std::vector<int>& arr) {
    std::sort(arr.begin(), arr.end());
    // Further problem-specific logic goes here
}

int main() {
    std::vector<int> arr = {5, 3, 8, 4, 2};
    solveProblem(arr);

    for(int i : arr) {
        std::cout << i << " ";
    }
    return 0;
}
function solveProblem(arr) {
    arr.sort((a, b) => a - b);
    // Further problem-specific logic goes here
}

const arr = [5, 3, 8, 4, 2];
solveProblem(arr);
console.log(arr.join(' '));
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

void solveProblem(int* arr, int size) {
    qsort(arr, size, sizeof(int), compare);
    // Further problem-specific logic goes here
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int size = sizeof(arr)/sizeof(arr[0]);
    solveProblem(arr, size);

    for(int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
using System;

class Solution {
    static void SolveProblem(int[] arr) {
        Array.Sort(arr);
        // Further problem-specific logic goes here
    }

    static void Main() {
        int[] arr = {5, 3, 8, 4, 2};
        SolveProblem(arr);

        Console.WriteLine(string.Join(" ", arr));
    }
}

This Python code sorts the list using the built-in sort() method. This simplifies the process of implementing further operations needed to solve the problem.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) because the sort is done in-place.

Try this approach in the editor

Approach 2: Using a HashMap for Efficient Lookup

In this approach, we utilize a HashMap (or a dictionary in languages like Python) to keep track of elements and perform efficient lookups. This is particularly useful when the problem requires checking for existence of elements or handling duplicates.

This approach reduces the time complexity of these operations to O(1) on average, which is significantly faster than scanning through an array.

def solve_problem(arr):
    hash_set = set()
    for num in arr:
        if num not in hash_set:
            hash_set.add(num)
            # Process this unique element

arr = [5, 3, 8, 4, 2]
solve_problem(arr)
import java.util.HashSet;

public class Solution {
    public static void solveProblem(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : arr) {
            if (!set.contains(num)) {
                set.add(num);
                // Process this unique element
            }
        }
        // Further problem-specific logic goes here
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        solveProblem(arr);
    }
}
#include <iostream>
#include <unordered_map>
#include <vector>

void solveProblem(const std::vector<int>& arr) {
    std::unordered_map<int, bool> hashMap;
    for (int num : arr) {
        if (hashMap.find(num) == hashMap.end()) {
            hashMap[num] = true;
            // Process this unique element
        }
    }
    // Further problem-specific logic goes here
}

int main() {
    std::vector<int> arr = {5, 3, 8, 4, 2};
    solveProblem(arr);
    return 0;
}
function solveProblem(arr) {
    const map = new Map();
    for (const num of arr) {
        if (!map.has(num)) {
            map.set(num, true);
            // Process this unique element
        }
    }
    // Further problem-specific logic goes here
}

const arr = [5, 3, 8, 4, 2];
solveProblem(arr);
#include <stdio.h>
#include <stdbool.h>
#define SIZE 100

bool hashTable[SIZE] = {false};

void solveProblem(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        if (!hashTable[arr[i]]) {
            hashTable[arr[i]] = true;
            // Process this unique element
        }
    }
    // Further problem-specific logic goes here
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    solveProblem(arr, size);
    return 0;
}
using System;
using System.Collections.Generic;

class Solution {
    static void SolveProblem(int[] arr) {
        HashSet<int> set = new HashSet<int>();
        foreach (int num in arr) {
            if (!set.Contains(num)) {
                set.Add(num);
                // Process this unique element
            }
        }
        // Further problem-specific logic goes here
    }

    static void Main() {
        int[] arr = {5, 3, 8, 4, 2};
        SolveProblem(arr);
    }
}

This Python solution uses a set to efficiently track elements, providing O(1) average time complexity for add and check operations.

Complexity

Time Complexity: O(n) for processing each element.
Space Complexity: O(n) for storing unique elements in the set.

Try this approach in the editor

Approach 3: Hash Table

We define two hash tables s1 and s2 to store the elements in arrays nums1 and nums2 respectively. Then we traverse each element in s1. If this element is not in s2, we add it to the first list in the answer. Similarly, we traverse each element in s2. If this element is not in s1, we add it to the second list in the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array.

function findDifference(nums1: number[], nums2: number[]): number[][] {
    const s1: Set<number> = new Set(nums1);
    const s2: Set<number> = new Set(nums2);
    nums1.forEach(num => s2.delete(num));
    nums2.forEach(num => s1.delete(num));
    return [Array.from(s1), Array.from(s2)];
}
func findDifference(nums1 []int, nums2 []int) [][]int {
	s1, s2 := make(map[int]bool), make(map[int]bool)
	for _, v := range nums1 {
		s1[v] = true
	}
	for _, v := range nums2 {
		s2[v] = true
	}
	ans := make([][]int, 2)
	for v := range s1 {
		if !s2[v] {
			ans[0] = append(ans[0], v)
		}
	}
	for v := range s2 {
		if !s1[v] {
			ans[1] = append(ans[1], v)
		}
	}
	return ans
}
use std::collections::HashSet;
impl Solution {
    pub fn find_difference(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<Vec<i32>> {
        vec![
            nums1
                .iter()
                .filter_map(|&v| if nums2.contains(&v) { None } else { Some(v) })
                .collect::<HashSet<i32>>()
                .into_iter()
                .collect(),
            nums2
                .iter()
                .filter_map(|&v| if nums1.contains(&v) { None } else { Some(v) })
                .collect::<HashSet<i32>>()
                .into_iter()
                .collect(),
        ]
    }
}
class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[][]
     */
    function findDifference($nums1, $nums2) {
        $s1 = array_flip($nums1);
        $s2 = array_flip($nums2);

        $diff1 = array_diff_key($s1, $s2);
        $diff2 = array_diff_key($s2, $s1);

        return [array_keys($diff1), array_keys($diff2)];
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Using Sorting to Solve the Problem

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) because the sort is done in-place.

Using a HashMap for Efficient Lookup

Time Complexity: O(n) for processing each element.
Space Complexity: O(n) for storing unique elements in the set.

Hash Table–

Complexity analysis

ApproachTimeSpaceWhen to Use
Sorting + Two PointersO(n log n + m log m)O(1) extra (excluding output)When memory is limited or arrays are already sorted
Hash Set / HashMap LookupO(n + m)O(n + m)General case and optimal interview solution with fast lookups

Frequently asked questions

Is Find the Difference of Two Arrays easy or hard?

This problem is categorized as Easy because it mainly tests understanding of hash sets and basic array iteration. Once you recognize it as a set-difference operation, the implementation becomes straightforward and runs in linear time.

Find the Difference of Two Arrays Python/Java solution

In Python, convert the arrays to sets and compute differences using membership checks or set subtraction. In Java, use HashSet<Integer> to store values from each array and iterate through them to build the result lists. Both implementations run in O(n + m) time.

How to solve Find the Difference of Two Arrays in O(n)?

Store elements of nums1 and nums2 in two hash sets. Iterate through the first set and collect elements not present in the second set, then repeat in the opposite direction. Because set membership checks are O(1) on average, the full algorithm runs in O(n + m) time.

What is the best approach for Find the Difference of Two Arrays?

The hash set approach is the most efficient and commonly expected solution. Convert both arrays into sets to remove duplicates, then check which elements from one set are missing in the other. Each lookup runs in O(1) average time, giving an overall time complexity of O(n + m) with O(n + m) space.

Is Find the Difference of Two Arrays asked at Google/Amazon/Meta?

Problems involving set difference, hash sets, and array deduplication frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying pattern of using hash tables for membership checks is very common in coding interviews.

What data structure is used in Find the Difference of Two Arrays?

Hash sets (or hash maps) are the primary data structures used in the optimal solution. They allow fast O(1) average-time membership checks and automatically remove duplicates, making them ideal for computing the difference between two arrays.

What is the time complexity of Find the Difference of Two Arrays?

The optimal solution runs in O(n + m) time where n and m are the lengths of the two arrays. This comes from building two hash sets and performing constant-time membership checks. A sorting-based solution exists but takes O(n log n + m log m) due to the sorting step.

Comments

Now write it yourselfClose this page and solve Find the Difference of Two Arrays in the editor, without looking.
Practise Find the Difference of Two Arrays