[Java] Explained: check valid K with two pointers, 6ms beats 100%
Let\'s assume that the original array was [x, y, z] (x <= y <= z), and after subtracting and adding k we\'ve got an array of pairs [x-k, x+k, y-k, y+k, z-k, z+k
Let\'s assume that the original array was `[x, y, z] (x <= y <= z)`, and after subtracting and adding `k` we\'ve got an array of pairs `[x-k, x+k, y-k, y+k, z-k, z+k]`. We can make the following observations:\n1. The smallest number `x` in the original array will produce the smallest number `x - k` in the generated array.\n2. All generated pairs will have the same fixed difference: `(x+k) - (x-k) = x + k - x + k = 2 * k`. \n3. This difference `2 * k` must be even and positive (because `k` is positive).\n4. Sequential numbers in the original array `x < y` generate 2 pairs in one of the following sorted orders: `[x-k, x+k, y-k, y+k]` or `[x-k, y-k, x+k, y+k]`, because `x-k < y-k` and `x+k < y+k`\n5. Thus, we can sort the array and use a sliding window of fixed difference = `2 * k` with `i` = index of the lower element and `j` = index of the higher element of the pair, both of them are strictly increasing.\n5. Introduce `visited` array to ensure that each number is processed only once.\n ```java\nclass Solution {\n    public int[] recoverArray(int[] nums) {\n        Arrays.sort(nums);\n        int[] res = new int[nums.length / 2];\n        int prev = 0; // used to process each diff of 2*k only once\n        // try finding a pair element x+2*k for the smallest one x\n        for (int i = 1; i < nums.length; i++) {\n            int diff = nums[i] - nums[0]; // 2*k, must be positive and even\n            if (diff != prev && diff > 0 && diff % 2 == 0 && check(nums, i, diff / 2, res)) break;\n            prev = diff;\n        }\n        return res;\n    }\n    \n\t // j points to the higher element of the pair\n    private boolean check(int[] nums, int j, int k, int[] res) {\n        int idx = 0;\n        boolean[] visited = new boolean[nums.length];\n        // i points to the lower element of the pair\n        for (int i = 0; i < nums.length; i++) {\n            if (visited[i]) continue;\n            visited[i] = true;\n            int target = nums[i] + 2 * k;\n            // find the target = the higher element of the pair\n            while (j < nums.length && (nums[j] < target || (nums[j] == target && visited[j]))) j++;\n            if (j == nums.length || nums[j] != target) return false;\n            visited[j] = true;\n            // both elements of the pair are confirmed, update the result\n            res[idx++] = nums[i] + k;\n        }\n        return true;\n    }\n}\n```\nSimilar problems:\n[954. Array of Doubled Pairs](https://leetcode.com/problems/array-of-doubled-pairs/)\n[2007. Find Original Array From Doubled Array](https://leetcode.com/problems/find-original-array-from-doubled-array/)\n\n**PLEASE UPVOTE if you liked this post. THANKS!**
['Java']