[Python] O(n) Sliding Window with detailed explanation
\nclass Solution:\n    def minMoves(self, nums: List[int], k: int) -> int:\n        # we use a rolling window, which keeps indices of consecutive k appearences 
```\nclass Solution:\n    def minMoves(self, nums: List[int], k: int) -> int:\n        # we use a rolling window, which keeps indices of consecutive k appearences of 1s\n        # lets say the index of 1s in current window is A = [a0, a1, ... ak-1]\n        # then we are trying to find an index x, such that\n        # we transform A to consecutive indices [x, x+1, ... x+k-1].\n        # Notice the moves needed is |a0 - x| + |a1 - (x+1)| + ... + |a(k-1) - (x+k-1)|\n        # do a little transformation -> |a0-x| + |(a1-1) - x| + |(a(k-1) - (k-1)) - x|\n        # it is obvious that when x is the median of [a0, a1-1, a2-2, ... a(k-1) - (k-1)]\n        # the solution reach the minimum\n        # Also, notice that if we shift A for any constant, that is for each i, ai -> ai+a,\n        # the median x changes but the summation does not change\n        # therefore, for ith occurence of 1, we subtract its index with k, ai -> ai-i.\n        # To find the rolling maximum value of c = |a0-x| + |(a1-1) - x| + |(a(k-1) - (k-1)) - x|\n        # we just need to update the value instead of recalculating. \n        # When we update the median from x -> y, for the first\n        # half A we add (y-x) to each of them, for the second half of A we subtract (y-x)\n        # and we need to remove |a0-x| and include |ak-y| where ak is the next index of 1\n\t\t\n\t\t# Time complexity: O(n), space complexity: O(n)\n        \n        ones = []\n        for i in range(len(nums)):\n            if nums[i] == 1:\n                ones.append(i - len(ones))\n                \n        # rolling window\n        cur = 0\n        # calculate initial summation\n        med = k//2\n        for i in range(k):\n            cur += abs(ones[i] - ones[med])\n            \n        res = cur\n        # rolling window update \n        for i in range(1, len(ones) - k + 1):\n            # find median of ones[i:i+k]\n            new_med = k//2+i\n            if k%2==0:\n                # if k is odd, the sum of abs difference will not change excluding the first value\n                cur += ones[new_med] - ones[med] \n            # update first value and last value\n            cur -= ones[med] - ones[i-1]\n            cur += ones[i+k-1] - ones[new_med]\n            med = new_med\n            res = min(res, cur)\n        return res\n        \n        \n```
[]