Finding the Intersection of Two Unsorted Arrays in Java

In programming, we often encounter problems that require us to find the intersection of two unsorted arrays. For instance, we might want to find the common elements in two lists of numbers, such as the numbers that appear in both lists. In Java, there are several ways to solve this problem, each with its own advantages and disadvantages.

Problem Statement

Let's start by defining the problem. Given two unsorted arrays of unique integers, we want to find the intersection of the two arrays, i.e., the set of all integers that appear in both arrays. For example, if we have the following two arrays:

arr1 = {7, 2, 9, 15, 10} arr2 = {5, 10, 7, 3, 2, 20, 9}

Then the intersection of arr1 and arr2 is {7, 10, 2, 9}, since these are the only integers that appear in both arrays.

Approaches

There are several approaches we can take to find the intersection of two unsorted arrays in Java. Let's discuss each of them in turn.

Approach 1: Linear Search

The simplest approach is to use a linear search to iterate over the first array and check if each element appears in the second array. If it does, we add it to a new array that stores the intersection. Here's the pseudocode for this approach:

csharp
void printIntersection(int[] arr1, int[] arr2) {
    List<Integer> intersection = new ArrayList<Integer>();
    for (int i = 0; i < arr1.length; i++) {
        for (int j = 0; j < arr2.length; j++) {
            if (arr1[i] == arr2[j]) {
                intersection.add(arr1[i]);
                break;
            }
        }
    }
    System.out.println(intersection);
}

The time complexity of this approach is O(m*n), where m and n are the lengths of the two arrays, since we need to compare each element in arr1 to each element in arr2.

Approach 2: Sorting and Binary Search

A more efficient approach is to sort one of the arrays and then use binary search to check if each element in the other array appears in the sorted array. Here's the pseudocode for this approach:

sql
void printIntersection(int[] arr1, int[] arr2) {
    List<Integer> intersection = new ArrayList<Integer>();
    Arrays.sort(arr2);
    for (int i = 0; i < arr1.length; i++) {
        if (binarySearch(arr2, arr1[i])) {
            intersection.add(arr1[i]);
        }
    }
    System.out.println(intersection);
}

boolean binarySearch(int[] arr, int x) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == x) {
            return true;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

The time complexity of this approach is O((m+n) log n), where m and n are the lengths of the two arrays, since we need to sort one of the arrays (which takes O(n log n) time) and then perform binary search on each element in the other array (which takes O(log n) time) for each element. However, this approach can be further optimized to achieve a better time complexity.

One way to improve the time complexity is to use a hashmap to store the elements of one of the arrays and then iterate over the other array to check if each element is present in the hashmap. This approach reduces the time complexity to O(m + n) since we only need to iterate over each element once and the lookup operation in a hashmap takes O(1) time on average.

To implement this approach, we can first create a hashmap and populate it with the elements of the smaller array. Then, we can iterate over the larger array and check if each element is present in the hashmap. If an element is found, we add it to the result array.

Here's an example implementation of this approach in Python:

python
def intersection(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    hashmap = {}
    for num in nums1:
        hashmap[num] = 1

    result = []
    for num in nums2:
        if num in hashmap and hashmap[num] > 0:
            result.append(num)
            hashmap[num] -= 1

    return result

In this implementation, we first check which of the two arrays is smaller and use it to populate the hashmap. Then, we iterate over the larger array and check if each element is present in the hashmap. If an element is found, we add it to the result array and decrement its count in the hashmap. This is necessary to handle cases where there are duplicate elements in one or both arrays.

With this approach, the time complexity is reduced to O(m + n) and the space complexity is O(min(m, n)) since we are storing the elements of the smaller array in the hashmap.

In conclusion, there are several ways to find the intersection of two arrays in an efficient manner. By using a hashmap to store the elements of one array, we can achieve a time complexity of O(m + n), which is better than the O((m + n) log n) time complexity of the binary search approach.