Solution 1 - Hash Map (Counter)

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays. Use a hash map to count occurrences in the smaller array, then iterate through the other array and collect matches while decrementing counts.

TimeComplexity: O(m + n)

SpaceComplexity: O(min(m, n))

""" 0350.1 - Intersection of Two Arrays II - Solution 1 - Hash Map (Counter) """

#####################################################################################
# Imports
#####################################################################################
from typing import List
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """Intersection of Two Arrays II Function"""
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)

        counts = Counter(nums1)
        result = []

        for num in nums2:
            if counts[num] > 0:
                result.append(num)
                counts[num] -= 1

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().intersect([1, 2, 2, 1], [2, 2]))           # [2, 2]
    print(Solution().intersect([4, 9, 5], [9, 4, 9, 8, 4]))     # [4, 9]
    print(Solution().intersect([1, 2], [1, 1]))                  # [1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Sorting with Two Pointers

Sort both arrays, then use two pointers to walk through them simultaneously. When elements match, add to the result and advance both pointers. Otherwise, advance the pointer pointing to the smaller element.

TimeComplexity: O(m \log m + n \log n)

SpaceComplexity: O(1)

""" 0350.2 - Intersection of Two Arrays II - Solution 2 - Sorting with Two Pointers """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """Intersection of Two Arrays II Function"""
        nums1.sort()
        nums2.sort()

        i, j = 0, 0
        result = []

        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().intersect([1, 2, 2, 1], [2, 2]))           # [2, 2]
    print(Solution().intersect([4, 9, 5], [9, 4, 9, 8, 4]))     # [4, 9]
    print(Solution().intersect([1, 2], [1, 1]))                  # [1]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0350 - Intersection of Two Arrays II

Solution 1 - Hash Map (Counter)

Solution 2 - Sorting with Two Pointers