⌛: O(N) only
Intuition\n Describe your first thoughts on how to solve this problem. \n In 3131. Find the Integer Added to Array I, we know that \min (nums1) + x = \min (nums
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n* In [3131. Find the Integer Added to Array I](https://leetcode.com/problems/find-the-integer-added-to-array-i/), we know that $$\\min (nums1) + x = \\min (nums2)$$\n* Therefore, in this problem, the crucial point would be which number is the minimum of `nums1` after removing two numbers\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n## Algorithm\n* Suppose the `nums1` is sorted, there is only three possible candidate for $$\\min (nums1)$$\n  1. nums1[2], when both nums2[1] and nums2[0] are removed\n  2. nums1[1], when nums2[0] is removed\n  3. nums1[0]\n* Combined with $$\\min (nums1) + x = \\min (nums2)$$, there\'s only three possible value for `x`, and they are strictly increasing from 1 to 3\n  1. $$\\min (nums1)$$ - nums1[2]\n  2. $$\\min (nums1)$$ - nums1[1]\n  3. $$\\min (nums1)$$ - nums1[0]\n* As as result, all we need to do is checking whether these numbers could be a valid value for `x` by using the order above\n\n## Implementation\n* Instead of sorting the entire array, we can perform a [partial sort](https://en.wikipedia.org/wiki/Partial_sorting) to get the first three minimal value of `nums1`\n* And because we didn\'t sort the entire array, we have to use an frequency map to help us checking the validity of a possible `x`\n\n# Complexity\n- Time complexity: $$O(N)$$\n  * partial sort to get first three minimal value takes O(N*log(3)) = O(N)\n  * The time complexity of finding the minimum if `nums2`, and checking `x` by iterating the hashmap are O(N)\n\n- Space complexity: $$O(N)$$\n  * the hash map to store frequency takes O(N)\n\n# Code\n```\nclass Solution {\npublic:\n    bool check(const unordered_map<int, int>& freq1,\n               const unordered_map<int, int>& freq2, int x) {\n        for (unordered_map<int, int>::const_iterator it = freq2.begin();\n             it != freq2.end(); ++it) {\n            int key = it->first;\n            int value = it->second;\n\n            unordered_map<int, int>::const_iterator found =\n                freq1.find(key - x); // nums1 + x = nums2\n\n            if (found == freq1.end() || found->second < value) {\n                return false;\n            }\n        }\n\n        return true;\n    }\n\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        partial_sort(nums1.begin(), nums1.begin() + 3, nums1.end());\n        int min2 = INT_MAX;\n        unordered_map<int, int> freq1;\n        unordered_map<int, int> freq2;\n\n        for (int i = 0; i < nums1.size(); i++) {\n            freq1[nums1[i]]++;\n        }\n        for (int i = 0; i < nums2.size(); i++) {\n            min2 = min(min2, nums2[i]);\n            freq2[nums2[i]]++;\n        }\n\n        for (int i = 2; i >= 0; i--) {\n            if (check(freq1, freq2, min2 - nums1[i])) {\n                return min2 - nums1[i];\n            }\n        }\n\n        return 0;\n    }\n};\n```\n\n---\n# If you have any question or advice, welcome to comment below.
['Array', 'Two Pointers', 'Sorting', 'Enumeration', 'C++']