[Python3] Sorting O(NlogN) | Bonus O(N) | Clean & Concise
Intuition\nNote: The constraint of the problem can be as large as 10^5.\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nStep 1: Sor
# Intuition\nNote: The constraint of the problem can be as large as $$10^5$$.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**Step 1:** Sort both arrays.\n**Step 2:** Set `nums2` as pivot, then the only possible values of `-x`, where we refer to as `diff`, are `[nums1[0] - nums2[0], nums1[1] - nums2[0], nums1[2] - nums2[0]]`.\n**Step 3:** For each possible `diff`, for each value `num2` of `nums2`, add `diff` to it, and check whether there is a corresponding value in `nums1`. Since `nums1` is already sorted, we can optimize this step by using two-pointer or binary search to achieve this.\n**Step 4:** If all `num2 + diff` are found in `nums1`, then `diff` is valid, and we compare it as the current value of `ans`.\n<!-- Describe your approach to solving the problem. -->\n\n# Explanations\n1. `nums1` must have either one of `nums1[0]`, `nums1[1]` or `nums1[2]` remaining after 2 elements are removed. Find the `diff` with the first element of nums2, giving possible diffs.\n2. Use this `diff` on each element of `nums2` and perform a two-pointer or binary search to find the corresponding number in `nums1` that would generate this number.\n3. If a number doesn\'t exist in `nums1`, this particular `diff` is not valid. Check the next `diff`.\n4. If we manage to find all nums in `nums1`, this is one possible `diff`.\n5. Store it as a possible `ans`.\n6. If we manage to do so again, find the smallest possible `ans`.\n\nCredit to [@qwerty7325](https://leetcode.com/qwerty7325).\n\n# Complexity\n- Time complexity: $$O(N\\log N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(sort)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nPlease upvote if you find this solution helpful.\n# Code (Sorting + Two-Pointer)\n```\nclass Solution:\n    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:\n        m = len(nums1)\n        ans = float(\'-inf\')\n        nums1.sort()\n        nums2.sort()\n\n        def check(diff):\n            idx = 0\n            for num2 in nums2:\n                num1 = num2 + diff\n                while idx < m and nums1[idx] != num1:\n                    idx += 1\n                if idx >= m:\n                    return False\n                idx += 1\n            return True\n\n        for diff in [nums1[0] - nums2[0], nums1[1] - nums2[0], nums1[2] - nums2[0]]:\n            if check(diff):\n                ans = max(ans, diff)\n        return -ans\n```\n\n# Code (Sorting + Binary Search)\n```\nclass Solution:\n    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:\n        m = len(nums1)\n        ans = float(\'-inf\')\n        nums1.sort()\n        nums2.sort()\n        for diff in [nums1[0] - nums2[0], nums1[1] - nums2[0], nums1[2] - nums2[0]]:\n            flag = True\n            lo = 0\n            for num2 in nums2:\n                num1 = num2 + diff\n                idx = bisect.bisect_left(nums1, num1, lo = lo)\n                if idx >= m or nums1[idx] != num1:\n                    flag = False\n                    break\n                lo = idx + 1\n            if flag:\n                ans = max(ans, diff)\n        return -ans\n```\n\n# Bonus (O(N) Solution) - Credit to: [@iyerke](https://leetcode.com/iyerke)\nSuppose this is an interview question, one may be asked if there is a solution with even better time complexity than $$O(N\\log N)$$, e.g. $$O(N)$$. The answer is **yes**, and here is the approach.\n\nTo achieve a solution with $$O(N)$$ time complexity, we need to avoid sorting either of the array `nums1` or `nums2` in the first place. However, same as the approach above, we still need to obtain the 3 possible candidates of `x`. So we will get the minimum value of `nums2` in linear time, and get the 3 smallest values of `nums1` in linear time. This could be done either by a one-pass approach or using the `nsmallest()` method from Python 3\'s `heapq` library with a time complexity of $$O(N\\log 3) = O(N)$$.\n\nNow we need to check either candidate of `x` is valid. Previously, we used a two-pointer or binary search over the already sorted `nums1` and `nums2` to achieve this. Now that neither `nums1` nor `nums2` is sorted, what we can do here is to compare the two frequency maps (i.e. `Counter` as dictionary objects in Python 3) and see if the frequency map based on `nums2` is **nested** in the frequency map based on `nums1` after applying the operations. This can be implemented by going through each (unique) element in `nums2` and check its count between two frequency maps. In Python 3, we can implemented with a one-liner:\n```\ndic1 = Counter([2, 1, 3])\ndic2 = Counter([1, 1, 2, 3, 4])\ndic3 = Counter([2, 3, 3])\nprint(dic1 <= dic2) # True\nprint(dic1 <= dic3) # False\n```\n\n# Complexity\n- Time complexity: $$O(N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code (No Sorting)\n```\nclass Solution:\n    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:\n        min2 = min(nums2)\n        c, b, a = [min2 - val for val in heapq.nsmallest(3, nums1)]\n        nums2 = Counter(nums2)\n        for x in (a, b, c):\n            if nums2 <= Counter(val + x for val in nums1):\n                return x\n```\n
['Sorting', 'Python3']