moving window (move to the median) + prefix sum
record indices of all ones, and calculate their gaps, we proceed with only the gap array (together with its prefix sum)\n\nkeep a sliding window of gaps with le
record indices of all ones, and calculate their gaps, we proceed with only the gap array (together with its prefix sum)\n\nkeep a sliding window of gaps with length k-1\n\nfor a certain window, the best thing to do is to move all ones towards its median point, in such cases, the total moves we need would be (draw a picture to understand)\n\n1*gap[0] + 2*gap[1]  ....... 2*gap[-2]+1*gap[-1]\n\nfor a certain window length we precalculate the arrays of coefficients.\n\nsliding the coefficients array we see that when we move the window by one, which now starts from i, the first half from i-1 would be decreased by their sum, while the new second half would add to the moving best distance -- both could be calculated easily with the stored presum. then we simply keep the running min of the best moves we get in each window, and return the best one in the end\n\n\n\n# Code\n```\nclass Solution:\n    def minMoves(self, nums: List[int], k: int) -> int:\n        if k == 1:return 0\n        ones = []\n        for i,a in enumerate(nums):\n            if a == 1:\n                ones.append(i)\n        gaps = [ones[i+1] - ones[i] - 1 for i in range(len(ones)-1)]\n        psum = [0]\n        for g in gaps:\n            psum.append(psum[-1]+g)\n        coeffs = [min(i,k-2-i)+1 for i in range(k-1)]\n        w = max(coeffs)\n        res = sum([coeffs[i]*gaps[i] for i in range(k-1)])\n        curres = res\n        n = len(gaps)\n        for i in range(1,n+2-k):\n            dec = psum[i+w-1] - psum[i-1]\n            inc = psum[i+k-1] - psum[i+k-w-1]\n            curres += inc - dec\n            res = min(res,curres)\n\n        return res\n```
['Python3']