[Python] O(max(nlogn, limit)) solution using heap
For 2 <= target <= 2 * limit, we find the number of moves necessary to make it so that nums[i] + nums[-i-1] == target for all i. We return the minimum of these.
For `2 <= target <= 2 * limit`, we find the number of moves necessary to make it so that `nums[i] + nums[-i-1] == target` for all `i`. We return the minimum of these.\n\nTo do this, for each `i`, we record the range of numbers which can be achieved in one move; this is readily seen to be `[1 + min(nums[i], nums[-i-1], max(nums[i], nums[-1-1]) + limit]`. We then sort these pairs by their minimum value, and while we are looping through the possible targets, we keep track of how many intervals contain `target`. We do this using a heap containing the upper bounds of the interval, ejecting an interval whenever this is less than target. Once we know the number of pairs whose sum can be changed to target in one move, we determine the number of moves necessary to transform every pair to target as follows: every pair which requires two moves to transform to target we count twice. Every pair whose original sum is equal to `target` we count zero times. Every pair which can be transformed to target in one move but which is not equal to `target` initially gets counted once.\n\n```\nimport heapq\n\nclass Solution:\n    def minMoves(self, nums: List[int], limit: int) -> int:\n        def getRange(pair):\n            """\n            for a given pair, returns the range of sums that\n            can be gotten from the pair after one move\n            """\n            return [1 + min(pair), limit + max(pair)]\n        ranges = [getRange([nums[i], nums[-i-1]]) for i in range(len(nums)//2)]\n        ranges.sort()\n        sums = [nums[i] + nums[-i-1] for i in range(len(nums)//2)]\n        sums = collections.Counter(sums)\n        inRange = []\n        res = float(\'inf\')\n        idx = 0\n        numInRange = 0\n        for target in range(2, 2 * limit + 1):\n            while idx < len(ranges) and ranges[idx][0] <= target:\n                heapq.heappush(inRange, ranges[idx][1])\n                numInRange += 1\n                idx += 1\n            waiting = True\n            while waiting and inRange != []:\n                upper = heapq.heappop(inRange)\n                if target <= upper:\n                    waiting = False\n                    heapq.heappush(inRange, upper)\n                else:\n                    numInRange -= 1\n            res = min(res, len(nums) - numInRange - sums[target])\n        return res\n```
[]