Intersection Of Two Arrays - Leetcode Solution

Problem Statement: Given two arrays, write a function to compute their intersection.

Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]

Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4]

Note: Each element in the result must be unique. The result can be in any order.

Solution: We can solve this problem using various approaches. Here, we will discuss two solutions.

Solution 1: Simple Approach Using HashSet One of the simplest solutions to this problem is to use a HashSet. We can create two HashSets, one for each array. Then, we can loop over one of the HashSets and check if that element exists in the other HashSet. If it does, we add it to the result set. Finally, we return the elements present in the result set.

Code:

class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<>(); Set<Integer> set2 = new HashSet<>(); for(int num : nums1) { set1.add(num); } for(int num : nums2) { set2.add(num); } Set<Integer> resultSet = new HashSet<>(); for(int num : set1) { if(set2.contains(num)) { resultSet.add(num); } } int[] result = new int[resultSet.size()]; int i = 0; for(int num : resultSet) { result[i++] = num; } return result; } }

Time Complexity: O(n+m) Space Complexity: O(n+m)

Solution 2: Using Sorting and Two Pointers Another solution to this problem is to sort both arrays and use two pointers to find the common elements. We can sort both arrays first, and then create two pointers, one for each array. We can then compare the values at the current pointers. If they are equal, we add the value to the result set. Otherwise, we move the pointer with the smaller value. We repeat this process until we reach the end of one of the arrays.

Code:

class Solution { public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); Set<Integer> resultSet = new HashSet<>(); int i = 0; int j = 0; while(i < nums1.length && j < nums2.length) { if(nums1[i] == nums2[j]) { resultSet.add(nums1[i]); i++; j++; } else if(nums1[i] < nums2[j]) { i++; } else { j++; } } int[] result = new int[resultSet.size()]; int k = 0; for(int num : resultSet) { result[k++] = num; } return result; } }

Time Complexity: O(nlogn + mlogm) Space Complexity: O(n+m)

Conclusion: In this article, we discussed two different solutions to the Intersection of Two Arrays problem on LeetCode. The first solution is a simple approach using HashSets, and the second solution is a bit complex but more space-efficient using sorting and two pointers.

1