Leetcode 349: Intersection of two arrays

By /

The original question can be found here.

The question is aksing for the intersection of two arrays, and element in final result should be unique. There’re multiple solutions for this question.

Hash Set

Load one array into a hashset, and iterate through the second array. Once we find the element in second array is also in hashset, we know this element is in final result. However, we’ll have problems for making sure the elements in result is unique. So actually we can load both arrays into 2 hashsets to avoid duplication.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1, set2 = set(nums1), set(nums2)
        return [element for element in set1 if element in set2]

Don’t panic if see this solution is too concise and hard to understand. It took me quite a while to refactor it.

Time complexity: O(m + n). Space complexity: O(m + n).

Sort & 2 Pointers

We can sort 2 arrays and use 2 pointers to iterate through the sorted 2 arrays together. Once we find both elements equal, then it’s a candidate that we may want to put into the final result.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        nums1_index, nums2_index = 0, 0
        result = []
        while nums1_index < len(nums1) and nums2_index < len(nums2):
            if nums1[nums1_index] == nums2[nums2_index]:
                if not result or result[-1] != nums1[nums1_index]:
                    result.append(nums1[nums1_index])
                nums1_index += 1
                nums2_index += 1
            elif nums1[nums1_index] < nums2[nums2_index]:
                nums1_index += 1
            else:
                nums2_index += 1
        return result

Time complexity: O(m*lg(m)+n*lg(n)). Space complexity: O(1). You might be asking why the space complexity is O(1) since we use result array. That’s because this array is what we use for holding the intersected elements and return to the caller, so won’t be counted as extra space usage.

Sort & Binary Search

We can sort 1 array and perform binary search on this array. But I think the solution 2 is more straightforward, so I’ll skip this solution.

Scroll to Top