Welcome to Subscribe On Youtube

349. Intersection of Two Arrays

Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

 

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]
Explanation: [4,9] is also accepted.

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

Solutions

Use a HashSet to put all nums1 in, and then traverse the elements of nums2. If it exists in the HashSet, it means that it is the intersection part, add it to the HashSet of the result, and finally convert the result to the form of a vector.

Or, use two pointers to do it, first sort the two arrays, then use the two pointers to point to the beginning of the two arrays respectively, then compare the size of the two arrays, move the pointer of the small number backward, if the two pointers point to The numbers are equal, add this number to the result.

Python set() operations

Python uses the & operator for intersection, and various methods like .intersection(), to find common elements between sets. Here’s how you can perform set operations in Python:

Intersection (Common elements in both sets)

  • Using the & operator: 
    set1 = {1, 2, 3}
set2 = {2, 3, 4}
intersection = set1 & set2
print(intersection)  # Output: {2, 3}
  • Using the .intersection() method: 
    intersection = set1.intersection(set2)
print(intersection)  # Output: {2, 3}

Union (All elements from both sets, without duplication)

  • Using the | operator: 
    union = set1 | set2
print(union)  # Output: {1, 2, 3, 4}
  • Using the .union() method: 
    union = set1.union(set2)
print(union)  # Output: {1, 2, 3, 4}

Difference (Elements in the first set but not in the second)

  • Using the - operator: 
    difference = set1 - set2
print(difference)  # Output: {1}
  • Using the .difference() method: 
    difference = set1.difference(set2)
print(difference)  # Output: {1}

Symmetric Difference (Elements in either of the sets, but not in both)

  • Using the ^ operator: 
    symmetric_difference = set1 ^ set2
print(symmetric_difference)  # Output: {1, 4}
  • Using the .symmetric_difference() method: 
    symmetric_difference = set1.symmetric_difference(set2)
print(symmetric_difference)  # Output: {1, 4}

These are some of the basic set operations supported in Python, which allow for efficient computation on sets, utilizing their inherent properties to perform operations like intersection, union, difference, and symmetric difference.

  • class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        boolean[] s = new boolean[1001];
        for (int x : nums1) {
            s[x] = true;
        }
        List<Integer> ans = new ArrayList<>();
        for (int x : nums2) {
            if (s[x]) {
                ans.add(x);
                s[x] = false;
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

  • class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        bool s[1001];
        memset(s, false, sizeof(s));
        for (int x : nums1) {
            s[x] = true;
        }
        vector<int> ans;
        for (int x : nums2) {
            if (s[x]) {
                ans.push_back(x);
                s[x] = false;
            }
        }
        return ans;
    }
};

  • class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

############

# counting
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt = Counter(nums1 + nums2)
        return [x for x in arr1 if cnt[x] == 2]

############

'''
https://docs.python.org/3/reference/expressions.html#operator-precedence

high to low:

**

*, @, /, //, %

+, -

<<, >>

&

^

|

in, not in, is, is not, <, <=, >, >=, !=, ==

and

or

if – else


'''
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        s = set(nums1)
        res = set()
        for num in nums2:
            if num in s:
                res.add(num)
        return list(res)

############

# no extra space
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        nums1.sort()
        nums2.sort()
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                # ans.append(nums1[i]) # for Leetcode 350, input with duplicates
                if (not ans) or (len(ans) > 0 and ans[-1] != nums1[i]):
                    ans.append(nums1[i])
                i += 1
                j += 1

        return ans

############

class Solution(object):
  def intersection(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    d = {}
    ans = []
    for num in nums1:
      d[num] = d.get(num, 0) + 1

    for num in nums2:
      if num in d:
        ans.append(num)
        del d[num]
    return ans



  • func intersection(nums1 []int, nums2 []int) (ans []int) {
	s := [1001]bool{}
	for _, x := range nums1 {
		s[x] = true
	}
	for _, x := range nums2 {
		if s[x] {
			ans = append(ans, x)
			s[x] = false
		}
	}
	return
}

  • /**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
    const s = Array(1001).fill(false);
    for (const x of nums1) {
        s[x] = true;
    }
    const ans = [];
    for (const x of nums2) {
        if (s[x]) {
            ans.push(x);
            s[x] = false;
        }
    }
    return ans;
};


  • class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        $rs = [];
        $set1 = array_values(array_unique($nums1));
        $set2 = array_values(array_unique($nums2));
        for ($i = 0; $i < count($set1); $i++) {
            $hashmap[$set1[$i]] = 1;
        }
        for ($j = 0; $j < count($set2); $j++) {
            if ($hashmap[$set2[$j]]) {
                array_push($rs, $set2[$j]);
            }
        }
        return $rs;
    }
}

  • public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        List<int> result = new List<int>();
        HashSet<int> arr1 = new(nums1);
        HashSet<int> arr2 = new(nums2);
        foreach (int x in arr1) {
            if (arr2.Contains(x)) {
                result.Add(x);
            }
        }
        return result.ToArray();
    }
}

All Problems

All Solutions