Stable O(NlogN) solution
To make this problem even harder, limit can be in range of [2, 10e9].\nThen O(n + k) solution becomes unstable.\nHere is a stable O(NlogN) solution despite of a
To make this problem even harder, limit can be in range of [2, 10e9].\nThen O(n + k) solution becomes unstable.\nHere is a stable O(NlogN) solution despite of any limit number. The main idea is sorting and counting.\nSimilar with those O(n + k) solutions, if we decide that the final sum is w, then those pairs (a <=b) satisfying a >= w take two moves, and those pairs w - b > limit also take two moves, others take one move except those with exactly sum of w.\n\nWhen we sort a and b, we can find how many pairs take two moves by two pointer counter. All procedures are not related with limit.\n\nPointer counter version:\n```\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int limit) {\n        vector<int> p1, p2; // p1: min value array, p2: max value array\n        int n = nums.size();\n        map<int, int> d; // map to record appearance count of sum values\n        for (int i=0;i<(n>>1);i++) {\n            int mini = min(nums[i], nums[n - 1 - i]);\n            int maxi = max(nums[i], nums[n - 1 - i]);\n            p1.push_back(mini);\n            p2.push_back(maxi);\n            d[maxi + mini] += 1;\n        }\n        sort(p1.begin(), p1.end());\n        sort(p2.begin(), p2.end());\n\t\t// sorted max and min values are needed\n        int ans = n;\n        int l1 = -1;\n        int l2 = -1;\n        d[limit + 1] += 0;\n        for (auto it: d) {\n            int i = it.first;\n\t\t\t// answers must appear at all sum values\' positions or limit + 1, so iterate all sum value, ans limit + 1 as well\n\t\t\t//then count how many pairs take two moves: as i becomes larger, the numbers increase/decrease\n\t\t    while (l1+1 < (n>>1) && p1[l1+1] < i) l1++;\n            while (l2+1 < (n>>1) && i - p2[l2+1] > limit) l2++;\n            ans = min(ans, n - (l1 - l2) - it.second);\n        }\n        return ans;\n    }\n};\n```\n\n\nOriginal bi-search version:\n```cpp\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int limit) {\n        vector<int> p1, p2, pp; // p1: min value array, p2: max value array, pp: sum value array\n        int n = nums.size();\n        map<int, int> d; // map to record appearance count of sum values\n        for (int i=0;i<(n>>1);i++) {\n            int mini = min(nums[i], nums[n - 1 - i]);\n            int maxi = max(nums[i], nums[n - 1 - i]);\n            p1.push_back(mini);\n            p2.push_back(maxi);\n            d[maxi + mini] += 1;\n            pp.push_back(maxi+mini);\n        }\n        sort(p1.begin(), p1.end());\n        sort(p2.begin(), p2.end());\n\t\t// sorted max and min values are needed\n        int ans = n;\n        for (int i: pp) {\n\t\t\t// answers must appear at all sum values\' positions, so iterate all sum value\n\t\t    // not proven yet, but seems to be correct\n\t\t\t// first bi-search: calculate how many pairs taking two moves due to exceed upperbound \n            int l, r;\n            l = -1;\n            r = n >> 1;\n            while (l + 1 < r) {\n                int m = (l + r) >> 1;\n                if (p1[m] >= i) r = m;\n                else l = m;\n            }\n            int k = (n >> 1) - r;\n\t\t\t// second bi-search: calculate how many pairs taking two moves due to exceed lowerbound \n            l = -1;\n            r = n >> 1;\n            while (l + 1 < r) {\n                int m = (l + r) >> 1;\n                if (i - p2[m] > limit) l = m;\n                else r = m;\n            }\n            l += 1;\n            // calculate and update the answer\n            ans = min(ans, ((n>>1) - k - l - d[i]) + (k+l)*2);\n        }\n        return ans;\n    }\n};\n```\n\n
[]