Python 3: TC O(N), SC O(N): Sliding Window of k Ones, Pigeonhole, Triangle
Intuition\n\nThis is a really tough problem to get the general solution for IMO. It\'s fairly straightforward to see that we want to start with regions with a h
# Intuition\n\nThis is a really tough problem to get the general solution for IMO. It\'s fairly straightforward to see that we want to start with regions with a high density of ones, usually, then swap in a few more ones.\n\nBut "usually" means "not always," and we need something that\'s always right.\n\nSo here\'s what I found that makes the problem tractable.\n\n## Sliding Window of `k` Ones\n\nWe know that we need to group `k` ones together.\n\nIn early approaches I tried looking at the closest ones to the left and right of a current window of size `k`, but it was getting too complicated\n* how many ones are to the left and right of the window? it varies\n* what\'s the cost to swap ones into the current window?\n  * depends on where the current window is\n  * *and* it depends on where the zeros are in the current window\n\nEventually I gave up on that. We can\'t afford `O(n*k)` because `k` can be order `n`, and `n` is `1e5` at most. `1e10` ops will give TLE for sure.\n\nBut it got me thinking: **we want to move the ones as little as possible, and we never want to swap a 1 past another one, or a zero past another zero.**\n\nTo avoid having to iterate `O(k)` times for numbers of ones to the left and right of the current window of length `k`, I *changed the window*.\n\n**I looked at sliding windows where the window has exactly `k` ones in it.**\n\nHere\'s an example:\n```a\n0011110100111010111010111000      k == 15 ones\n```\n\nWhy this? Because we can determine more quickly\n* what the optimal solution is for this window\n* no `O(k)` iterating over window bounds\n* the solution is tractable\n\n## The Cost to Group `k` Ones\n\nIn the example above:\n\n```a\n0011110100111010111010111000      k == 15 ones\n```\n\nWe have `k` ones by construction. To group them, we know that all the 1s must be adjacent. Equivalently, **all zeros have to be moved to the left or right edge. Some zeros can move left and others move right.**\n\nBecause we know that we should never swap zeros, **all zeros left of some "critical position" will move left, and the rest will move right.** In other words, we **aways move each zero to the closer of the next left or right location for a zero.**\n\nWe can look at the cost to move a zero at index `i` left, in a window of indices `l..r`:\n* if there are no prior zeros in the window: `i-l`\n* if there is one prior zero in the winow: `i-l-1`\n  * index `l` is already zero\n  * so we move to index `l+1` instead\n* if there are `z` prior zeros: `i-l-z`\n\nThe sum of this is\n* `i-l` for the first zero\n* `i-l+1` for the second zero\n* `i-l-z` for the `(z+1)`th zero\n\nRewriting this a bit, we see that\n* the left-most `z` zeros belong at indices `l, l+1, .., l+z-1`\n* so if their current indices sum to `lsum`\n* then the cost is `lsum - (l + l+1 + .. + l+z-1)`\n\nWhich is great, because\n* maintaining cumulative sums is easy(ish)\n* the sums of contiguous integers are triangle numbers, which we can calculate in `O(1)`\n  * if you don\'t have the formula memorized: **memorize the triangle number formula. You\'re going to need it**\n\n## Example of Move Cost for Each Index\n\nThat\'s all pretty dense, so here\'s a smaller example where I\'ve labeled each zero with it\'s move cost to get to the next left or right target position for a zero\n\n```a\n                                    :\n# left cost  0  0         4   5  5  :        8   9       12\n             0  0 1 1 1 1 0 1 0  0  :  1 1 1 0 1 0 1 1 1 0 \n# right cost 10 9         8   7  7  :       4   3       0    \n                                    :\n        <-- cheaper to move left    :\n                                    :  cheaper to move right ->\n```\n\nNote that the cost to move left or right is the number of preceding/succeeding ones, which makes sense. It costs one to swap each zero past each prior 1 on its way to the left edge. Same logic for right.\n\nSo in the algorithm we\'ll look at the left-most zero in `right_idxs`. While it\'s move cost to the left is lower (which will eventually happen as we move the window right), we\'ll pop it from `right_idxs` and append it to `left_idxs`.\n\n# Approach\n\nSo now an algorithm takes shape. We have a current window `l` and `r`.\n\nFor each next index `r`, if it\'s a one, increment the number of ones.\n\nIf the number of ones is now `k+1`, then\n* drop the left index, which we ensure is always a one to keep things simple\n* then keep dropping zeros off the left\n\nNext, we look at `left_idxs` and `right_idxs`. As we add ones, the right costs will increase by one. As we remove ones from the left edge, the left costs will decrease. **So as we iterate, indices will move from `right_idxs` to `left_idxs`.**\n\nSpeaking of which, Whenever we change the window, indices may need to be moved from `right_idxs` to `left_idxs`. To do this:\n* look at the `right_idxs[0]` if it exists\n* look at its "move cost" to the left and right\n* if the left cost is smaller, move `right_idxs[0]` to the end of `left_idxs`\n  * **two deques**\n  * record the running sum of indices in the deques because we\'ll need them for `O(1)` work per element (amortized)\n\n**Finally:** now that we have the up-to-date left and right indices and their sums, we use triangle numbers to compute\n* the cost to move all `left_idxs` flush against the left edge of the window: `lsum - (sum of l + l+1 + ... + l+len(left_idxs)-1)`\n* the cost to move all `right_idxs` flush against the right edge of the window: `rsum = (sum of r + r-1 + ... + r-len(right_idxs)+1) - rsum`\n* **the total cost for the current window is `lsum + rsum`**, i.e. the cost to completely push all the zeros in the window to the "cheaper" of the two ends\n\n# The Actual Code versus This\n\nAgain, it took me a long time with several failed approaches before getting this.\n\nSo the code isn\'t as clean as it could be, sorry.\n\nIn particular, you\'ll see that I consider both\n* moving the left-most zero in `right_idxs` left (correct)\n* moving the right-most zero in `left_idxs` right (unnecessary)\n\nWe know moving zeros right is never relevant from the ASCII art above. We saw above that the move cost is the number of ones in the way, and\n* the left cost is non-increasing as we slide the window right\n* the right cost is non-decreasing as we slid the window right\n\nTherefore the only possible way any of the indices of zeros can move is to the left after we iterate.\n\nBut I only figured this out while writing it up, so... yeah. Oh well.\n\n# Complexity\n- Time complexity: `O(N)`\n  - we trivially do `O(1)` work in each iteration except for shuffling elements between `right_idxs` to `left_idxs`\n  - from the discussion above, we know that indices only move left\n  - each index is appended exactly once to right\n  - at most each element is moved ones from `right_idxs` to `left_idxs`\n  - and at most each element is popped once from `left_idxs` as we advance the window\n  - each of these are `O(1)` append/pop(left) operations, which happen at most once, so it\'s `O(1)` amortized per element (some iterations can do `O(N)` work though, hence *amortized*)\n  - and thus the "rebalancing cost" summed across all elements is about `4*N`, i.e. `O(N)`\n\n- Space complexity: `O(N)`. At any time, the indices of all zeros are in at most one of `left_idxs` and `right_idxs`. So at most `N` indices are ever in there.\n\n# Code\n```\nclass Solution:\n    def minMoves(self, nums: List[int], k: int) -> int:\n        # nums has 1s and zeros\n\n        # can swap two adj in one move\n        \n        # what\'s the minimum number of moves to get k consec. ones?\n        # something something sliding window?\n\n        # move windows of size k around\n        #   ............000111011101011101............\n        #               ------------------\n        #                    have k-7 zeros\n        #     \n\n        # simpler example:\n        #          ............. 010110 ...........\n        #                        ------\n        #                           k, 3 zeros\n        #     if we know the prior indices of ones, and we want to swap in 1:\n        #          > index of first 0 in the window: that\'s the cost to swap it to the front\n        #          > then keep swapping to the location of the prior 1\n        #          > so it\'s firstZeroIdx - lastOneIdx\n        #\n        #          > repeat for later zeros: the above gets us e.g. 01101 -> 11101\n        #              so we need to get to 01111 (swap zero at window idx 3 to front of window), then swap prior one into position\n        #                \n        #            so it\'s sum of first z zeros minus sum of prior z one indices\n        #     when we move the window by 1: prior z one indices increases if we shifted off a 1\n        #     and sum of first z zeros increases potentially if we shift off a zero, otherwise decreases by z\n\n        # that involves O(k) work per shift, too much\n        # can we reduce that to O(1)?\n        # what if we know the cost to swap each prior 1 into position?\n\n        #   like 11000110100\n        #                 1\n        #                  2\n        # doesn\'t reall help. We could store the cost of moving k, but that would be O(n*k) dp which is still too expensive\n        \n        # what about\n        #    having a sliding window of k ones | we get the cost to swap those k ones into position. SOME contig. set of 1s\n        #    will be the answer b/c it doesn\'t make sense to swap ones past each other\n        #\n        #    there are many indices in the window though\n        #\n        #       1101001010101010001   k==9\n        # BUT: to "condense" all the ones, we know the 0s have to get swapped to one side or the other!\n        #     to swap left: sum of zero indices minus sum of of where all the zeros would go (l, l+1,...)\n        #     to swap right: sum of where all the zeros would go minus sum of zero indices (r, r-1, ...)\n\n        # so we "just" need the sum of zero indices relative to l\n\n        if k == 1: return 0\n\n        # earlier: had a more naive solution what\n        #    found windows with k ones\n        #       then computed cost to shift all the zeros to the left or right edges\n        #       mostly right, except it misses a case like this:\n        #\n        #     10111111111111111111101\n        #  clearly the solution is to swap twice, putting one zero on either side\n        #\n        # how can we fix this?\n        #      we have a 0 close to the left edge: move it left\n        #      we have a zero close to the right edge: move it right\n        #\n        #      zeros start out closest to right edge, then get closer to left as we advance the window\n        #      so we gradually "shuffle" indices left\n        #      deque stuff!!!\n\n        l = nums.index(1)\n\n        # two deques: left_idxs are indices of zeros where it\'s cheaper to move that zero to the left edge\n        left_idxs = deque()\n        lsum = 0\n        right_idxs = deque()\n        rsum = 0\n\n        ones = 1\n        ans = math.inf\n        for r in range(l+1, len(nums)):\n            if nums[r] == 1:\n                ones += 1\n                if ones > k:\n                    ones -= 1 # drop left-most 1\n                    l += 1\n\n                    # TODO: we know all the indices of zeros so we can probably avoid re-iterating\n                    while nums[l] == 0: l += 1 # also drop left-most zeros we no longer need\n                    while left_idxs and left_idxs[0] < l:\n                        lsum -= left_idxs[0]\n                        left_idxs.popleft()\n                    while right_idxs and right_idxs[0] < l:\n                        rsum -= right_idxs[0]\n                        right_idxs.popleft()\n            else:\n                right_idxs.append(r)\n                rsum += r\n\n            # cost to move zero left: current index is l, move it to l+num_earlier_zeros\n            # b/c after swapping prior zeros into position, the target index advances by the number of zeros\n\n            while right_idxs and right_idxs[0]-l-len(left_idxs) < r-len(right_idxs)+1-right_idxs[0]:\n                # less expensive to shift right_idxs[0] left\n                lsum += right_idxs[0]\n                rsum -= right_idxs[0]\n                left_idxs.append(right_idxs.popleft())\n\n            while left_idxs and left_idxs[-1]-l-len(left_idxs)+1 > r-len(right_idxs)-left_idxs[-1]:\n                # less expensive to shift left_idxs[-1] right\n                lsum -= left_idxs[-1]\n                rsum += left_idxs[-1]\n                right_idxs.appendleft(left_idxs.pop())\n\n            if ones == k:\n                # l cost: move the left zeroes to l..l+len(left_idxs)-1\n                lcost = lsum - ((l+len(left_idxs)-1)*(l+len(left_idxs))//2 - (l-1)*l//2)\n                # r cost: move right zeros to r-len(left_idxs)+1 .. r\n                rcost = r*(r+1)//2 - (r-len(right_idxs))*(r-len(right_idxs)+1)//2 - rsum\n\n                ans = min(ans, lcost + rcost)\n\n        return ans\n\n        ### STILL not quite right\n\n        # I messed up a case like this:\n        #    1000000011\n        #   it\'s cheaper to move all the zeros left even though some are closer than right\n        #   "easy" way to check: look at the right-most 0\n        #      cost to shift left: 1, because\n        #         it\'s like 8 spots above l\n        #         but 7 of those prior 8 are also zeros\n        #         so we shift idx-l-preceedingZeros == 1\n        #      cost to shift right: 2, because\n        #         shift right r-idx = 2, minus zero because there are no zeros in the way\n        #    so we\'d detect that the right-most zero index actually belongs in left_idxs\n        #    this property is monotonic, in that if idx is closer to left, then idx\' > idx\n        #    is either still closer to left, or should now be in right\n        #\n        #    so we can repair the invariant that all left_idxs shift left, all right_idxs shift right\n        #    by looking at the right-most left and left-most right, and moving until the invariant holds again\n\n        # UGHHHH\n```
['Python3']