Greedy + Sorting + Hashmap 💯💯💯💯 Easy To understand!!!! With Comments
Approach\nFirst sort the nums, this way we can tell that nums[0] is lower[i] for some ith index in the original array.\nNow we know that higher[i] - lower[i] = 
# Approach\nFirst sort the nums, this way we can tell that nums[0] is lower[i] for some ith index in the original array.\nNow we know that **higher[i] - lower[i] = 2*k.**\nTry for all possible value of 2*k fixing lower[i]==nums[0], now for each value of 2*k check wether this value is valid or not. This can be checked if using 2*k can we consume the whole nums array or not. If we can then we have found our k, now construct the original array.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {\n        int n = nums.size();\n        \n        //Storing the frequencies of each element\n        unordered_map<int,int> freq;\n        for(auto x : nums){\n            freq[x]++;\n        }\n        \n/*After we have sorted the nums, we are sure that nums[0] is lower[i], now we will fix its valid upper[i] \none by one and then check whether the diff btw them i.e. 2*k is possible for other left numbers or not*/\n        sort(nums.begin(),nums.end());\n\n        int k{}; //Storing final value of K\n        for(int i{1}; i<n; i++){\n            int potentialK = (nums[i]-nums[0]);\n\n            if(potentialK%2!=0 || potentialK==0) continue; \n            potentialK/=2;\n            \n            unordered_map<int,int> temp = freq;\n\n            //Check wether potentialK*2 is possible or not\n            bool flag = true;\n            for(int i{}; i<n; i++){\n                //As difference between higher[i]-lower[i]==2*k, higher[i]=lower[i]+2*k\n                int loweri = nums[i];\n                int higheri = nums[i]+(2*potentialK);\n\n                //loweri left or already used\n                if(temp[loweri]!=0){\n                    if(temp[higheri]!=0){\n                        temp[loweri]--;\n                        temp[higheri]--;\n                    }\n                    else{\n                        flag = false;\n                        break;\n                    }\n                }\n            }\n            //Found Valid K\n            if(flag){\n                k = potentialK;\n                break;\n            }\n        }\n\n        //Constructing the original array using K we found\n        vector<int> ans;\n        for(int i{}; i<n; i++){\n            int loweri  = nums[i];\n            int higheri = nums[i]+(2*k);\n            if(freq[loweri]!=0){\n                int ele = nums[i]+k;\n                ans.push_back(ele);\n                freq[loweri]--;\n                freq[higheri]--;\n            }\n        }\n        return ans;\n    }\n};\n\n\n\n```
['C++']