{x}
blog image

Find the Difference of Two Arrays

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

Solution Explanation: Find the Difference of Two Arrays

This problem asks to find the unique elements present in one array but not in the other, and vice-versa, for two input arrays nums1 and nums2. The solution leverages the efficiency of hash tables (sets in many languages) to achieve optimal time complexity.

Approach:

  1. Convert to Sets: The input arrays are first converted into sets (HashSet in Java, C++, Go, Set in Python, JavaScript, TypeScript, array_flip in PHP, or similar data structures in other languages). Sets provide constant time complexity, O(1), on average, for add, contains, and remove operations, significantly improving performance compared to using arrays directly. This step handles duplicate removal efficiently as sets inherently store only unique values.

  2. Find Differences: We then iterate through the elements of each set. For each element in nums1, we check if it's present in the nums2 set. If not, it's a unique element and is added to the result list answer[0]. The same process is repeated for nums2, adding unique elements to answer[1].

Time Complexity Analysis:

  • Converting each array to a set takes O(n) time, where n is the maximum length of the input arrays (nums1 or nums2).
  • Iterating through each set and checking for membership in the other set also takes O(n) time on average, due to the constant time lookup in sets.
  • Therefore, the overall time complexity of the solution is O(n), linear with respect to the input size.

Space Complexity Analysis:

  • We use sets to store the unique elements of each array. In the worst case, both sets could hold all unique elements from their respective arrays. Therefore, the space complexity is O(n) in the worst case. This is because the space used is proportional to the number of unique elements in the input arrays.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, PHP):

The provided code snippets demonstrate this approach in various programming languages. All of them follow the same basic steps: converting to sets, iterating, and checking for membership to find the unique elements. The specific set and list/array implementations may vary slightly between languages but the underlying algorithm remains consistent. Pay attention to how each language handles set operations and list/array creation.

Example: Python

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

This Python solution is particularly concise, utilizing set difference operations (s1 - s2) to directly obtain the unique elements. This leverages Python's built-in set functionality for a very efficient and readable solution. The other languages provide similar capabilities, albeit with slightly different syntax.