How to find intersection of two arrays ?

How to find intersection of two arrays ?

Given two arrays, write a function to compute the intersection of the two arrays

Example 1:

Input: nums1 = [2,3,4,5], nums2 = [4,6,7,5]

Output: [4,5] Explanation: This is because the intersection (common elements ) of these two arrays are [4, 5]

Example 2:

Input: nums1 = [1,3,5] nums2 = [4,5]

Output: [5] Explanation: This is because the intersection (common elements) of these two arrays are [5]

Note:

• Each element in the final intersection should appear as many times as it shows in both arrays.
• The result can be in any order.

Solution:

To find the intersection of two arrays, we can use simple sorting approach as follows:

1. Sort both the arrays.
2. Take three variables i, j, k. Initialize them with 0.
3. From nums1[i] and nums2[j] check whether:
   • nums1[i] < nums2[j], increment i as ++i.
   • nums1[i] > nums2[j], increment j as ++j.
   • nums1[i] == nums2[j], add the value to the resulting array and increment both i and j as well as k.
4. Return the resulting array which contains the final intersection.

Here to reduce the space complexity, we just add our resulting values to the nums1 array instead of creating a new array.

Java:

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            ++i;
        } else if (nums1[i] > nums2[j]) {
            ++j;
        } else {
            nums1[k++] = nums1[i++];
            ++j;
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}

Complexity Analysis:

• Time Complexity: O(nlogn + nlogm), n and m are length of given two arrays.
• Space Complexity: O(1).