Line Sweep Algorithm | Python
\nclass Solution:\n    def minMoves_v1(self, nums: List[int], limit: int) -> int:\n        """\n        TLE, for digestion\n        """\n        \n        # com
```\nclass Solution:\n    def minMoves_v1(self, nums: List[int], limit: int) -> int:\n        """\n        TLE, for digestion\n        """\n        \n        # compute needed moves\n        def n_moves(a, b, s, limit):\n            """\n            If the pair is (a, b), the target sum is s, given the limit,\n            what is the needed number of moves?\n            """\n            if a + b == s:\n                return 0\n            if a > b:\n                a, b = b, a\n        \n            if a + b > s:\n                delta = a + b - s\n                if b - 1 >= delta:\n                    return 1\n                else:\n                    return 2\n            if a + b < s:\n                delta = s - a - b\n                if limit - a >= delta:\n                    return 1\n                else:\n                    return 2\n                \n                \n        n = len(nums)\n        def f(median):\n            res = 0\n            for i in range(n//2):\n                res += n_moves(nums[i], nums[n-1-i], median, limit)\n            return res\n        \n        \n        return min(f(i) for i in range(1, 2 * limit + 1))\n    \n    \n    def minMoves(self, nums: List[int], limit: int) -> int:\n        """\n        Line Sweep\n        \n        For each possible target sum  2 <= s <= 2 * limit], if we require all the pairs sum to\n        s, what is the needed number of moves N(s)? \n        We choose the minimal of these N(s).\n        \n        Different from V1, we use Line Sweep and Prefix sum to effect compute N(s).\n        """\n        \n        n = len(nums)\n        m = n // 2\n        \n        d = collections.defaultdict(int)\n        \n        for i in range(m):\n            a, b = nums[i], nums[~i]\n            s, e = min(a, b), max(a, b)\n            \n            # 1 changes in this interval [s + 1, e + limit] \n            d[s + 1] -= 1\n            d[e + limit + 1] += 1\n            \n            d[s + e] -= 1\n            d[s + e + 1] += 1\n            \n        res = n # each pair needs at most 2 moves, in total n//2 pairs, at most n moves\n        cur = n\n        \n        # compute for each pair sum, call it target, the needed total moves\n        # pick the minimum\n        for target in range(2, 2 * limit + 1):\n            cur += d[target]\n            res = min(res, cur)\n        return res\n        \n        \n```
['Python']