O(n^2)
If we have the lowest value of the lower array and the lowest value of the higher array we can recunstruct it in linear time. We just keep adding the next lowes
If we have the lowest value of the lower array and the lowest value of the higher array we can recunstruct it in linear time. We just keep adding the next lowest from the set + k to the result and remove the lowest and the lowest + 2 * k from the set.\nWe already know the lowest value of the lower array, because it must be the lowest value in nums. So we sort the array and use the first element as the lowest of the lower array, and then we try all possible values in nums as the lowest of the higher array and try to recunstruct it.\n\nI used recursion to recunstruct the array. It should also be possile to do it iteratively, but I found it easier doing it backtracking. The recursive function runs in linear time.\n\n```\nclass Solution {\npublic:\n    bool recunstruct(int i, int diff, vector<int>& nums, unordered_map<int, int>& freq, vector<int>& res) {\n        if (i == nums.size()) return true;\n        if (!freq[nums[i]]) return recunstruct(i + 1, diff, nums, freq, res);\n        if (!freq[nums[i] + diff]) return false;\n\t\t\n\t// remove it from map so we don\'t use it again\n        freq[nums[i]]--;\n        freq[nums[i] + diff]--;\n        res.push_back(nums[i] + diff / 2);\n        if (recunstruct(i + 1, diff, nums, freq, res)) return true;\n        res.pop_back();\n\t\t\n\t// add it back to map\n        freq[nums[i] + diff]++;\n        freq[nums[i]]++;\n        return false;\n    }\n    vector<int> recoverArray(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n\t\t\n\t// map to store the values that are not used yet\n        unordered_map<int, int>freq;\n        for (int n : nums) freq[n]++;\n        vector<int>res;\n        for (int i = 1; i < nums.size(); i++) {\n\t\t\n\t\t// if we\'ve already tried this value we can skip it\n            if (nums[i] == nums[i - 1]) continue;\n            int diff = nums[i] - nums[0];\n\t\t\t\n\t\t// if diff is odd or equals zero we can skip it\n            if (diff & 1 || diff == 0) continue;\n            if (recunstruct(0, diff, nums, freq, res)) return res;\n        }\n        return {};\n    }\n};\n```
[]