[26ms] || Compression solution || With Explanation|| C++
\nclass Solution {\npublic:\n    /*\n        Hint:\n            PLEASE AS A PREREQUISITE DO SOLVE: https://leetcode.com/problems/find-original-array-from-double
```\nclass Solution {\npublic:\n    /*\n        Hint:\n            PLEASE AS A PREREQUISITE DO SOLVE: https://leetcode.com/problems/find-original-array-from-doubled-array/ \n            1. There are basically 2 types of elements (X + k) or (X - k), and the problem is you don\'t know which is which or do you?\n            2. You can atleast say the smallest element in the array is a (X - k) type and the biggest element is a (X + k) type\n            3. And if you do know that the smallest element is (smallest - k) how can you use that?\n            4. If there is a (smallest - k) in the array that means there must be a (smallest + k) as well.\n            5. (smallest + k) - (smallest - k) = 2 * k\n            6. You can try with all other elements assuming that it is the (smallest + k) element, and guess a [possible_k]\n            7. Then you need to check if enough freq of [arr_val + possilbe_k] and [arr_val - possible_k] exists or not.\n            8. If you have already solved the prerequisite problem then the last part would be a piece of cake.\n        \n        Complexity:\n            Time: O(N * logN + N * N)\n            Space: O(N)\n    */\n    \n    \n    #define inf             0x3f3f3f3f\n    #define all(a)          a.begin(),a.end()\n    #define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())\n    int org_frq[2001], frq[2001];\n    unordered_map <int, int> val_to_id;\n    vector<int> recoverArray(vector<int>& nums) {\n        vector <int> compressed; compressed.push_back(-inf);\n        for (int &val: nums) compressed.push_back(val); Unique(compressed);\n        \n        for (int i = 0; i < nums.size(); i++) {\n            int index = lower_bound(compressed.begin(), compressed.end(), nums[i]) - compressed.begin();\n            val_to_id[ nums[i] ] = index;\n            nums[i] = index;\n            org_frq[ index ]++;\n        }\n        \n        vector <int> result;\n        for (int arr_plus_k_id = 2; arr_plus_k_id < compressed.size(); arr_plus_k_id++) {\n            int possible_k = (compressed[arr_plus_k_id] - compressed[1]);\n            if (possible_k & 1) continue;\n            possible_k /= 2;\n            \n            memcpy(frq, org_frq, sizeof org_frq);\n            \n            for (int plus_k_id = compressed.size() - 1; plus_k_id > 0; plus_k_id--) {\n                if (frq[ plus_k_id ] == 0) continue;\n                int minus_k_id = val_to_id[ compressed[plus_k_id] - 2 * possible_k ];\n                if (minus_k_id == 0 || frq[ minus_k_id ] < frq[ plus_k_id ]) {\n                    result.clear();\n                    break;\n                } \n                \n                frq[minus_k_id] -= frq[ plus_k_id ];\n                for (int time = 0; time < frq[ plus_k_id ]; time++) result.push_back(compressed[plus_k_id] - possible_k);\n                if (result.size() * 2 == nums.size()) break;\n            }\n            \n            if (result.size()) break;\n        }\n        \n        return result;\n    }\n};\n```
[]