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=0ptr2=0result=[]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)