Solution For Intersection Of Two Arrays

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 set1 = new HashSet<>();
Set set2 = new HashSet<>();
for(int num : nums1) {
set1.add(num);
}
for(int num : nums2) {
set2.add(num);
}
Set 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 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.

Step by Step Implementation For Intersection Of Two Arrays

/**
 * Given two arrays, write a function to compute their intersection.
 * 
 * Example:
 * Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
 * 
 * Note:
 * Each element in the result must be unique.
 * The result can be in any order.
 */
 
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // create a set to store the unique elements of nums1
        Set set = new HashSet<>();
        for(int i : nums1) {
            set.add(i);
        }
        
        // create a list to store the intersection of the two arrays
        List list = new ArrayList<>();
        
        // iterate through nums2 and check if each element is in the set
        // if it is, add it to the list (this will ensure that there are no duplicates)
        for(int i : nums2) {
            if(set.contains(i)) {
                list.add(i);
            }
        }
        
        // convert the list to an array and return it
        return list.stream().mapToInt(i->i).toArray();
    }
}

def intersection(nums1, nums2):
    # create a set from nums1
    nums1_set = set(nums1)
    
    # create a set from nums2
    nums2_set = set(nums2)
    
    # find the intersection of the two sets
    intersection = nums1_set & nums2_set
    
    # return the intersection as a list
    return list(intersection)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    //Create an empty set
    let set = new Set()
    
    //Loop through the first array and add each element to the set
    for(let i = 0; i < nums1.length; i++) {
        set.add(nums1[i])
    }
    
    //Create another empty set
    let result = new Set()
    
    //Loop through the second array and check if each element is in the first set
    //If it is, add it to the result set
    for(let i = 0; i < nums2.length; i++) {
        if(set.has(nums2[i])) {
            result.add(nums2[i])
        }
    }
    
    //Return the result set as an array
    return [...result]
};

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        // set up our return vector and our two sets
        vector ret;
        unordered_set s1;
        unordered_set s2;
        
        // insert all values from nums1 into our first set
        for (int i : nums1) {
            s1.insert(i);
        }
        
        // insert all values from nums2 into our second set
        for (int i : nums2) {
            s2.insert(i);
        }
        
        // if our first set is smaller than our second, we iterate through it
        if (s1.size() < s2.size()) {
            for (int i : s1) {
                // if the value is also in our second set, we add it to our return vector
                if (s2.find(i) != s2.end()) {
                    ret.push_back(i);
                }
            }
        // otherwise, we iterate through our second set
        } else {
            for (int i : s2) {
                // if the value is also in our first set, we add it to our return vector
                if (s1.find(i) != s1.end()) {
                    ret.push_back(i);
                }
            }
        }
        
        // return our vector of intersection values
        return ret;
    }
};

public int[] Intersect(int[] nums1, int[] nums2) { // create a hashset to store all elements in nums1 HashSet set = new HashSet(); foreach(int num in nums1) { set.Add(num); } // create a list to store all elements in nums1 that are also in nums2 List list = new List(); foreach(int num in nums2) { if(set.Contains(num)) { list.Add(num); // remove element from set so that we don't add duplicates set.Remove(num); } } // convert list to array and return return list.ToArray(); }