C++ Understandable Solution Reverse Line-Sweep Prefix Sum Detailed Explanation
Approach\nLine sweep: so what we do is keep a line sweep array up to the max answer we can return, so s[200002]; s will represent the cost of taking that certai
# Approach\nLine sweep: so what we do is keep a line sweep array up to the max answer we can return, so s[200002]; s will represent the cost of taking that certain number. E.g. s[20] will be the lowest cost to turn ALL pairs in the array into 20.\n\nWe will find the smallest and the largest of each pair of numbers, so `small` and `big` respectively. We first realise that everything can be done in 2 moves (up to the limit of course), by just swapping both values. So we will do s[1] += 2 to add 2 at the beginning of the prefix sum array, assigning a default moves taken of 2 to every single value onwards. We will then find the numbers which will require less than 2 moves via our line sweep array, and subtract that range accordingly. Everything above the range will get a +1 added to it so that it returns to being 2 moves. \n\nNote: it\'s actually kind of a reverse line sweep -> instead of doing 1 0 0 0 -1, we are doing -1 0 0 0 1, because everything starts off with += 2 at the very start, and we want to reduce these values.\n\nSo now we find the range of our \'1\' move-rs.\nFrom small+1 onwards, we can change the big to anything under lim. So small+1 is our lower bound for a cost of 1, so we do `s[small+1]--;`. We then try to find the maximum range: this is `s[big+lim]`, since we can change small to the limit. We then do `s[big+lim+1]++;` so that everthing onwards will return to being a cost of 2. That\'s all the 1\'s done.\n\nNow to do the 0s - well there\'s only 1 value that can be 0, which is `s[small+big]` so just do `s[small+big]--;`. And right after it, we want to resume the 1\'s moves again so do `s[small+big+1]++;`. That\'s all.\n\nOriginally when I was approaching this question, I tried to count the number of occurrences of each possible candidate. E.g. if the sum 5 occurred 11 times (the most), I would naively assume it would (probably) be the cheapest to make. However, it\'s not that simple since other sums can be made cheaper if they have more 1s than the 2s for a sum of 5, so we need a method to do all of them at the same time. Line sweep is not exactly obvious, but the bounds allow for it and you can calculate it for every single number in O(n).\n\n# Code\n```\nclass Solution {\npublic:\n    int s[200002]; // sweep array\n    int minMoves(vector<int>& nums, int limit) {\n        int n = nums.size();\n        int reach = 0;\n        for (int i = 0; i < n/2; i++) {\n            int small = min(nums[i],nums[n-1-i]);\n            int big = max(nums[i], nums[n-1-i]);\n            reach = max(reach, small+big);\n            // Everything gets default 2 moves, subtract off moves\n            // if we don\'t need to take it\n            s[1] += 2;\n            s[small+1]--;\n            s[small+big]--;\n            s[small+big+1]++;\n            s[big+limit+1]++;\n        }\n        reach = max(reach, limit*2);\n        int ans = INT_MAX;\n        for (int i = 2; i <= reach; i++) {\n            s[i] += s[i-1];\n            ans = min(ans, s[i]);\n        }\n        return ans;\n    }\n};\n```
['C++']