Logo
    Akhil Abraham
    Akhil Abraham
    0350 - Intersection of Two Arrays II
    0350 - Intersection of Two Arrays II

    0350 - Intersection of Two Arrays II

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/intersection-of-two-arrays-ii/

    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)TimeComplexity: O(m + n)TimeComplexity:O(m+n)
    SpaceComplexity:O(min(m,n))SpaceComplexity: O(min(m, n))SpaceComplexity:O(min(m,n))

    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(mlog⁡m+nlog⁡n)TimeComplexity: O(m \log m + n \log n)TimeComplexity:O(mlogm+nlogn)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    """ 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()

    """ 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()