prefixsum sliding window O(N)
Intuition\nDuring contest , I did the simple O(N*K) solution where for every position in nums, I looked for k different items left and right of the position. To
# Intuition\nDuring contest , I did the simple O(N*K) solution where for every position in nums, I looked for k different items left and right of the position. To find the nearest item from position, I used the sorted array of marked(1) numbers.\n\n        N = len(nums)\n        marked = []\n        for i,x in enumerate(nums):\n            if 1 == x:\n                marked.append(i)\n\nI also did binary search to find the distance left/right of current position.\n\nThen I thought I can get lidx/ridx using following formula,\n\n```\nlidx = max(0,iidx- (half of pointsNeeded + 1 in case of odd) )\nridx = min(lidx + pointsNeeded, len(marked)-1)\n```\n\nI was able to get the cost(`calcCost`) from lidx, position and points needed. \n\n```\ndef calcCost(lidx, ii, ptNeeded)\n```\n\n\n# Approach\nPrefixsum , sliding window.\n\n# Complexity\n- Time complexity:\n`O(N)`\n- Space complexity:\n`O(N)`\n# Code\n```\n\nSearchResult = namedtuple(\'SearchResult\',\'points,cost\')\n\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        \n        nums = [0] + nums + [0]\n        N = len(nums)\n        marked = []\n        bisect_memo = [0]*N\n        for i,x in enumerate(nums):\n            bisect_memo[i] = len(marked)\n            if 1 == x:\n                marked.append(i)\n                \n        if 0 == len(marked):\n            return k*2 # we can only apply rule1 for all the points\n\n        # make the prefix memo\n        presum = [0] + list(accumulate(marked))\n\n        def calcCost(lidx,ii,ptNeeded):\n            iidx = bisect_memo[ii]\n            if lidx > iidx:\n                lidx = iidx\n            ridx = min(lidx+ptNeeded-1,len(marked)-1)\n            points = (ridx+1)-lidx\n            if points < ptNeeded:\n                return SearchResult(0,0)\n \n            cost = 0\n            lpt = iidx-lidx\n            assert(lpt >= 0)\n            cost += lpt*ii - (presum[iidx] - presum[lidx])\n            if ridx >= iidx:\n                rpt = (ridx+1)-iidx\n                assert(rpt >= 0)\n                cost += (presum[ridx+1] - presum[iidx]) - rpt*ii\n            return SearchResult(points,cost)\n\n        def cntSet(ii,ptNeeded):\n            # calculate number of items set between i-mid to i+mid\n            more   = ptNeeded-nums[ii]\n            mid    = (more>>1) + (more&1)\n\n            iidx = bisect_memo[ii]\n\n            lidx = max(0,iidx-mid)\n            ridx = min(lidx+ptNeeded-1,len(marked)-1)\n            points = (ridx+1)-lidx\n            if points < ptNeeded:\n                lidx = max(0,ridx-ptNeeded+1)\n\n            ptA,costA = calcCost(lidx,ii,ptNeeded)\n            ptB,costB = calcCost(lidx+1,ii,ptNeeded)\n\n\n            if ptA != ptNeeded:\n                ptA,costA = ptB,costB\n            \n            if ptB == ptNeeded:\n                costA = min(costA,costB)\n\n            if ptA < ptNeeded:\n                return SearchResult(0,0)\n            return SearchResult(ptA,costA)\n        \n        \n        INF = float(\'Inf\')\n        result = N*k\n        for i in range(1,N-1):\n            kk,ct = k,0\n            kk -= nums[i]\n            if 0 == kk:\n                return ct\n            kk -= nums[i-1]\n            ct += nums[i-1]\n            if 0 == kk:\n                return ct\n            kk -= nums[i+1]\n            ct += nums[i+1]\n            appl   = min(kk,maxChanges)\n            kk    -= appl\n            ct    += appl*2\n            if 0 == kk:\n                assert(ct >= 0)\n                result = min(result,ct)\n                #print(i,\'No need bisect\', ct)\n            else:\n                assert(kk > 0)\n                kk,ct = k,0\n                kk    -= appl\n                ct    += appl*2\n                res = cntSet(i,kk)\n                assert(res.cost >= 0)\n                assert(ct >= 0)\n                #print(i,res,kk)\n                if res.points == kk:\n                    result = min(result,res.cost+ct)\n        return result\n        \n```
['Sliding Window', 'Prefix Sum', 'Python3']