Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe want to move 1s at positions a0, a1 .. ak-1 to x, x+1 .. x+k-1 in the array.\n\nCost
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe want to move 1s at positions a0, a1 .. ak-1 to x, x+1 .. x+k-1 in the array.\n\nCost = |a0 - x| + |a1 - (x+1)| + ... + |ak-1 - (x + k-1)|\n\nrearranging\n\nCost = |a0 - x| + |(a1-1) - x| + ... + |(ak-1 - (k-1)) - x|\n\nThis is minimum when x is the median of a0, a1-1, a2-2 .. ak-1-(k-1)\n\nWhen we move the window to a1-1, a2-2, ... ak - k the cost becomes\n\nCost = |(a1-1) - x| + ... + |(ak-1 - (k-1)) - x| + |ak - k - x|\n\nSo we again want to find the median of a1-1, a2-2 .. ak-k. And this median element is exactly the next element after the median of the first window.\n\nSo we first find the positions of ones a0, a1 .. etc. and then convert this array into a0, a1-1, a2-2 .. so on. Then for every window of size k in this array we find the median array and calculate the cost. We only have to fully compute the first window cost. We also keep count of elements on the left and right side of the median element. Then for the next window, we lose the |a0-old_median| part of the cost. We also add left*(new_median - old_median) to the cost as the extra distance the left side has to move due to change in median from j to j+1 (it is like re-rooting). From the right, we gain |ak-k-new_median| part of the cost (w.r.t new median). We lose right*(new_median - old_median) as the distance the right side no longer has to move. Thus we get the cost for the new window in O(1)\n\nTC: O(n+k)\n\nhttps://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/988056/python-o-n-sliding-window-with-detailed-explanation/\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int k) {\n        vector<int> ones;\n\n        for(int i = 0; i<nums.size(); i++)\n        {\n            if(nums[i] == 1)\n            {\n                ones.push_back(i);\n            }\n        }\n\n        for(int i = 0; i<ones.size(); i++)\n        {\n            ones[i] = ones[i] - i;\n        }\n\n        int cost = 0;\n        int mincost = INT_MAX;\n\n        // use first and last to quickly add/subtract from cost\n        // and also to keep track of the index of the median loop\n        int first = 0;\n        int last = k-1;\n\n        int left = 0;\n        int right = 0;\n        int med = k/2;\n\n        for(int i = 0; i<k; i++)\n        {\n            if(i < k/2)\n            {\n                left++;\n            }\n            else if(i > k/2)\n            {\n                right++;\n            }\n\n            cost += abs(ones[i] - ones[med]);\n        }\n\n        mincost = min(mincost, cost);\n\n        // i is always the median position\n        for(int i = k/2+1; last+1<ones.size(); i++)\n        {\n            cost -= ones[i-1] - ones[first];\n            cost += left * (ones[i] - ones[i-1]);\n\n            first++;\n\n            cost += ones[last+1] - ones[i];\n            cost -= right * (ones[i] - ones[i-1]);\n\n            last++;\n\n            mincost = min(mincost, cost);\n        }\n\n        return mincost;\n    }\n};\n```
['C++']