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