Java | Sort and try all Ks | brute force with two pointers (6ms)
Sort the mixed up array and use two pointers within it (i1, i2) to point to elements of the smaller and larger arrays.\nTry all possible Ks: the first element o
Sort the mixed up array and use two pointers within it (i1, i2) to point to elements of the smaller and larger arrays.\nTry all possible Ks: the first element of the larger array after sorting can be at index in range [1...n]. K is then equal to (nums[i2]-nums[i1])/2  (must be positive).\n```\n // i - index of resulting array (ans)\n // i1/i2next - indexes of smaller array (as subsequence of nums)\n // i2/i2next - indexes of larger array (as subsequence of nums)\n\nclass Solution {\n    public int[] recoverArray(int[] nums) {\n        Arrays.sort(nums);\n        int ans[]= null, n= nums.length/2;\n        for(int i2=1; i2<=n; i2++)\n            if((ans= attempt(nums, i2))!=null) break;\n        return ans;\n    }\n\n    int[] attempt(int[] nums, int i2){\n        int twoN= nums.length, n= twoN/2, i=0, i1= 0;\n        boolean[] used= new boolean[twoN];\n        used[i1]= used[i2]= true;\n\n        int twoK= nums[i2]-nums[i1], k= twoK/2;\n        if(twoK==0 || twoK%2==1) return null;\n        \n        int[] ans= new int[n];\n        ans[i++]= nums[i1]+k;\n        while(i<n){\n            int i1next= i1+1;\n            while(i1next<twoN && used[i1next]) i1next++;\n            if(i1next==twoN) return null;\n            used[i1next]= true;\n            \n            int diff= nums[i1next]-nums[i1], num2next= nums[i2]+diff;\n            int i2next= i2+1;\n            while(i2next<twoN && nums[i2next]<num2next) i2next++;\n            if(i2next==twoN || nums[i2next]!=num2next) return null;\n            used[i2next]= true;\n            \n            ans[i++]= nums[i1next]+k;\n            i1= i1next;\n            i2= i2next;\n        }\n        return ans;\n    }\n}
[]