C++ Hash Table Sorting
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first thought we may have by looking a this question may have binary search. But as
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first thought we may have by looking a this question may have binary search. But as we see, we have no criteria to decide when to move left or right in binary search. But by looking at the question, we can see the relation between the elements. Each element is either some element + 2k or - 2k. All we have to do is to find a k that fits. But how can we check if a k fits? Also, how to find possible values of k?\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe answer to the first question is, we can check if k satisfies if we take all unique elements of the nums in a sorted order in a array called **vec**. Also we need to store the number of times the unique value has been repeated. To store this we can use an unordered_map called **mp**. Now, when we iterate over the sorted unique values, we check if for any **unique value vec[i]**, does there exist an vec[i] + 2k, as we have already seen the relation. If not, then the k is wrong. Else, we can subtract 1 from the mp[vec[i] + 2k] for each occurence of vec[i]. If we successfully iterate the whole array, then the k is correct. The reason to sort is, we now do not need to care about vec[i] -2k as they have already been visited and they have compensated from vec[i].\n\nComing to the second question, how to find possible values of k? For vec[0], there must exist some vec[i] such that vec[i] - vec[0] = 2k, where k is valid, as we there is a guarantee that a valid k exists. So we start iterating from i = 1 to i = vec.size() - 1. For each i, we take a possible value of k = (vec[i] - vec[0])/2. We test for this k. If successful, we are done and found a k. Else we try for next value.\n\n**Now, how to find the original array from this k?** We so something similar to the first question, the one where we define the test of k. But here instead of checking if k is correct, we know the k is correct. We take another array to store result called res. In the verification, we subtract 1 from mp[vec[i + 2k]] for each mp[vec[i]], we do the same here, **but we also push vec[i] + k in res for each mp[vec[i]]**. This way the res array contains the final solution.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe sorting of vec array takes $$O(nlogn)$$ time. Finding possible values of k and testing them takes $$O(n^2)$$ time. All unordered map operations are of $$O(1)$$. Obtaining final array takes $$O(n)$$ time. Hence the time complexity is $$O(n^2)$$. \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe additional space required is order of $$O(n)$$.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {        \n        unordered_map<int, int> m;        \n        for (auto x: nums) m[x]++;\n        int ans = -1;\n        vector<int> vec;\n        for (auto it = m.begin(); it != m.end(); it++) vec.push_back(it->first);\n        sort(vec.begin(), vec.end());\n        int n = vec.size();\n        for (int i = 1; i < (n); i++){\n            int val = vec[i] - vec[0];\n            if (val&1) continue;\n            unordered_map<int, int> mp;\n            mp.insert(m.begin(), m.end());\n            bool fail = false;\n            for (auto x: vec){\n                if (mp[x] == 0) continue;\n                auto it = mp.find(x + val);\n                if (it == mp.end() || mp[x] > it->second){\n                    fail = true;\n                    break;\n                } \n                it->second -= mp[x];\n                mp[x] = 0;\n            }\n            if (!fail){\n                ans = val;\n                break;\n            }            \n        }\n        vector<int> res;\n        //cout << ans;\n        int val = ans/2;\n        for (auto x: vec){\n            if (m[x] == 0) continue;\n            //cout << ans << " "; \n            int clc = x + val;\n            auto it = m.find(x + ans);\n            it->second -= m[x];\n            int z = m[x];\n            m[x] = 0;\n            while (z--){\n                res.push_back(clc);\n            }\n        }\n        return res;\n    }\n};\n```
['Hash Table', 'Sorting', 'C++']