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

Approach1 :

Naive approach

iterate over nums1 , check if current number in nums1 is also in nums2 , if yes then append it to the result array and delete that element from nums2.

This is worst solution , since it takes o(n³) time , where n is the number of the items in the list. The complexity is n³, since

n (iterate on n ums1)*n(iterate on nums2)*n(deleting the item from nums2)

Space: 0(1)

Approach 2:

We iterate through nums2 generate a hashmap and keep count of each character in nums2. Then after this, we iterate through the nums1, and check whether the character currently being checking is present in the hash map, if yes, add this to the result and decrement the count of that character from the hashmap, as it is encountered.

Time :O(n1+n2)

Space : O(n2)

Approach 3:

Two pointer approach

Sort both arrays. Then iterate in both , simultaneously. Once finding the same character in both add to the result

nums1.sort()
nums2.sort()
ptr1=0
ptr2=0
result=[]
while(ptr1<len(nums1) and ptr2<len(nums2)):
   if(nums1[ptr1]<nums2[ptr2]):
      ptr1+=1   
   elif(nums2[ptr2]<nums1[ptr1]):
      ptr2+=1
   else:
      result.append(nums1[ptr1])
      ptr1+=1
      ptr2+=1

Time : n1 1og (n1) +n2 log (n

Space :O(1)