O(N) solution: No Sorting No Sliding Window No DP - Explained in details
Intuition\n- How many possible values are there for x? \n- Imagine if we have both arrays sorted, each element from nums2 needs to match an element from nums1, 
# Intuition\n- How many possible values are there for x? \n- Imagine if we have both arrays sorted, each element from `nums2` needs to match an element from `nums1`, then the first possible element from `nums1` can **ONLY** from the first 3 elements, because the `num2` has 2 less elements than `nums1`;\n- So we have at most 3 possible values of `x`, let\'s call this array `candidates`\n- For each `candidates[i]`, we scan through `nums1` to search for `nums2[j] - candidates[i]`, if there\'s any missing, this `candidates` value is invalid.\n- Eventually, we just return the smallest valid candidate.\n\n# Complexity\n- **Time complexity**: $$O(n)$$.\n- **Space complexity**: $$O(n)$$\n\n# Code\n```\nclass Solution {\n    public int minimumAddedInteger(int[] nums1, int[] nums2) {\n        int n = nums1.length;\n\n        // find top 3 smallest elements in nums1:\n        int min1_1 = Integer.MAX_VALUE, min1_2 = Integer.MAX_VALUE, min1_3 = Integer.MAX_VALUE;\n        for (int val : nums1) {\n            if (val < min1_1) {\n                min1_3 = min1_2;\n                min1_2 = min1_1;\n                min1_1 = val;\n            } else if (val < min1_2) {\n                min1_3 = min1_2;\n                min1_2 = val;\n            } else if (val < min1_3) {\n                min1_3 = val;\n            }\n        }\n        \n        // find the smallest element in nums2\n        int min2 = Integer.MAX_VALUE;\n        for (int val : nums2) {\n            min2 = Math.min(min2, val);\n        }\n        // the 3 only possible x values:\n        int[] candidates = new int[] {min2 - min1_1, min2 - min1_2, min2 - min1_3};\n        \n        // count the occurrences of each number in nums1: \n        int[] numberOccurs = new int[1001];\n        for (int i = 0; i < n; i++) {\n            int n1 = nums1[i];\n            numberOccurs[n1]++;\n        }\n\n        int minX = Integer.MAX_VALUE;\n        for (int possibleX : candidates) {\n            int[] numberCounts = new int[1001];\n            boolean isPossible = true;\n            // iterate nums2 to check whether the value of \'nums2[i] - possibleX\' exists for every element\n            for (int i = 0; i < n - 2 && isPossible; i++) {\n                int target = nums2[i] - possibleX;\n                if (target < 0 || target > 1000 || numberOccurs[target] == 0 || numberCounts[target] == numberOccurs[target]) {\n                    isPossible = false;\n                } else {\n                    numberCounts[target]++;\n                }\n            }\n            if (isPossible) {\n                minX = Math.min(minX, possibleX);\n            }\n        }\n        return minX;\n    }\n}\n```
['Hash Table', 'Java']