Find the Difference of Two Arrays

Difficulty: Easy | Acceptance: 81.40% | Paid: No Topics: Array, Hash Table

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.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sorting and Two Pointers
• Approach 3: Hash Set

Examples

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[0]=1 and nums1[2]=3 are not present in nums2.
For nums2, nums2[1]=4 and nums2[2]=6 are not present in nums1.

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2]=3 and nums1[3]=3 are not present in nums2.
For nums2, there are no integers that are not present in nums1.

Constraints

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

Approach 1: Brute Force

Intuition Iterate through each element of the first array and check if it exists in the second array. Repeat the process for the second array against the first.

Steps

• Initialize two empty lists, diff1 and diff2.
• Loop through each number x in nums1. If x is not found in nums2 and not already in diff1, add it to diff1.
• Loop through each number x in nums2. If x is not found in nums1 and not already in diff2, add it to diff2.
• Return [diff1, diff2].

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        res1, res2 = [], []
        for x in nums1:
            if x not in nums2 and x not in res1:
                res1.append(x)
        for x in nums2:
            if x not in nums1 and x not in res2:
                res2.append(x)
        return [res1, res2]

Complexity

• Time: O(n * m), where n and m are the lengths of the arrays.
• Space: O(n + m) to store the result lists.
• Notes: Simple to implement but inefficient for large inputs.

Approach 2: Sorting and Two Pointers

Intuition Sort both arrays to easily identify unique elements and skip duplicates using two pointers.

Steps

• Sort nums1 and nums2.
• Initialize two pointers i and j to 0, and result lists diff1, diff2.
• While both pointers are within bounds:
  • If nums1[i] == nums2[j], advance both pointers to skip all duplicates of this value.
  • If nums1[i] < nums2[j], nums1[i] is unique to nums1. Add it to diff1 and advance i skipping duplicates.
  • If nums1[i] > nums2[j], nums2[j] is unique to nums2. Add it to diff2 and advance j skipping duplicates.
• Process remaining elements in either array.

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        nums1.sort()
        nums2.sort()
        i, j = 0, 0
        res1, res2 = [], []
        n, m = len(nums1), len(nums2)
        while i < n and j < m:
            if nums1[i] == nums2[j]:
                val = nums1[i]
                while i < n and nums1[i] == val: i += 1
                while j < m and nums2[j] == val: j += 1
            elif nums1[i] < nums2[j]:
                val = nums1[i]
                res1.append(val)
                while i < n and nums1[i] == val: i += 1
            else:
                val = nums2[j]
                res2.append(val)
                while j < m and nums2[j] == val: j += 1
        while i < n:
            val = nums1[i]
            res1.append(val)
            while i < n and nums1[i] == val: i += 1
        while j < m:
            val = nums2[j]
            res2.append(val)
            while j < m and nums2[j] == val: j += 1
        return [res1, res2]

Complexity

• Time: O(n log n + m log m) due to sorting.
• Space: O(1) auxiliary space (excluding output and sorting stack).
• Notes: Better time complexity than brute force but modifies input or requires copies.

Approach 3: Hash Set

Intuition Use Hash Sets to store elements of both arrays. Set difference operations efficiently find elements present in one set but not the other.

Steps

• Convert nums1 to a set set1 and nums2 to a set set2.
• Compute the difference set1 - set2 to find elements unique to nums1.
• Compute the difference set2 - set1 to find elements unique to nums2.
• Convert the resulting sets back to lists and return them.

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

Complexity

• Time: O(n + m), where n and m are the lengths of the arrays.
• Space: O(n + m) to store the sets.
• Notes: Most optimal time complexity for this problem.