[Python] Simple O(n+k) solution
The key is to keep track of how many pairs of elements need to make one move or two moves\n\n\tclass Solution:\n\t\tdef minMoves(self, nums: List[int], limit: i
The key is to keep track of how many pairs of elements need to make one move or two moves\n\n\tclass Solution:\n\t\tdef minMoves(self, nums: List[int], limit: int) -> int:\n\t\t\tmove0 = [0]*(limit*2+2)\n\t\t\tmove1 = [0]*(limit*2+2)\n\n\t\t\tfor i in range(len(nums)//2):\n\t\t\t\ta, b = nums[i], nums[len(nums)-1-i]\n\t\t\t\ta, b = min(a, b), max(a, b)\n\n\t\t\t\tmove0[a+b] += 1\n\n\t\t\t\t# note a + 1 <= b + 1 <= a + b <= a + limit <= b + limit\n\t\t\t\t# making one change, we take all values from a+1 to b+limit\n\t\t\t\t# but we make no change if total is a+b\n\n\t\t\t\tsm, lg = a+1, b+limit\n\t\t\t\tmove1[sm] += 1\n\t\t\t\tmove1[a+b] -= 1\n\t\t\t\tmove1[a+b+1] += 1\n\t\t\t\tmove1[lg+1] -= 1 \n\n\t\t\t# now iterate and calculate the number of moves and find the smallest\n\t\t\tres = len(nums)\n\n\t\t\tps = 0\n\t\t\tfor i in range(len(move0)):\n\t\t\t\tps += move1[i] # use partial sum to record the number of pairs that can take 1 move when the target is i\n\t\t\t\t# number of elements - ones that take 0 move - ones that takes 1 move\n\t\t\t\tres = min(res, len(nums) - 2*move0[i] - ps)\n\t\t\treturn res
[]