Similar Problems

Similar Problems not available

Intersection Of Two Arrays - Leetcode Solution

LeetCode:  Intersection Of Two Arrays Leetcode Solution

Difficulty: Easy

Topics: hash-table binary-search two-pointers array sorting  

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.

Intersection Of Two Arrays Solution Code

1class Solution {
2public:
3    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
4        // set up our return vector and our two sets
5        vector<int> ret;
6        unordered_set<int> s1;
7        unordered_set<int> s2;
8        
9        // insert all values from nums1 into our first set
10        for (int i : nums1) {
11            s1.insert(i);
12        }
13        
14        // insert all values from nums2 into our second set
15        for (int i : nums2) {
16            s2.insert(i);
17        }
18        
19        // if our first set is smaller than our second, we iterate through it
20        if (s1.size() < s2.size()) {
21            for (int i : s1) {
22                // if the value is also in our second set, we add it to our return vector
23                if (s2.find(i) != s2.end()) {
24                    ret.push_back(i);
25                }
26            }
27        // otherwise, we iterate through our second set
28        } else {
29            for (int i : s2) {
30                // if the value is also in our first set, we add it to our return vector
31                if (s1.find(i) != s1.end()) {
32                    ret.push_back(i);
33                }
34            }
35        }
36        
37        // return our vector of intersection values
38        return ret;
39    }
40};