LeetCode Problem 2215

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 2215, Find the Difference of Two Arrays

Problem Understanding

This problem asks us to compare two integer arrays and identify the unique values that appear in one array but not the other.

We are given two 0-indexed integer arrays, nums1 and nums2. The goal is to return a list containing two separate lists:

• The first list should contain every distinct integer that exists in nums1 but does not exist in nums2.
• The second list should contain every distinct integer that exists in nums2 but does not exist in nums1.

The keyword "distinct" is extremely important. Even if a number appears multiple times in an array, it should only appear once in the result.

For example, if nums1 = [1,2,3,3] and nums2 = [1,1,2,2], the number 3 appears twice in nums1, but the output should contain only one 3.

The order of the returned integers does not matter, which gives us flexibility in implementation.

The constraints are relatively small:

• Each array length is at most 1000
• Values range from -1000 to 1000

Even though the constraints are small enough that multiple approaches would work, the problem is fundamentally about efficient membership checking and duplicate removal. This naturally suggests using hash-based data structures such as sets.

Several edge cases are important to consider:

• Arrays containing duplicates
• Arrays that are completely identical
• Arrays with no overlapping values
• Arrays containing negative integers
• Arrays where one side contributes an empty result list

The problem guarantees that both arrays contain at least one element, so we do not need to handle completely empty input arrays.

Approaches

Brute Force Approach

A straightforward solution is to examine each element in one array and manually check whether it exists in the other array.

For every value in nums1, we could scan through nums2 to see whether that value exists. If it does not exist, we add it to the result. We would repeat the same process in the opposite direction for nums2.

Because duplicates are possible, we would also need an additional mechanism to avoid adding the same number multiple times.

This approach works correctly because every element is explicitly compared against the other array. However, membership checking inside a loop leads to repeated scanning.

If n is the length of nums1 and m is the length of nums2, checking membership costs O(m) for each element in nums1, and similarly O(n) for elements in nums2.

This results in quadratic-style behavior.

Optimal Approach

The key observation is that we repeatedly need to answer the question:

"Does this value exist in the other array?"

A hash set is ideal for this because set membership checks are approximately O(1) on average.

We can convert both arrays into sets:

set1 = set(nums1)
set2 = set(nums2)

This immediately removes duplicates and allows fast lookups.

Then:

• Any value in set1 but not in set2 belongs in the first result list.
• Any value in set2 but not in set1 belongs in the second result list.

This can even be expressed directly using set difference operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(n + m)	Repeated linear membership checks
Optimal	O(n + m)	O(n + m)	Uses hash sets for fast lookup and duplicate removal

Algorithm Walkthrough

1. Convert nums1 into a hash set called set1.

This removes duplicates automatically and gives constant-time membership lookup. 2. Convert nums2 into a hash set called set2.

This serves the same purpose for the second array. 3. Create an empty list called only_in_nums1.

This will store numbers present in set1 but absent from set2. 4. Iterate through every value in set1.

For each value, check whether it does not exist in set2. If the value is missing from set2, append it to only_in_nums1. 5. Create another empty list called only_in_nums2.

This will store numbers present in set2 but absent from set1. 6. Iterate through every value in set2.

For each value, check whether it does not exist in set1. If it is missing, append it to only_in_nums2. 7. Return the final result as:

[only_in_nums1, only_in_nums2]

Why it works

The algorithm works because sets contain only distinct elements. Therefore, duplicates are eliminated automatically before comparison begins.

For every value in set1, we check whether the same value exists in set2. If it does not, that value must appear exclusively in nums1. The same logic applies symmetrically for values in set2.

Because every distinct value is checked exactly once against the opposite set, the algorithm correctly produces all required differences.

Python Solution

from typing import List

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1 = set(nums1)
        set2 = set(nums2)

        only_in_nums1 = []
        only_in_nums2 = []

        for num in set1:
            if num not in set2:
                only_in_nums1.append(num)

        for num in set2:
            if num not in set1:
                only_in_nums2.append(num)

        return [only_in_nums1, only_in_nums2]

The implementation begins by converting both input arrays into sets. This is the most important step because it simultaneously removes duplicates and enables fast membership checks.

Two result lists are then created. The first loop examines every unique value from nums1. If a value does not exist in set2, it belongs exclusively to nums1, so it is appended to only_in_nums1.

The second loop performs the same logic in reverse for values unique to nums2.

Finally, both result lists are returned together in the required format.

An alternative implementation could use direct set subtraction:

list(set1 - set2)

However, the explicit loops shown above make the algorithm easier to follow and explain.

Go Solution

func findDifference(nums1 []int, nums2 []int) [][]int {
    set1 := make(map[int]bool)
    set2 := make(map[int]bool)

    for _, num := range nums1 {
        set1[num] = true
    }

    for _, num := range nums2 {
        set2[num] = true
    }

    onlyInNums1 := []int{}
    onlyInNums2 := []int{}

    for num := range set1 {
        if !set2[num] {
            onlyInNums1 = append(onlyInNums1, num)
        }
    }

    for num := range set2 {
        if !set1[num] {
            onlyInNums2 = append(onlyInNums2, num)
        }
    }

    return [][]int{onlyInNums1, onlyInNums2}
}

