algoadvance

Leetcode 2215. Find the Difference of Two Arrays

Problem Statement

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

1. answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
2. answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Example:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]

Clarifying Questions

1. Can the integers in the arrays be negative?
   • Yes.
2. Can the arrays contain duplicate numbers?
   • Yes, but we are only interested in distinct integers.
3. What should be the order of elements in the output lists?
   • The order of elements in the output lists does not matter.
4. Can the arrays be empty?
   • Yes, the arrays can be empty.

Strategy

1. Use Sets for Distinct Elements: Convert nums1 and nums2 to sets, called set1 and set2, to automatically handle distinct integers.
2. Difference Calculation:
   • For answer[0]: find elements in set1 that are not in set2.
   • For answer[1]: find elements in set2 that are not in set1.
3. Convert to Lists: The problem requires the final result to be in the form of lists of integers.

Code

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        // Convert arrays to sets to handle distinct elements
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        
        for (int num : nums1) {
            set1.add(num);
        }
        
        for (int num : nums2) {
            set2.add(num);
        }
        
        // Find elements in set1 not in set2
        List<Integer> list1 = new ArrayList<>();
        for (int num : set1) {
            if (!set2.contains(num)) {
                list1.add(num);
            }
        }
        
        // Find elements in set2 not in set1
        List<Integer> list2 = new ArrayList<>();
        for (int num : set2) {
            if (!set1.contains(num)) {
                list2.add(num);
            }
        }
        
        // Prepare the answer
        List<List<Integer>> answer = new ArrayList<>();
        answer.add(list1);
        answer.add(list2);
        
        return answer;
    }
}

Time Complexity

• Conversion to Sets (O(n) and O(m) where n is the length of nums1 and m is the length of nums2): Each integer from the arrays is added to a set.
• Difference Calculation (O(n + m)): Each set element is checked against the other set.

Overall, the time complexity is O(n + m), where n and m are the lengths of the input arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?