349_Intersection of Two Arrays
[Easy][Array, Two Pointers, Binary Search, Hash Table, Sort]
Given two arrays, write a function to compute their intersection.
Note:
Each element in the result must be unique.
The result can be in any order.
Example 1:
Example 2:
Solution 1: Sort + Binary Search
Idea:
Sort the two arrays first.
Loop over each element in one array, use binary search to find if that element exist in the other array.
We can choose smaller length array for the loop, such that the time complexity will be smaller.
This approach has advantage if one array is much smaller in size than the other one.
Time Complexity: or
Space Complexity:
Solution 2: Sort + Two Pointers
Idea:
First sort the two arrays.
Simultaneously advance through the two arrays in increasing order. At each iteration:
If the two elements differ, eliminate the small one.
If they are the same, append to output and advance both.
If the length of two arrays are similar, this solution has advantage.
Time Complexity:
Space Complexity:
Solution 3: Dictionary
Idea:
Count frequency of each number in nums1, store in a dictionary.
Loop for each element in nums2, check if it has a pair in the dictionary. If yes, append the element, and decrease the corresponding frequency by 1.
Time Complexity:
Space Complexity: or , can choose the smaller one.
Last updated