Go does not have a built-in set type, so the implementation uses map[int]bool to simulate a hash set. The keys represent the stored values, and the boolean value is not particularly important beyond indicating presence.

Slices are used for the result lists. Empty slices are returned naturally when no unique values exist on one side.

There are no integer overflow concerns because the constraints are very small.

Worked Examples

Example 1

Input:

nums1 = [1,2,3]
nums2 = [2,4,6]

Step 1: Convert to sets

Variable	Value
set1	{1,2,3}
set2	{2,4,6}

Step 2: Find elements only in set1

Current Number	Exists in set2?	Action	Result
1	No	Add to result	[1]
2	Yes	Skip	[1]
3	No	Add to result	[1,3]

Step 3: Find elements only in set2

Current Number	Exists in set1?	Action	Result
2	Yes	Skip	[]
4	No	Add to result	[4]
6	No	Add to result	[4,6]

Final output:

[[1,3],[4,6]]

Example 2

Input:

nums1 = [1,2,3,3]
nums2 = [1,1,2,2]

Step 1: Convert to sets

Variable	Value
set1	{1,2,3}
set2	{1,2}

Notice that duplicates disappear automatically.

Step 2: Find elements only in set1

Current Number	Exists in set2?	Action	Result
1	Yes	Skip	[]
2	Yes	Skip	[]
3	No	Add to result	[3]

Step 3: Find elements only in set2

Current Number	Exists in set1?	Action	Result
1	Yes	Skip	[]
2	Yes	Skip	[]

Final output:

[[3],[]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Building sets and checking membership each require linear work
Space	O(n + m)	Additional storage is used for the two hash sets

The algorithm processes each element a constant number of times. Building the sets takes linear time, and iterating through the unique values also takes linear time.

The extra memory usage comes primarily from storing the two sets, which together may contain all unique elements from both arrays.

Test Cases

from typing import List

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1 = set(nums1)
        set2 = set(nums2)

        only_in_nums1 = []
        only_in_nums2 = []

        for num in set1:
            if num not in set2:
                only_in_nums1.append(num)

        for num in set2:
            if num not in set1:
                only_in_nums2.append(num)

        return [only_in_nums1, only_in_nums2]

sol = Solution()

# Example 1
result = sol.findDifference([1, 2, 3], [2, 4, 6])
assert set(result[0]) == {1, 3} and set(result[1]) == {4, 6}

# Example 2 with duplicates
result = sol.findDifference([1, 2, 3, 3], [1, 1, 2, 2])
assert result[0] == [3] and result[1] == []

# Completely identical arrays
result = sol.findDifference([1, 2, 3], [1, 2, 3])
assert result == [[], []]

# No overlap at all
result = sol.findDifference([1, 2], [3, 4])
assert set(result[0]) == {1, 2} and set(result[1]) == {3, 4}

# Negative numbers
result = sol.findDifference([-1, -2, 0], [-2, 1])
assert set(result[0]) == {-1, 0} and set(result[1]) == {1}

# Single element arrays
result = sol.findDifference([5], [5])
assert result == [[], []]

# One side empty after filtering
result = sol.findDifference([1, 2, 3], [1, 2])
assert result[0] == [3] and result[1] == []

# Large duplicate counts
result = sol.findDifference([7, 7, 7, 7], [8, 8, 8])
assert result[0] == [7] and result[1] == [8]

Test	Why
[1,2,3] vs [2,4,6]	Standard mixed overlap case
Duplicate-heavy input	Verifies duplicate elimination
Identical arrays	Ensures both outputs can be empty
No overlapping values	Confirms full separation behavior
Negative integers	Validates handling of signed values
Single-element arrays	Tests smallest valid input size
One empty result side	Ensures asymmetric outputs work
Repeated duplicates	Confirms uniqueness handling

Edge Cases

Arrays with Many Duplicates

A common bug is accidentally returning repeated values in the result. For example:

nums1 = [3,3,3]
nums2 = [1]

A naive implementation might incorrectly return [3,3,3]. Converting arrays into sets removes duplicates immediately, ensuring each value appears only once in the output.

Completely Identical Arrays

If both arrays contain exactly the same values, neither side should contribute any unique elements.

nums1 = [1,2,3]
nums2 = [1,2,3]

The correct output is:

[[], []]

The implementation handles this naturally because every membership check succeeds, so nothing is appended to either result list.

Arrays with No Overlap

If the arrays share no common values:

nums1 = [1,2]
nums2 = [3,4]

every value from both sets should appear in the result.

This case verifies that the implementation does not accidentally remove valid unique elements during comparison.

Negative Numbers

Since the constraints allow negative integers, the implementation must correctly handle values below zero.

Hash sets work uniformly for positive and negative integers, so no special handling is required. Values like -1000 are processed exactly the same way as positive values.