# 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:  Explanation: This is because the intersection (common elements) of these two arrays are 

#### 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).
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]