LeetCode: Intersection of Two Arrays II
Another one from LeetCode (I'm impressed by how well and fast their site works!): https://leetcode.com/problems/intersection-of-two-arrays-ii/. Here it is:
We'll be optimizing for speed not necessarily space. The goal is to write an algorithm in O(len(nums1) + len(nums2)) with small constant. Here is the approach:
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].We'll be optimizing for speed not necessarily space. The goal is to write an algorithm in O(len(nums1) + len(nums2)) with small constant. Here is the approach:
- Use a hashTable and insert all the elements of nums1 into it
- Keep the value of each key as the number of instances of that key seen
- Have another hashTable which will store the overlapped elements
- Go thru the second array nums2 and whenever you see a match in the first hashTable, then
- Add the match to the overlapped hashTable
- Keep track of the number of elements added
- Reduce the count of elements in the first hashTable.
- Whenever that count hits zero, remove it from the first hashTable
- Finally transform the overlapped hashTable into an array and return it. Don't worry, you can initialize an empty array in C#.
This accomplishes the O(len(nums1) + len(nums2))-time as expected. Solution beats near 90% of all the other C# submissions. Code is below, hope you enjoy it, cheers, Marcelo.
public class Solution
{
public int[] Intersect(int[] nums1, int[] nums2)
{
if (nums1 == null || nums2 == null) return null;
Hashtable htOverlap = new Hashtable();
for (int i = 0; i < nums1.Length; i++)
{
if (htOverlap.ContainsKey(nums1[i])) htOverlap[nums1[i]] = (int)htOverlap[nums1[i]] + 1;
else htOverlap.Add(nums1[i], 1);
}
Hashtable htResults = new Hashtable();
int numElements = 0;
for (int i = 0; i < nums2.Length; i++)
{
if (htOverlap.ContainsKey(nums2[i]))
{
if (htResults.ContainsKey(nums2[i])) htResults[nums2[i]] = (int)htResults[nums2[i]] + 1;
else htResults.Add(nums2[i], 1);
numElements++;
htOverlap[nums2[i]] = (int)htOverlap[nums2[i]] - 1;
if ((int)htOverlap[nums2[i]] <= 0)
{
htOverlap.Remove(nums2[i]);
}
}
}
int[] results = new int[numElements];
int resultsIndex = 0;
foreach (int key in htResults.Keys)
{
int nOccurrences = (int)htResults[key];
for (int i = 0; i < nOccurrences; i++)
{
results[resultsIndex++] = key;
}
}
return results;
}
}
there are many ways to solve this problem and I believe 2 most straightforward implementations are:
ReplyDelete1) slightly optimized version of your approach
vector intersect(vector& nums1, vector& nums2) {
unordered_map count;
for (int num : nums1) ++count[num];
vector res;
for (int num : nums2) {
if (--count[num] >= 0) res.push_back(num);
}
return res;
}
2) sort both arrays and use a modified merge function:
vector intersect(vector& nums1, vector& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector res;
set_intersection(nums1.cbegin(), nums1.cend(), nums2.cbegin(), nums2.cend(), back_inserter(res));
return res;
}
I didn't bother implementing merge, since it's super easy anyways (keep 2 pointers, advance one with a smaller value or record and advance both when they point at equal values).
It's easy to spot that 2) implementation is O(N*logN+M*logM+MAX(M,N)), which can be simplified to O(N*logN+M*logM), but 1) is O(N+M). In practice though both implementations run in 9ms and I suspect that both algorithms are so efficient that overhead of growing the resulting vector dominates runtime. Which is why it is wise and frequently beneficial to preallocate array in advance, just like you did Marcelo :) But life is too short to spend time on optimizing something that runs in 9ms :)