Python Sorting + check at most 3 candidates linearly
Super easy to AC with $O(n^3)$, but not easy to optimize to better big-O.\n# Intuition\n Describe your first thoughts on how to solve this problem. \n1. If you 
Super easy to AC with $O(n^3)$, but not easy to optimize to better big-O.\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. If you need to determine the positions of the two deleted/shifted elements, the brute force method is nested loops.\n2. To avoid nested loops, you may choose sorting. The reason is that after sorting, if two arrays have $n - 2$ elements in common, the relative order of these $n - 2$ elements are fixed. ($n = \\text{len}(nums1)$)\n3. When two arrays are sorted, the element-wise comparison will tell you that the difference are kept the same, except when two elements in $nums1$ need to be deleted/shifted.\n4. Based on intuition 3, the major problem is to find the two shift positions. The maximum number of shifts is 2. \n5. When is a shift needed? \nIt can be treated as a two-pointer problem, with $i$ as the pointer in $nums2$ and $i + shift$ as the pointer in $nums1$.\n   ```\n   while nums1[i + shift] + diff < nums2[i] and shift < 2:\n   ```\n\n6. How is the diff determined? After sorting, the $nums2[0]$ if fixed. The effective starting element in $nums1$ is to be determined, but it\'s upper-bounded by how to delete/shift the elements in $nums1$. The effective starting element of $nums1$ can be $nums1[0]$ with zero shift up to index 0 in $nums1$, $nums1[1]$ with $nums1[0]$ is deleted/shifted, or $nums1[2]$ with $nums1[0]$ and $nums1[1]$ are deleted/shifted.\n7. Therefore, totally there are 3 candidates of the effective starting element of $nums1$. And thus there are at most 3 candidates of the diff.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n * log(n))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution:\n    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:\n        nums1.sort()\n        nums2.sort()\n\n        diffs = sorted(set(nums2[0] - nums1[i] for i in range(3)))\n\n        def check(diff):\n            shift = 0\n            for i, num2 in enumerate(nums2):\n                while nums1[i + shift] + diff < num2 and shift < 2:\n                    shift += 1\n                if nums1[i + shift] + diff != num2:\n                    return False\n            return True\n        \n        for diff in diffs:\n            if check(diff):\n                return diff\n```
['Two Pointers', 'Sorting', 'Python3']