Vultr DocsLatest Content

Find the Difference of Two Arrays

Updated on 29 May, 2025
Find the Difference of Two Arrays header image

Problem Statement

The task involves two integer arrays, nums1 and nums2, which are indexed starting from 0. We need to determine the elements from each of these arrays that are not present in the other array. The final output should be a list called answer containing two sub-lists:

  1. The first sub-list should include all unique integers from nums1 that are absent in nums2.
  2. The second sub-list should feature all distinct integers from nums2 that do not appear in nums1.

It's important to note that the order in which integers appear in the sub-lists is irrelevant, and only distinct integers from each list should be considered, ensuring no repetitions within the sub-lists.

Examples

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 nums1. 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 and Intuition

The primary goal is to compare two lists and efficiently find unique elements in each that are absent in the other. Let's break down the approach using the given examples, incorporating practical constraints:

  1. Convert each list (nums1 and nums2) into a set to eliminate any duplicate items, ensuring all elements we handle are distinct.
  2. To find elements in nums1 not present in nums2, subtract the set derived from nums2 from the set of nums1.
  3. Similarly, derive elements exclusive to nums2 by subtracting the set of nums1 from the set of nums2.
  4. Compile these resulting sets into two sublist components of the final answer list.

Steps to Implement:

  1. Initialize two sets, set1 and set2, from nums1 and nums2 respectively.
  2. Calculate the difference between set1 and set2 to create the first sublist in the answer.
  3. Compute the difference between set2 and set1 for the second sublist in the answer.
  4. Construct the final output list using these two differences.

This approach is efficient given the constraints, as set operations such as difference are typically fast, and converting the arrays to sets also removes any duplicate items, simplifying our process. Moreover, handling up to 1000 elements in each list is computationally feasible with this method.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    vector<int> uniqueElements(vector<int>& list1, vector<int>& list2) {
        unordered_set<int> distinctElements;
        unordered_set<int> setList2(list2.begin(), list2.end());

        for (int item : list1) {
            if (setList2.find(item) == setList2.end()) {
                distinctElements.insert(item);
            }
        }

        return vector<int>(distinctElements.begin(), distinctElements.end());
    }

    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        return {uniqueElements(nums1, nums2), uniqueElements(nums2, nums1)};
    }
};

The provided C++ code defines methods for finding unique elements in two different arrays that are not present in the other. This process is accomplished using a combination of functions and C++ Standard Library containers, specifically unordered_set and vector.

  • First, the uniqueElements function is declared, which computes elements present in one list but absent in another. It starts by creating an unordered_set named setList2, which stores all the elements from the second list. It then iterates through the first list and checks if any of its elements are not found in setList2. If an element is unique to the first list, it is added to another unordered_set called distinctElements. This set, which holds unique elements, is converted back to a vector before being returned.

  • The findDifference function serves to return the unique elements from both input lists as separate vectors packed into a single vector. It calls the uniqueElements function twice:

    • Once with the first list as the primary list and the second list as the comparison target.
    • Once with the roles of the lists reversed.

The result is a vector of vectors, where the first nested vector contains elements unique to the first input list and the second nested vector contains elements unique to the second input list. This approach ensures that the differences between two arrays are comprehensively and efficiently harvested.

java 
class Solution {
    List<Integer> uniqueElementsFromFirst(int[] firstArray, int[] secondArray) {
        Set<Integer> uniqueToFirst = new HashSet<>();
        
        Set<Integer> elementsInSecond = new HashSet<>();
        for (int elem : secondArray) {
            elementsInSecond.add(elem);
        }
        
        for (int elem : firstArray) {
            if (!elementsInSecond.contains(elem)) {
                uniqueToFirst.add(elem);
            }
        }
        
        return new ArrayList<>(uniqueToFirst);
    }
    
    public List<List<Integer>> findDifference(int[] first, int[] second) {
        return Arrays.asList(uniqueElementsFromFirst(first, second), uniqueElementsFromFirst(second, first));
    }
}

This solution addresses the problem of finding elements that are unique to each of two arrays using Java. The approach utilizes sets to facilitate quick lookups and ensure unique element storage. Here's a breakdown of the methods used in the solution:

  • uniqueElementsFromFirst(int[] firstArray, int[] secondArray): This method identifies elements that are unique to the firstArray compared to the secondArray.

    • A HashSet called elementsInSecond is created to store elements of secondArray for quick lookup.
    • Another HashSet called uniqueToFirst is employed to capture unique elements from firstArray.
    • The method iterates through firstArray, and for each element, it checks if it is not in elementsInSecond. If it isn't present, the element is added to uniqueToFirst.
    • It finally returns a new ArrayList containing all elements from uniqueToFirst.

  • findDifference(int[] first, int[] second): This public method serves to find the differences from both perspectives:

    • It calls uniqueElementsFromFirst first for elements unique to first and not in second, and then with the arrays reversed to find elements unique to second and not in first.
    • It wraps and returns these lists in a single list.

Ensure the arrays are non-null to avoid NullPointerException. The use of sets helps in achieving an average-case time complexity of O(n), where n is the length of the arrays, making this method efficient for large sized arrays.

Comments

No comments yet.