C++ easy to understand - beats 98% - not bruteforce - test 3 smallest in array only
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#include <algorithm>\n#include <unordered_map>\nclass Solution {\npublic:\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        \n        std::unordered_map<int, int> frequencies;\n\n        // Find smallest element in shorter list\n        auto min_2 = *std::min_element(nums2.begin(), nums2.end());\n        \n        // Find 3 smallest in longer list\n        std::array<int, 3> mins {};\n        std::partial_sort_copy(nums1.begin(), nums1.end(), mins.begin(), mins.end());\n        \n        // We know that one of these 3 minimum elements is guaranteed to map to the minimum element in the shorter list\n        // It\'s 3 minimum since there is a chance that the two real minimum were both removed\n        // So we know x must be the difference between one of the 3 values and the minimum in the smallest list\n\n        // Store the frequencies of each number in a dictionary\n        for (const auto num: nums1)\n        {\n            frequencies[num] += 1;\n        }\n        \n\n        std::vector<int> working_xs;\n        // Now for each x, test if the frequencies match and if so append to our list of working x\n        for (const auto min: mins)\n        {\n            int x = min_2 - min;\n            bool works {true};\n            std::unordered_map<int, int> temp_frequencies;\n            for (const auto num: nums2)\n            {\n                temp_frequencies[num-x] += 1;\n                // Just need to see if any test frequencies go over the real ones\n                if (frequencies.count(num-x) == 0 || temp_frequencies[num-x] > frequencies[num-x])\n                {\n                    works = false; // test failed so break early\n                    break;\n                }\n            }\n            // all frequencies match (besides 2 removed) so the solution is valid\n            if (works) working_xs.push_back(x);\n        }\n        // return minimum of valid xs\n        return *std::min_element(working_xs.begin(), working_xs.end());\n    }\n};\n```
['C++']