[LeetCode] Intersection of Two Arrays II

Problem: 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 and you may return the result in any order.

Example:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Approach: We can sort both the arrays and then we can use two pointers approach. The algorithm looks like follows:

• Sort(num1)
• Sort(num2)
• result = []
• i = 0, j = 0, k = 0
• WHILE i < COUNT(num1) AND j < COUNT(num2)
• IF num1[i] < num2[j]
• i = i + 1
• ELSE IF num1[i] > num2[j]
• j = j + 1
• ELSE
• result[k] = num1[i]
• i = i + 1
• j = j + 1
• k = k + 1
• RETURN result

This approach will take O(nlogn) time but is very useful and fast if arrays are sorted. 

Another approach would be to simply use the hashing here to solve this question. You can look at the implementation to understand the approach.

Implementation in C#:

    public int[] Intersect(int[] nums1, int[] nums2) 

    {

        Dictionary<int, int> frequencies = new Dictionary<int, int>();

        int[] arrayToBuildHash = nums1.Length < nums2.Length ? nums1 : nums2;

        int[] arrayToIterate = nums1.Length < nums2.Length ? nums2 : nums1;

        this.FillNumsWithCount(arrayToBuildHash, frequencies);

        return this.GetIntersection(arrayToIterate, frequencies);

    }

    

    private int[] GetIntersection(int[] nums, Dictionary<int, int> frequencies)

    {

        List<int> commonNums = new List<int>();

        foreach(int num  in nums)

        {

            if (frequencies.ContainsKey(num))

            {

                commonNums.Add(num);

                --frequencies[num];

                if (frequencies[num] == 0)

                {

                    frequencies.Remove(num);

                }

            }

        }

        return commonNums.ToArray();

    }

    

    private void FillNumsWithCount(int[] nums, Dictionary<int, int> frequencies)

    {

        foreach(int num in nums)

        {

            if (!frequencies.ContainsKey(num))

            {

                frequencies[num] = 0;

            }

            ++frequencies[num];

        }

    }

Complexity: O(m + n)