C++ || 4 different approaches || sort, unique, set_difference, set, unordered_set, copy_if, bitset
TODO(heder): Insert cute cat meme to ask for up-votes. ;)\n\nPlease let me know if you came up with another approach or if you have some suggestions how to impo
**TODO(heder): Insert cute cat meme to ask for up-votes. ;)**\n\nPlease let me know if you came up with another approach or if you have some suggestions how to imporve one of the following approaches.\n\n# Approach 1: std::sort, std::unique, and std::set_difference\n\nIn order to use ```std::set_difference``` the inputs need to be sorted, and since we are only looking for distinct numbers we need to call ```std::unique``` too. This approach modifies the input.\n\n```cpp\n    static vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {\n        sort(begin(nums1), end(nums1));\n        nums1.erase(unique(begin(nums1), end(nums1)), end(nums1));\n        sort(begin(nums2), end(nums2));\n        nums2.erase(unique(begin(nums2), end(nums2)), end(nums2));\n        vector<vector<int>> ans(2);\n        ans[0].reserve(size(nums1));\n        ans[1].reserve(size(nums2));\n        set_difference(begin(nums1), end(nums1), begin(nums2), end(nums2), back_inserter(ans[0]));\n        set_difference(begin(nums2), end(nums2), begin(nums1), end(nums1), back_inserter(ans[1]));\n        return ans;\n    }\n```\n\n**Complexity Analysis**\n\n* Time complexity: $$O(n \\log n)$$, because the run time is dominated by ```std::sort```, ```std::unique``` and ```std::set_difference``` are both linear.\n\n* Space complexity: $$O(1)$$ no extra memory needed. I am not taking the result into account. Maybe we should.\n\n## Variant 1: std::sort, std::unique, and rewrite in-place\n\nThis variant is inspired by @Satj, after we have sorted and "unique-yfied" the input we can rewrite them together.\n\n```cpp\n    static vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {\n        // sort and unique\n        sort(begin(nums1), end(nums1));\n        nums1.erase(unique(begin(nums1), end(nums1)), end(nums1));\n        sort(begin(nums2), end(nums2));\n        nums2.erase(unique(begin(nums2), end(nums2)), end(nums2));\n        int i1 = 0;\n        int i2 = 0;\n        int o1 = 0;\n        int o2 = 0;\n        // "merge"\n        while (i1 < size(nums1) && i2 < size(nums2)) {\n            if (nums1[i1] == nums2[i2]) {\n                ++i1;\n                ++i2;\n            } else if (nums1[i1] < nums2[i2]) {\n                nums1[o1++] = nums1[i1++];\n            } else {\n                nums2[o2++] = nums2[i2++];\n            }\n        }\n        // handle the rest\n        while (i1 < size(nums1)) nums1[o1++] = nums1[i1++];\n        nums1.resize(o1);\n        while (i2 < size(nums2)) nums2[o2++] = nums2[i2++];\n        nums2.resize(o2);        \n        return {nums1, nums2};   \n    }\n```\n\n**Complexity Analysis**\n\n* Time complexity: $$O(n \\log n)$$, because the run time is dominated by ```std::sort```, ```std::unique``` and "merge" and handling the rest are all linear.\n\n* Space complexity: $$O(1)$$ no extra memory needed, we don\'t even have extra output vectors.\n\n# Variant 2: std::sort and "merge" we de-duping\n\nWe can take this a step further and handle the unique elements while merging. The code gets quite long though.\n\n```cpp\n    static vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {\n        // sort\n        sort(begin(nums1), end(nums1));\n        sort(begin(nums2), end(nums2));\n        int i1 = 0;\n        int i2 = 0;\n        int o1 = 0;\n        int o2 = 0;\n        // "merge"\n        while (i1 < size(nums1) && i2 < size(nums2)) {\n            if (i1 > 0) {\n                while (i1 < size(nums1) && nums1[i1 - 1] == nums1[i1]) ++i1;\n                if (i1 == size(nums1)) break;\n            }\n            if (i2 > 0) {\n                while (i2 < size(nums2) && nums2[i2 - 1] == nums2[i2]) ++i2;\n                if (i2 == size(nums2)) break;\n            }\n            if (nums1[i1] == nums2[i2]) {\n                ++i1;\n                ++i2;\n            } else if (nums1[i1] < nums2[i2]) {\n                nums1[o1++] = nums1[i1++];\n            } else {\n                nums2[o2++] = nums2[i2++];\n            }\n        }\n        // handle the rest\n        while (i1 < size(nums1)) {\n            if (i1 > 0) {\n                while (i1 < size(nums1) && nums1[i1 - 1] == nums1[i1]) ++i1;\n                if (i1 == size(nums1)) break;\n            }\n            nums1[o1++] = nums1[i1++];\n        }\n        nums1.resize(o1);\n        while (i2 < size(nums2)) {\n            if (i2 > 0) {\n                while (i2 < size(nums2) && nums2[i2 - 1] == nums2[i2]) ++i2;\n                if (i2 == size(nums2)) break;\n            }\n            nums2[o2++] = nums2[i2++];\n        }\n        nums2.resize(o2);        \n        return {nums1, nums2};   \n    }\n```\n\n**Complexity Analysis**\nIs basically the same as variant 1.\n\n# Approach 2: std::set and std::set_difference\n\nIf we turn the input vectors into ```std::set```s we can do the `sort | unique` in one go. We are also not modifying the input.\n\n```cpp\n    static vector<vector<int>> findDifference(const vector<int>& nums1, const vector<int>& nums2) {\n        const set<int> s1(begin(nums1), end(nums1));\n        const set<int> s2(begin(nums2), end(nums2));\n        vector<vector<int>> ans(2);\n        ans[0].reserve(size(nums1));\n        ans[1].reserve(size(nums2));\n        set_difference(begin(s1), end(s1), begin(s2), end(s2), back_inserter(ans[0]));\n        set_difference(begin(s2), end(s2), begin(s1), end(s1), back_inserter(ans[1]));\n        return ans;\n    }\n```\n\n**Complexity Analysis**\n\n* Time complexity: $$O(n \\log n)$$ which comes from creating the sets.\n\n* Space complexity: $$O(n)$$ we need the extra memory for the sets\n\n# Approach 3: std::unordered_set and std::copy_if\n\nIt doesn\'t matter in which order we return the numbers in the answer, so we can use an ```std::unordered_set``` as well.\n\n```cpp\n    static vector<vector<int>> findDifference(const vector<int>& nums1, const vector<int>& nums2) {\n        const unordered_set<int> s1(begin(nums1), end(nums1));\n        const unordered_set<int> s2(begin(nums2), end(nums2));\n        vector<vector<int>> ans(2);\n        ans[0].reserve(size(nums1));\n        ans[1].reserve(size(nums2));\n        copy_if(begin(s1), end(s1), back_inserter(ans[0]), [&](int x) { return !s2.count(x); });\n        copy_if(begin(s2), end(s2), back_inserter(ans[1]), [&](int x) { return !s1.count(x); });\n        return ans;\n    }\n```\n\n**Complexity Analysis**\n\n* Time complexity: $$O(size(nums1) + size(nums2))$$\n\n* Space complexity: $$O(size(nums1) + size(nums2)$$\n\n# Approach 4: std::bitset\n\nSince we know that the numbers in ```nums1``` and ```nums2``` are limited to the range ```-1000``` to ```1000``` we can just use a ```bitset<>``` if we apply and offset to make the index non negative. The drawback is that we need to check the entire ```bitset<>```, we could keep tracking of the smallest and the biggest number in the input vectors.\n\n```cpp\n    static vector<vector<int>> findDifference(const vector<int>& nums1, const vector<int>& nums2) {\n        bitset<2048> s1;\n        for (int num : nums1) s1.set(num + 1024);\n        bitset<2048> s2;\n        for (int num : nums2) s2.set(num + 1024);\n        \n        vector<vector<int>> ans(2);\n        ans[0].reserve(size(nums1));\n        ans[1].reserve(size(nums2));\n        for (int i = 0; i < size(s1); ++i) {\n            if (s1[i] && !s2[i]) {\n                ans[0].push_back(i - 1024);\n            } else if (!s1[i] && s2[i]) {\n                ans[1].push_back(i - 1024);\n            }\n        }\n        return ans;\n    }\n```\n\nThe following version keeps track of smallest and biggest number in the input vectors, and seems to a bit faster for the current test sets, but the code is also more complicated:\n\n```cpp\n    static vector<vector<int>> findDifference(const vector<int>& nums1, const vector<int>& nums2) {\n        bitset<2048> s1;\n        int mx = -1024;\n        int mn = 1024;\n        for (int num : nums1) {\n            mn = min(mn, num);\n            mx = max(mx, num);\n            s1.set(num + 1024);\n        }\n        bitset<2048> s2;\n        for (int num : nums2) {\n            mn = min(mn, num);\n            mx = max(mx, num);\n            s2.set(num + 1024);\n        }\n        \n        vector<vector<int>> ans(2);\n        ans[0].reserve(size(nums1));\n        ans[1].reserve(size(nums2));\n        for (int i = mn + 1024; i <= mx + 1024; ++i) {\n            if (s1[i] && !s2[i]) {\n                ans[0].push_back(i - 1024);\n            } else if (!s1[i] && s2[i]) {\n                ans[1].push_back(i - 1024);\n            }\n        }\n        return ans;\n    }\n```\n\n... and yes, I agree we should likely factor out ```1024``` into a constant.\n\n**Complexity Analysis**\n\n* Time complexity: $$O(size(nums1) + size(nums2))$$ we still need to process all the input. For very small inputs the cost will be dominated by scanning the bitset\n\n* Space complexity: $$O(1)$$, even if a big 1, if we consider the value range fixed. :) As @Satj pointed out it would be more accurate to describe it as $$O(M)$$ where $$M$$ is the possible value range of the input, which is for this problem fixed to -1000 to 1000.\n\n_As always: Feedback, questions, and comments are welcome, and leave a like (aka upvote) before you leave. :)_\n
['C', 'Sorting', 'Ordered Set']