Python O(N) prefixsum
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        N = len(nums)\n        marked = []\n        for i,x in enumerate(nums):\n            if 1 == x:\n                marked.append(i)\n```\n\nNow if we can find the distance from current position by binary search we can calculate the result in `O(N*log N)` time.\n\nIn case we select too many `1`s from the distance, I had to skip one that is most costly.\n\nI kept doing `bisect_left` on `marked` list that I introduced and got TLE. So I have just changed `bisect_left` invocation to `bisect_memo` instead and it beats `100%`.\n\n# Approach\n\nPrefix-sum, binary search.\n\n# Complexity\n- Time complexity:\n`O(N*log N)`\n- Space complexity:\n`O(N)`\n\n# Code\n```\n\nSearchResult = namedtuple(\'SearchResult\',\'points,cost,lidx,ridx\')\n\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        \n        # let us start with the median of the set positions\n        N = len(nums)\n        marked = []\n        for i,x in enumerate(nums):\n            if 1 == x:\n                marked.append(i)\n                \n        if 0 == len(marked):\n            return k*2\n\n        M = len(marked)\n        presum = [0]*(M+1)\n        for i in range(M):\n            presum[i+1] = presum[i] + marked[i]\n\n        bisect_memo = [0]*(N+1)\n        cur = 0\n        for i in range(N):\n            # when we are bisecting for position i\n            # bisect_left(marked, i)\n            if marked and cur < len(marked) and marked[cur] < i:\n                cur += 1\n            bisect_memo[i] = cur\n\n        def cntSet(ii,mid, ptLmt):\n            # calculate number of items set between i-mid to i+mid\n            left = max(0,ii-mid)\n            right = min(ii+mid,N-1)\n            \n            lidx = bisect_memo[left]\n            if lidx >= len(marked):\n                return SearchResult(0,0,0,0)\n\n            ridx = bisect_memo[right]\n            if ridx < len(marked) and marked[ridx] == right:\n                pass\n            else:\n                ridx -= 1 # skip last\n\n            iidx = bisect_memo[ii]\n\n            points = (ridx+1)-lidx\n            if points > ptLmt:\n                if marked[ridx] > ii:\n                    rdist = marked[ridx]-ii\n                    ldist = ii-marked[lidx]\n                    if rdist >= ldist:\n                        ridx -= 1\n                    else:\n                        ldist += 1\n                else:\n                    lidx += 1\n                    \n            points = (ridx+1)-lidx\n            cost = 0\n            if points > 0:\n                if marked[lidx] <= ii:\n                    cost = 0\n                    if nums[ii] == 1: # when marked\n                        lpt = iidx+1-lidx\n                        cost += lpt*ii - (presum[iidx+1] - presum[lidx])\n                        if ridx > iidx:\n                            rpt = (ridx+1)-(iidx+1)\n                            cost += (presum[ridx+1] - presum[iidx+1]) - rpt*ii\n                    else:\n                        lpt = iidx-lidx\n                        cost += lpt*ii - (presum[iidx] - presum[lidx])\n                        if ridx >= iidx:\n                            rpt = (ridx+1)-iidx\n                            cost += (presum[ridx+1] - presum[iidx]) - rpt*ii\n                else:\n                    cost = 0\n                    if nums[ii] == 1: # when marked\n                        assert(ridx > iidx)\n                        rpt = (ridx+1)-(iidx+1)\n                        cost += (presum[ridx+1] - presum[iidx+1]) - rpt*ii\n                    else:\n                        assert(ridx >= iidx)\n                        rpt = (ridx+1)-iidx\n                        cost += (presum[ridx+1] - presum[iidx]) - rpt*ii\n                \n            return SearchResult(points,cost, lidx, ridx)\n        \n        \n        INF = float(\'Inf\')\n        result = INF\n        for i,head in enumerate(nums):\n            kk,ct = k,0\n            if 1 == head:\n                kk -= 1\n            if kk > 0 and i > 0 and nums[i-1] == 1:\n                kk -= 1\n                ct += 1\n            if kk > 0 and (i+1) < len(nums) and nums[i+1] == 1:\n                kk -= 1\n                ct += 1\n            appl   = min(kk,maxChanges)\n            kk    -= appl\n            ct    += appl*2\n            if 0 == kk:\n                result = min(result,ct)\n                #print(i,\'No need bisect\', ct)\n            else:\n                kk,ct = k,0\n                kk    -= appl\n                ct    += appl*2\n                # now we can kind of calculate\n                lo = 0\n                hi = N\n                \n                while lo < hi:\n                    \n                    mid = (lo+hi) >> 1\n                    res = cntSet(i,mid, kk)\n                    if res.points >= kk:\n                        hi = mid\n                    else:\n                        lo = mid+1\n                res = cntSet(i,lo, kk)\n                #print(i,\'lo\', res,kk)\n                if res.points == kk:\n                    result = min(result,res.cost+ct)\n                res = cntSet(i,hi, kk)\n                #print(i,\'hi\', res,kk)\n                if res.points == kk:\n                    result = min(result,res.cost+ct)\n        return result\n        \n```
['Binary Search', 'Prefix Sum', 'Python3']