[Python] The trick and related problems
We consider a more complex test case  nums = [1,0,1,0,0,1,1,0,0,0,1,1,0,1] and k=4\n\nIn this problem, only the position of ones is relevant.\n\npython\npos = [
We consider a more complex test case  `nums = [1,0,1,0,0,1,1,0,0,0,1,1,0,1]` and `k=4`\n\nIn this problem, only the position of ones is relevant.\n\n```python\npos = [p for p,x in enumerate(nums) if x == 1]\n# [0, 2, 5, 6, 10, 11, 13]\n```\n\nThe problem is now to consider every sliding window of side `k`. **The task is to move each element of the window to the median of the window.** (If `k` is even, we can choose either of the two most middle positions). If we calculate the cost from scratch for each of the window, we will TLE. We need to use the cost of one window to compute the cost of the next window.\n\n\n\n**This is the trick - we consider `pos[i] - i` for each of the ones.** The idea is this - if the current element is the `j`th element in the window and the left most element in the window is `j` units away you do not need to move the element.\n\nAs K_kkkyle mentioned in the comments, it is a common trick in competitive programming to use `a[i] - i` to convert a "min sum of moves to make numbers consecutive" problem into a "min sum of moves to a single point".\n\n```python\npos = [p-i for i,p in enumerate(pos)]\n# [0, 1, 3, 3, 6, 6, 7]\n```\n\nThe problem now is to consider every sliding window of side `k` - the difference of each element in the window with its median. In this example, `k=4` and it is now quite obvious that we will choose the right-most window for the cost of 4.\n\nWe want to reuse the computation for one sliding window for the next sliding window.\n\nWe split the sliding window into three parts - the median, the part left of the median and the part right of the median. We consider the cost of the left and right parts separately.\n\n```text\nBefore: abc | d | e   fg\nAfter:   bc   d | e | fgh\n```\nThe old median is `d` and the new median is `e`.  \n\nBefore the window moves\n\n```\n   .   .   .\n       .   .\n           .\n a   b   c   d   e   f   g  (h)\n               .   .   .\n               .   .\n               .\n```\n\nAfter the window moves\n\n```\n       .   .   .\n           .   .\n               .\n(a)  b   c   d   e   f   g   h\n                   .   .   .\n                   .   .\n                   .\n``` \n\nComparing the difference, `x` is lost, `o` is added.\n\n```\n   x   .   .   o\n       x   .   o\n           x   o\n a   b   c   d   e   f   g   h\n               x   .   .   o\n               x   .   o\n               x   o\n```\n\nIn summary\n- For the left part, the cost decreases by `d-a` and increases by `(e-d)*sizeleft`\n- For the right part, the cost increases by `h-e` and decreases by `(e-d)*sizeright`\n\n\nThe similar procedure happens if `k` is even, but `sizeleft` is not the same as `sizeright`.\n```text\nBefore: abc | d | e   f\nAfter:   bc   d | e | fg\n```\n\nThe full code is here. The tracking procedure can be compressed, but I have kept it expanded for your understanding (and this is what I submitted also).\n\n```python\nclass Solution:\n    def minMoves(self, nums: List[int], k: int) -> int:\n        pos = [p for p,x in enumerate(nums) if x == 1]\n        print(pos)\n\n        pos = [p-i for i,p in enumerate(pos)]        \n        print(pos)\n        \n        mid = k//2\n        sizeleft = mid\n        sizeright = k-1-sizeleft\n        \n        curleft = sum(abs(x - pos[mid]) for x in pos[:sizeleft])\n        curright = sum(abs(x - pos[mid]) for x in pos[mid+1:k])        \n        minres = curleft + curright\n        \n        print(curleft, curright, minres)\n        \n        for ptr in range(1, len(pos)-k+1):\n            # print("ptr", ptr, ptr+mid, ptr+k)\n            curleft -= (pos[ptr+mid-1] - pos[ptr-1])\n            curleft += (pos[ptr+mid] - pos[ptr+mid-1])*sizeleft\n        \n            curright -= (pos[ptr+mid] - pos[ptr+mid-1])*sizeright\n            curright += (pos[ptr+k-1] - pos[ptr+mid])\n        \n            minres = min(minres, curleft+curright)\n            # print(curleft, curright, minres)\n            \n        print()\n        return minres\n```\n\n\nI was able to solve this problem because I was exposed to related problems in the past.\n\n[Google Kickstart 2020 Round H Q3 - Rugby](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b027)\n\n\n[Codeforces Educational Round 99 Div 2E](https://codeforces.com/contest/1455/problem/E)
['Sliding Window', 'Python']