349. Intersection of Two Arrays

Notes.md

Question: 349. Intersection of Two Arrays

Intution:

Time Complexity: $$O(Nlog(M))$$

Space Complexity: $$O(1)$$

Solution:

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        ArrayList<Integer> ans = new ArrayList<>();

        if (n <= m) {
            Arrays.sort(nums1);
            for (int i = 0; i < m; i++) {
                if (binarySearch(nums1, nums2[i]) && !ans.contains(nums2[i])) {
                    ans.add(nums2[i]);
                }
            }
        } else {
            Arrays.sort(nums2);
            for (int i = 0; i < n; i++) {
                if (binarySearch(nums2, nums1[i]) && !ans.contains(nums1[i])) {
                    ans.add(nums1[i]);
                }
            }
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    boolean binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) return true;
            else if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }

        return false;
    }
}