C++ || 5 different approaches || clean code
Please let me know if can think of another approach.\n\n# Approach 1: nested loops (30ms)\n\nThis constraint for the problem are small enough, that we can just 
Please let me know if can think of another approach.\n\n# Approach 1: nested loops (30ms)\n\nThis constraint for the problem are small enough, that we can just use ntested loops.\n\n```cpp\n    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {\n        int c1 = 0, c2 = 0;\n        for (int x : nums1)\n            for (int y : nums2)\n                if (x == y) {\n                    ++c1;\n                    break;\n                }\n        for (int y : nums2)\n            for (int x : nums1)\n                if (x == y) {\n                    ++c2;\n                    break;\n                }\n        return {c1, c2};\n    }\n```\n\n**Complexity Analysis**\nLet $$n_1$$ be the length of ```nums1``` and $$n_2$$ the lenght of ```nums2```, then the\n\n* Time complexity is $$O(n_1 n_2)$$, and the\n\n* Space comlexity is $$O(1)$$.\n\n# Approach 2 : nested loops, but using STL fancyness\n\nThis is the same idea as in approach 1, but using STL functions.\n\n```cpp\n    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {\n        const int c1 = count_if(begin(nums1), end(nums1), [&](int x) {\n            return find(begin(nums2), end(nums2), x) != end(nums2);\n        });\n        const int c2 = count_if(begin(nums2), end(nums2), [&](int x) {\n            return find(begin(nums1), end(nums1), x) != end(nums1);\n        });\n        return {c1, c2};\n    }\n```\n\n## Variant: "one-liner"\n\nIf we feel fancy, we could turn this into a one-liner. We need to add some casts though s.t. we can construct the ```vector<int>``` directly.\n\n```cpp\n    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {\n        return {\n            static_cast<int>(count_if(begin(nums1), end(nums1), [&](int x) {\n                return find(begin(nums2), end(nums2), x) != end(nums2);\n            })),\n            static_cast<int>(count_if(begin(nums2), end(nums2), [&](int x) {\n                return find(begin(nums1), end(nums1), x) != end(nums1);\n            }))};\n    }\n```\n\n**Complexity Analysis**\nSame as approach 1.\n\n# Approach 3: sort and binary search (18ms)\n\nIf we sort the input we can use binary search.\n\n```cpp\n    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {\n        sort(begin(nums1), end(nums1));\n        sort(begin(nums2), end(nums2));\n        const int c1 = count_if(begin(nums1), end(nums1), [&](int x) {\n\t\t\t\treturn binary_search(begin(nums2), end(nums2), x);\n\t\t});\n        const int c2 = count_if(begin(nums2), end(nums2), [&](int x) {\n\t\t\t\treturn binary_search(begin(nums1), end(nums1), x);\n\t\t});\n        return {c1, c2};\n    }\n```\n\n**Complexity Analysis**\nLet $$n_1$$ be the length of ```nums1``` and $$n_2$$ the lenght of ```nums2```, then the\n\n* Time complexity is $$O(n_1 \\log(n_1) + n_2 \\log(n_2) + n_1 \\log(n_2) + n_2 \\log(n_1)) = O((n_1 + n_2) (\\log(n_1) + \\log(n_2))$$, as we need to sort each input vector and then scan through each of them while doing binary search on the other one, and the\n\n* Space comlexity is $$O(1)$$.\n\n# Approach 4: hash sets (36ms)\nFor faster lookup we can turn the input vectors into hash sets.\n\n```cpp\n    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {\n        const unordered_set<int> s1(begin(nums1), end(nums1));\n        const unordered_set<int> s2(begin(nums2), end(nums2));\n        const int c1 = count_if(begin(nums1), end(nums1), [&](int x) {\n            return s2.count(x);\n        });\n        const int c2 = count_if(begin(nums2), end(nums2), [&](int x) {\n            return s1.count(x);\n        });\n        return {c1, c2};\n    }\n```\n\n**Complexity Analysis**\nLet $$n_1$$ be the length of ```nums1``` and $$n_2$$ the lenght of ```nums2```, then the\n\n* Time complexity is $$O(n_1 + n_2)$$, and the\n\n* Space comlexity is $$O(n_1 + n_2)$$.\n\nWhile the last approach offers the past asymptotic time complexity it seems for the given input other approaches perform better. We would need to do some micro benchmarks to confirm this.\n\n# Approach 5 : bitset (23ms)\nGiven the input constraints we can use a ```bitset``` instead of a hashset.\n\n```cpp\n   vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {\n        bitset<128> s1, s2;\n        for (int n : nums1) s1[n] = true;\n        for (int n : nums2) s2[n] = true;\n        const int c1 = count_if(begin(nums1), end(nums1), [&](int x) { return s2[x]; });\n        const int c2 = count_if(begin(nums2), end(nums2), [&](int x) { return s1[x]; });\n        return {c1, c2};\n    }\n```\n\n**Complexity Analysis**\nLet $$n_1$$ be the length of ```nums1``` and $$n_2$$ the lenght of ```nums2```, then the\n\n* Time complexity is $$O(n_1 + n_2)$$, and the\n\n* Space comlexity is $$O(1)$$ as the bitsets of a fixed size.\n\nTBH I would have expected this approach to perform the best. For more comparable results we should do some micro benchmarks.\n\n_As always: Feedback, questions, and comments are welcome. Leaving an up-vote sparks joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['C', 'Sorting', 'Binary Tree']