Arrays Intersection

Array, Hash Table

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 1:

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

Example 2:

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

Constraints:

• 1 <= nums1.length, nums2.length <= 1000

• 0 <= nums1[i], nums2[i] <= 1000

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?

• What if num1's size is small compared to nums2's size? Which algorithm is better?

• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solutions

Approach - Brute Force Technique

It works by checking each element of the first array against the second array and adding it to the intersection if it exists. The second array is represented as a list so that elements can be easily removed. This ensures that each element is counted the correct number of times.

Steps

1. Initialize intersection and list2: A new List intersection is created to store the intersection of nums1 and nums2. Another List list2 is created as a copy of nums2. This is done because elements will be removed from list2 during the process, and we don’t want to modify the original array.

2. Iterate over nums1: The method iterates over each element num in nums1.

3. Check if num exists in list2: For each num in nums1, the method checks if num exists in list2 using the Contains method.

4. Add num to intersection and remove from list2: If num exists in list2, it is added to intersection and removed from list2. The Remove method removes the first occurrence of num from list2. This ensures that each element in the intersection appears as many times as it shows in both arrays.

5. Return intersection as an array: After all elements in nums1 have been processed, the ToArray method is called on intersection to convert it back to an array before returning it as the result of the method.

public class Solution
{
    public int[] Intersect(int[] nums1, int[] nums2)
    {
        List<int> intersection = new List<int>();
        List<int> list2 = new List<int>(nums2);

        foreach (int num in nums1)
        {
            if (list2.Contains(num))
            {
                intersection.Add(num);
                list2.Remove(num);
            }
        }

        return intersection.ToArray();
    }
}

Approach - Hash Table Technique

Steps

1. Initialization: The function Intersect is defined with two parameters, nums1 and nums2, which are the input arrays. It initializes a dictionary dict to keep track of the frequency of each number in nums1, and a list res to store the result.

2. Create Frequency Dictionary: The function iterates over each number in nums1. For each number, it checks if the number is already a key in dict. If it is, it increments the value associated with that key. If not, it adds the number as a key to dict with a value of 1. This results in dict containing each unique number in nums1 as a key, and the frequency of that number as the value.

3. Find Intersection: The function then iterates over each number in nums2. For each number, it checks if the number is a key in dict and if the associated value is greater than 0. If both conditions are met, it means the number is present in both nums1 and nums2, so it adds the number to res and decrements the value associated with the number in dict.

4. Return Result: Finally, the function converts res to an array and returns it. This array contains the intersection of nums1 and nums2.

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        
        var dict = new Dictionary<int, int>();
        var res = new List<int>();

        foreach (var num in nums1)
        {
            if (dict.ContainsKey(num))
                dict[num]++;
            else
                dict[num] = 1;
        }

         foreach (var num in nums2)
        {
            if (dict.ContainsKey(num) && dict[num]>0)
            {
                res.Add(num);
                dict[num]--;
            }
        }

        return res.ToArray();
    }
}

Complexity

• Time complexity: O(N+M)

• Space complexity: O(N)