[Python3] difference array
Approach 1 - difference array O(N)\nThis implementation is based on this post which gives an excellent explanation of the algo. \n\n\nclass Solution:\n    def m
**Approach 1** - difference array `O(N)`\nThis implementation is based on this [post](https://leetcode.com/problems/minimum-moves-to-make-array-complementary/discuss/952773/PythonJava-simple-O(max(n-k))-method) which gives an excellent explanation of the algo. \n\n```\nclass Solution:\n    def minMoves(self, nums: List[int], limit: int) -> int:\n        diff = [0]*(2*limit+2) # difference array \n        \n        for i in range(len(nums)//2): \n            m = min(nums[i], nums[~i]) + 1 # lower bound \n            diff[m] += -1\n            x = nums[i] + nums[~i]\n            diff[x] += -1\n            diff[x+1] += 1\n            M = max(nums[i], nums[~i]) + 1 + limit # upper bound \n            diff[M] += 1\n        \n        for i in range(1, len(diff)): diff[i] += diff[i-1] # prefix sum \n        return len(nums) + min(diff)\n```\n\n**Approach 2** - binary search \nThis was similar to my original approach. The idea is quite simiarl to that of Approach 1. But a key difference is that the we use two arrays `lower` and `upper` to keep track of lower and upper bounds so that when a value `x` is given we know how many extras to add by counting the number of elements in `lower` that are larger than `x` and the number of elements in `upper` that are smaller than `x`. \n\n```\nclass Solution:\n    def minMoves(self, nums: List[int], limit: int) -> int:\n        freq = {} # frequency table \n        lower, upper = [], []\n        \n        for i in range(len(nums)//2): \n            x = nums[i] + nums[~i]\n            freq[x] = 1 + freq.get(x, 0)\n            lower.append(min(nums[i], nums[~i]))\n            upper.append(max(nums[i], nums[~i]) + 1 + limit)\n        \n        lower.sort()\n        upper.sort()\n        \n        ans = inf\n        for x in freq: \n            k = len(lower) - bisect_left(lower, x)\n            kk = bisect_right(upper, x)\n            val = len(nums)//2 - freq[x] + k + kk\n            ans = min(ans, val)\n        return ans \n```\n\n
['Python3']