O(NK) to O(N*Log(K)) with picture. Different than the median way
Let\'s break problem into different sub problems.\n1. First sub problem is that we need to find a window that starts with 1 and end with 1 \n    and has k 1s in
Let\'s break problem into different sub problems.\n1. First sub problem is that we need to find a window that starts with 1 and end with 1 \n    and has k 1s inside it. Leading and trailing 0 does not\n\tcontribute to the number of 1s we are looking for,\n\tso we can skip them to make the window as small \n\tas we can.\n\t\n2. Now we have a window of some 1s and some 0s\n     and we want to bring all 1s together.\n\t This means we need to **bubble 0s either to the left or right of all 1s**\n\t for a 0 at ith position, we need to swap it with either\n\t* all 1s to the left of index i\n\t* all 1s to the right of index i\n\n    Best choice in terms of cost is **minimum** of above values\n    In the following picture, it\'s cheaper to bubble 0 at index 3 to left since there are only\n\ttwo 1s to the left of it, while there are five 1s to the right.\n![image](https://assets.leetcode.com/users/images/a4e5f50d-27fb-4b06-a935-9fbc0e31b5ed_1609387993.2791135.png)\n\n3. We can scan from left of the window to the right of the window,\n    and for each 0, calculate the cost \n\t1. if we move this 0 to the right vs \n\t2. if we move it to left\n\n\tWe need to take **minimum** of above two values and add it to overal swaps for this window.\n\tLet\'s call this BestForThisWindow, then ultimate result will be minimum of \n\tall BestForThisWindow values.\n    Bottle neck here is that this is a linear scan and overall complexity will be\n\tO(NK) which TLEs.\n \n 4. We can improve O(NK) to be O(NLog(K)) with Binary Search.\n     Let\'s first proof this is binary searchable:\n\t Consider following:\n\t \n\t ![image](https://assets.leetcode.com/users/images/f7e05854-1d77-4091-ab5d-941c95f35de7_1609389692.5640857.png)\n     \n\t p: number of 1s to the left of index 1\n\t q: number of 1s to the right of index 1\n\t \n\t `if x == 0` =>  `p\' = p` and `q\' = q`\n\t `if x == 1` => `p\' = 1 + p` and `q\' = q-1`\n\t \n     Here is the example that shows\n\t* \t number of 1s to the left is increasing:\n\t* \t number of 1s to the right is decreasing\n\n    and hence both above are binary searchable.\n ![image](https://assets.leetcode.com/users/images/8e4b7b59-3b0b-49f9-8594-65aabe53c1c4_1609389306.657918.png)\n\n    Now, we need to find the ***last* 0 that number of 1s to the left** of it is **less** than\n\t**number of 1s to the right of it**, let\'s call it **midZero** .\n\tFrom the **left** to **midZero** all 0s need to bubble left.\n\tFrom **midZero + 1** to **right** all 0s need to bubble right.\n\t\n\tObviously we need to keep track of #1s to the left and #1s to the right in a prefix sum.\n\tAlso we keep a prefix sum for accumulative left and right cost.\n\t\n\tHere is my Swift implementation:\n\t\n\t\n```\nclass Solution {\n    func minMoves(_ nums: [Int], _ k: Int) -> Int {\n        var numberOfOnesToTheLeftOf = [Int](repeating: 0, count: nums.count)\n        var numberOfOnesToTheRightOf = [Int](repeating: 0, count: nums.count)\n        var costLeft = [Int](repeating: 0, count: nums.count)\n        var costRight = [Int](repeating: 0, count: nums.count)\n        \n        for i in stride(from: 1, to: numberOfOnesToTheLeftOf.count, by: 1) {\n            \n            numberOfOnesToTheLeftOf[i] = numberOfOnesToTheLeftOf[i-1] + (nums[i-1] == 1 ? 1 : 0)\n            //cumulative cost of swaps to the left of this element\n            costLeft[i] = costLeft[i-1] + (nums[i] == 0 ? numberOfOnesToTheLeftOf[i] : 0)\n            \n            \n            let j = nums.count-i-1\n            numberOfOnesToTheRightOf[j] = numberOfOnesToTheRightOf[j+1]  + (nums[j+1] == 1 ? 1 : 0)\n            //cumulative cost of swaps to the right of this element\n            costRight[j] = costRight[j+1] + (nums[j] == 0 ? numberOfOnesToTheRightOf[j] : 0)\n        }\n        \n        /*\n         queue tracks how many 0s are in this window,\n         as we increment left counter, dequeue from this queue if we see any 0\n         as we increment right counter, we enqueue if we see any 0\n         */\n        \n        var q = [[Int]]()\n        var left = 0, right = 0, sum = 0, res = Int.max\n        while right < nums.count {\n            if nums[right] == 1 {\n                sum += 1\n            } else {\n                q.append([costLeft[right],\n                          costRight[right],\n                          numberOfOnesToTheLeftOf[right],\n                          numberOfOnesToTheRightOf[right]\n                ])\n            }\n            guard sum == k else {\n                right += 1\n                continue\n            }\n            while left <= right && nums[left] == 0 {\n                q.removeFirst()\n                left += 1\n            }\n            if sum == k {\n                /**\n                 do a binary search to find the last 0 in this window\n                 that #of 1s on it\'s left side is less than #of 1s on it\'s right side.\n                 */\n                var low = 0, high = q.count-1\n                while low <= high {\n                    let mid = low + (high-low)/2\n                    let lo = q[mid][2] - numberOfOnesToTheLeftOf[left], ro = q[mid][3] - numberOfOnesToTheRightOf[right]\n                    if lo >= ro {\n                        high = mid - 1\n                    } else {\n                        low = mid + 1\n                    }\n                }\n                \n                \n                var l = 0, r = 0\n                if high >= 0 {\n                    /**\n                     cumulative left cost of midZero - cost that\'s added to the 0s from left to midZero by 1s from index 0 to left pointer of the window - cost of 0s that are NOT in the window and are on the left side of the window\n                     */\n                    l = q[high][0] - (high + 1) * numberOfOnesToTheLeftOf[left] - costLeft[left]\n                }\n                if high + 1 < q.count {\n                    /**\n                     cumulative right cost of (midZero + 1) - cost that\'s added to the zeros from (midZero+1) to right by 1s from index right pointer of the window to array.size() - cost of 0s that are NOT in the window and are on the right side of the window\n                     */\n                    r = q[high+1][1] - (q.count - (high + 1)) * numberOfOnesToTheRightOf[right] - costRight[right]\n                }\n                \n                res = min(res, l + r)\n                right += 1\n                sum -= 1\n                \n                left += 1\n            }\n        }\n        return res\n    }\n}\n```\n\nLet me know if you have any question, and hope it helps.\n
['Binary Search', 'Sliding Window']