[Python] Sorting and Recursion (O(n log n) beats 100%)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nSort and recursion. Imagine if we have 2 arrays of same size and 2 numbers of nums1 a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nSort and recursion. Imagine if we have 2 arrays of same size and 2 numbers of `nums1` are removed, after having sorted the arrays, `nums2[0] - nums1[0] == nums2[1] - nums1[1] == ...` and so on. Now is the issue of finding "which" numbers to remove from `nums1`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet\'s say `nums1 = [3, 12, 13, 16, 20]`, `nums2 = [10, 14, 18]`. If we take in `nums1[0]`, `x = nums2[0] - nums1[0] = 7` \n\nIterate over the 2 arrays. If we find a discrepancy (i.e. `nums2[i] - nums1[i] != x`), we branch out with 2 options: \n\n(1) Remove `nums1[0]`, iterate from the start again and recalculate `x`. \n\nSo the new arrays are `nums1 = [12, 13, 16, 20]`, `nums2 = [10, 14, 18]`, and `x` is recalculated as `x = nums2[0] - nums1[0] = 2` \n\n(2) Remove the discrepancy point (at the moment it\'s `i=1`), and keep the previous `x`.\n\nSo the new arrays are `nums1 = [3, 12, 16, 20]`, `nums2 = [10, 14, 18]`, and `x = 7`.\n\nIf the 2 arrays have the same difference `x` on each item pair, we return this `x`. But this `x` may not be the smallest so we need to look at 3 cases in total, `nums1`, `nums1[1:]`, and `nums1[2:]`, and take the minimum between them\n\n# Complexity\n- Time complexity: O(n log n) due to the initial sorting. The recursion portion takes at most O(n).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:\n        sort1 = sorted(nums1)\n        sort2 = sorted(nums2)\n        \n        def helper(nums1, nums2, x, use_x: bool):\n            # base case\n            if len(nums1) - len(nums2) < 0:\n                return float("inf")\n            \n            diff = 0\n            res = float("inf")\n            \n            if not use_x:\n                x = nums2[0] - nums1[0]\n            \n            for i in range(len(nums2)):\n                if nums2[i] - nums1[i] != x:\n                    return min(\n                        # either remove the nums1[0] number, find new x\n                        helper(nums1[1:], nums2, 0, False),\n                        # or keep x and skip this number, replace -= 1\n                        helper(nums1[:i] + nums1[i+1:], nums2, x, True)\n                    )\n            return min(x, helper(nums1[1:], nums2, 0, False), helper(nums1[2:], nums2, 0, False))\n        \n        return helper(sort1, sort2, 0, False)\n```
['Recursion', 'Sorting', 'Python3']