Approach
I am getting back into the swing of things after a much needed weekend off. This morning, I thought I'd continue with knocking out the "easys" from the Leetcode 75 Study Plan.
This problems asks to return a vector of 2 vectors, each containing the unique items from inputs nums1 and nums2, respectively. I used C++ for this simply out of fimilarity -- most of my undergrad at Penn State World Campus was taught in C++ with some Java sprinkled in so we'll just stick with that.
To solve this, we will use an unordered_map to store who has what since the problem states that the answer can be returned in any order. This should save on time complexity when inserting elements.
Using JSON to describe what this map could look like after looking at all the elements from both input vectors, and using the example here is what I imagined:
{
1 : 1
2 : -1
3 : 1
4 : 2
6 : 2
}
This tells us that 1 is exclusively in nums1, 2 is in both as indicated by the -1 flag, 3 is exclusively in nums1, and the remaining are exclusively in nums2.
Let's stop here and code this up.
I'll start by looping over nums1 and insert everything into the map with the value set to 1.
Next, I'll loop over num2 but here we will perform a quick if-else statement to check if m[i] is already a 1. This is our indication that this item already exists and the -1 flag should be set. Otherwise, I will set the value in the map for that item to 2.
By the way, I used 1 and 2 because I wasn't sure how unordered_maps treat the initial values for elements accessed that weren't explicitly set yet. Something worth researching.
The next step is seemingly complicated but I simply want to loop over the map's keys and build the return value. To do this I use an iterator for the map and for each key-value pair I check using an if-else statement if the key's value is a 1 or a 2 and place it in the respective result vector.
Lastly, I return the result vector.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Code
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> m;
for(int i : nums1){
m[i] = 1;
}
for(int i : nums2){
if(m[i] == 1) m[i] = -1;
else if (m[i] == NULL) m[i] = 2;
}
vector<vector<int>> res = vector<vector<int>>(2);
for(auto i = m.begin(); i != m.end(); ++i){
if(i->second == 1){
res[0].push_back(i->first);
} else if (i->second == 2) {
res[1].push_back(i->first);
}
}
return res;
}
};