Easy to Understand Explanation with C++ Code || Multiset TLE Why?
Question Summary - There is an array arr. You created two different arrays, say Low and High. Low contains all the elements of arr but all the elements are decr
Question Summary - There is an array arr. You created two different arrays, say Low and High. Low contains all the elements of arr but all the elements are decremented by a positive no k. Same as Low, High contains all the elements of arr but they are incremented by k. You are given an array which contains all the elements of Low and High array(with duplicates). You need to construct the original array.\n\nApproach:\n\nAs the size of given array was at max 10^3, we can construct a O(n^2) algo and it will do the job. \nNow first we sort the given array. \n\nIf we can get the value of k by any means then the original array can be reconstructed.\nHow?\nWe take all the element of given array in a multiset. Now the smallest element of multiset will always be in the form of X-k, where X is a element of our original array. \nNow since we have X, we can search X+k in our multiset and if it is present, we can remove these both elements and add X to the ans vector. Futher we continue the same algo until the size of multiset is greater than 0.\n\nNow how can we get k?\nSay the smallest element of the original array be Y. If we have sorted our array then the element at 0 index will be Y-k.\nNow if we can find Y+k in the given array, then by adding these values we can get 2*Y and thus we can also get value of k.\nSince Y+k can be any value of the array, we will iterate entire array and consider every index from 1 to n-1 as Y+k.\n\nNote: Some multiset solutions are giving TLE because some test cases were added recently. It all boils down to reducing number of operations. I reduced operations by passing multiset by reference and hence it is giving Accepted verdict.\n\nC++ Code:\n```\ntypedef long long ll;\ntypedef long double ld;\n#define mod 1000000007\n#define F first\n#define S second\n#define all(x) begin(x),end(x)\n\nclass Solution {\npublic:\n\tvector<int> canMakeIt(multiset<int>& st, int k) {\n\t\tif (k <= 0)\n\t\t\treturn { -1};\n\t\tmultiset<int> erased;\n\t\tvector<int> ans;\n\t\twhile (st.size() > 0) {\n\t\t\tauto it = st.begin();\n\t\t\tint val = *it;\n\t\t\tint org = val + k;\n\t\t\tst.erase(st.find(val));\n            erased.insert(val);\n\t\t\tif (st.find(org + k) != st.end()) {\n\t\t\t\tans.push_back(org);\n\t\t\t\tst.erase(st.find(org + k));\n\t\t\t\terased.insert(org + k);\n\t\t\t}\n\t\t\telse\n\t\t\t{\n\t\t\t\tfor(int x:erased)\n\t\t\t\t\tst.insert(x);\n\t\t\t\treturn { -1};\n\t\t\t}\n\t\t}\n\t\treturn ans;\n\t}\n\n\tvector<int> recoverArray(vector<int>& nums) {\n\t\tsort(all(nums));\n\t\tmultiset<int> st(all(nums));\n\t\tint smallest = nums[0];\n\t\tfor (int j = 1; j < nums.size(); ++j) {\n\t\t\tint addi = smallest + nums[j];\n\t\t\tif (addi % 2 == 0) {\n\t\t\t\tint org = addi / 2;\n\t\t\t\tint k = nums[j] - org;\n\t\t\t\tvector<int> ans = canMakeIt(st, k);\n\t\t\t\tif (ans[0] != -1)\n\t\t\t\t\treturn ans;\n\t\t\t}\n\t\t}\n\t\treturn { -1};\n\t}\n};\n```\nTIme complexity will be O(n^2logn) as I am using multiset.\nIf you have any doubts, you can ask in the comment section.\nIf you found this post helpful consider upvoting so that others can also undestand this question.
['C']