LeetCode 350. Intersection of Two Arrays II Java Solution

Problem Description

• Problem: Intersection of Two Arrays II

• Description: This problem involves finding the duplicate numbers in two arrays, nums1 and nums2.

Approach

• Idea: Use a HashMap to count the occurrences of each number in the arrays to check for duplicates. The challenge here is that each array can have duplicate numbers. If the arrays are not sorted, using a two-pointer method to check for duplicates is inefficient. Therefore, we use a HashMap to track the duplicate numbers.

• Algorithm:

  1. First, count the occurrences of each number in the nums1 array using a HashMap.

  2. Next, iterate through the nums2 array and check if the number exists in the HashMap. If the count is greater than 0, add the number to the result list and decrease the count in the HashMap.

Code

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> result = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        for (int val : nums1) {
            map.put(val, map.getOrDefault(val, 0) + 1);
        }

        for (int val : nums2) {
            if (map.getOrDefault(val, 0) > 0) {
                result.add(val);
                map.put(val, map.getOrDefault(val, 0) - 1);
            }
        }

        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;
    }
}

Conclusion

• Time Complexity: This algorithm iterates through both arrays once, resulting in O(m + n) time complexity, where m is the length of nums1 and n is the length of nums2.

• Space Complexity: The HashMap stores the frequency of each number, resulting in O(min(m, n)) space complexity, using the smaller of the two array lengths.