Given two integer arrays, impleemnt a function that returns their intersection — the set of elements that appear in both arrays, with each result appearing only once regardless of frequency.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]<br></br>Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]<br></br>Output: [4,9] (order does not matter)

Approach 1: Hash Set Intersection

This method leverages hash sets to eliminate duplicates and enable O(1) average lookup. First, convert one array into a Set. Then iterate over the second array, collecting values present in the set while avoiding duplicates using a second set or streaming with distinct().

Refactored implementation:

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int[] findCommonElements(int[] firstArr, int[] secondArr) {
        Set<Integer> baseSet = Arrays.stream(firstArr)
                                       .boxed()
                                       .collect(Collectors.toSet());
        
        return Arrays.stream(secondArr)
                     .distinct()
                     .filter(baseSet::contains)
                     .toArray();
    }
}

Complexity:
– Time: O(m + n), where m and n are the lengths of the input arrays.
– Space: O(m + n), dominated by storage for the sets.

Approach 2: Sorted Two-Pointer Technique

Sort both arrays first. Then use two pointers starting at index 0. Advance the pointer pointing to the smaller value. When values match, append to the result only if it differs from the last added element — ensurign uniqueness without auxiliary collections.

Optimized version with clean variable names and minimal state:

import java.util.Arrays;

class Solution {
    public int[] findCommonElements(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        
        int i = 0, j = 0, k = 0;
        int[] buffer = new int[Math.min(a.length, b.length)];
        
        while (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                if (k == 0 || a[i] != buffer[k - 1]) {
                    buffer[k++] = a[i];
                }
                i++;
                j++;
            } else if (a[i] < b[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        return Arrays.copyOf(buffer, k);
    }
}

Complexity:
– Time: O(m log m + n log n), due to sorting.
– Space: O(log m + log n) for internal sort recursion stack (e.g., in Java’s dual-pivot quicksort).