Problem of The Day: Intersection of Two Arrays

3 min read 683 words

Problem Statement

leetcode problem link

Solution [Accepted]

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

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        var uniqueNums1 = nums1.Distinct().ToHashSet();
        var uniqueNums2 = nums2.Distinct().ToHashSet();
        List<int> res = new List<int>();
        foreach(var num in uniqueNums1) {
            if (uniqueNums2.Contains(num)) {
                res.Add(num);
            }
        }
        return res.ToArray();
    }
}

• time: O(n + m)
• space: O(n + m)

Editorial

Approach 1: Sorting and Two Pointers

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # Sort both arrays
        nums1.sort()
        nums2.sort()

        # Initialize two pointers
        N = len(nums1)
        M = len(nums2)
        p1 = 0
        p2 = 0

        # Create set that stores integers appearing in both arrays
        intersection = set()

        while p1 < N and p2 < M:
            # Add a value to the set if values at both pointers equal
            if nums1[p1] == nums2[p2]:
                intersection.add(nums1[p1])
                p1 += 1
                p2 += 1
            elif nums1[p1] < nums2[p2]:
                p1 += 1
            else:
                p2 += 1

        # Convert intersection to an array
        result = []
        for x in intersection:
            result.append(x)

        # Return the result
        return result

Approach 2: Built-in Set Intersection

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        set1 = set(nums1)
        set2 = set(nums2)
        return list(set2 & set1)

Approach 3: Two Sets

class Solution:
    def set_intersection(self, set1, set2):
        return [x for x in set1 if x in set2]

    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        set1 = set(nums1)
        set2 = set(nums2)

        if len(set1) < len(set2):
            return self.set_intersection(set1, set2)
        else:
            return self.set_intersection(set2, set1)