2215. Find the Difference of Two Arrays - Explanation

Description

You are 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]]

Example 2:

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

Output: [[3],[]]

Constraints:

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

1. Brute Force

class Solution:
    def findDifference(self, nums1: list[int], nums2: list[int]) -> list[list[int]]:
        res = [set(), set()]

        for num1 in nums1:
            found = False
            for num2 in nums2:
                if num1 == num2:
                    found = True
                    break
            if not found:
                res[0].add(num1)

        for num2 in nums2:
            found = False
            for num1 in nums1:
                if num1 == num2:
                    found = True
                    break
            if not found:
                res[1].add(num2)

        return [list(res[0]), list(res[1])]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$ .

2. Sorting

class Solution:
    def findDifference(self, nums1: list[int], nums2: list[int]) -> list[list[int]]:
        nums1.sort()
        nums2.sort()

        def helper(A, B):
            n, m = len(A), len(B)
            res = []

            j = 0
            prev = float('-inf')
            for num in A:
                if prev == num:
                    continue
                while j < m and B[j] < num:
                    j += 1
                if j == m or B[j] != num:
                    res.append(num)
                prev = num
            return res

        return [helper(nums1, nums2), helper(nums2, nums1)]

Time & Space Complexity

Time complexity: $O(n \log n + m \log m)$
Space complexity: $O(1)$ or $O(n + m)$ depending on the sorting algorithm.

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$ .

3. Hash Set

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        num1Set, num2Set = set(nums1), set(nums2)
        res1, res2 = [], []

        for num in num1Set:
            if num not in num2Set:
                res1.append(num)

        for num in num2Set:
            if num not in num1Set:
                res2.append(num)

        return [res1, res2]

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$ .

4. Hash Set Difference

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

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$ .