Java solution using 2 pointer along with every possible value of k (11ms)
\nclass Solution {\n    \n    int[] res;\n    public int[] recoverArray(int[] nums) {\n        int n = nums.length;\n        Arrays.sort(nums);\n        ArrayLi
```\nclass Solution {\n    \n    int[] res;\n    public int[] recoverArray(int[] nums) {\n        int n = nums.length;\n        Arrays.sort(nums);\n        ArrayList<Integer> diffs = new ArrayList<>();\n        int smallest = nums[0];\n        for(int i = 1; i < n; i++){\n            int k =(nums[i] - smallest) / 2;\n            if((nums[i] - smallest) % 2 == 0 && k !=0){\n                diffs.add(k);\n            }\n        }\n        for(int k : diffs){\n            if(check(n,k,nums)) break;\n        }\n        return res;\n    }\n    \n    public boolean check(int n, int k, int[] nums){\n        res = new int[n/2];\n        boolean[] visited = new boolean[n];\n        int lower = 0;\n        int higher = 1;\n        int count = 0;\n        while(lower < n){\n            \n            if(visited[lower]){\n                lower++;\n                continue;\n            }\n            int lowerVal = nums[lower];\n            int higherVal = lowerVal + (2 * k);\n            while(higher < n){\n                if(nums[higher] == higherVal && !visited[higher]) break;\n                higher++;\n            }\n            if(higher == n) return false;\n            visited[lower] = true;\n            visited[higher] = true;\n            res[count] = lowerVal + k;\n            count++;\n            if(count == n/2) return true;\n            lower++;\n            higher++;\n        }\n        return false;\n    } \n    \n}\n```
['Two Pointers', 'Java']