C++ O(n) solution with prefix sum and window with detailed explanation and example
Take [1,0,0,1,1,0,0,1,0,0,1], k=4 for example \nIdea:\n1. Find the indices of all 1s\n->[0,3,4,7,10])\n2. Calculate the total number of swaps with a sliding win
Take [1,0,0,1,1,0,0,1,0,0,1], k=4 for example \nIdea:\n1. Find the indices of all 1s\n->[0,3,4,7,10])\n2. Calculate the total number of swaps with a sliding window of length k\n->window 1: [0,3,4,7] and window 2: [3,4,7,10] (eg. k=4)\n3. Notice that aggregate all 1s to the median 1 will lead to the minimum distance\n->1st window: 3 and 4 are both medians, I choose the larger one\n->2nd window: 4 and 7 are both medians, I choose the larger one\n4. For each valid index, I aggregate all k/2 left 1s and (k-1)/2 right 1s\n->aggregate "1 at 0, 3, and 7" to "1 at 4" for the first window (eg. [0,3,4,7] to [2,3,4,5])\n->aggregate "1 at 3, 4, and 10" to "1 at 7" for the second window (eg. [3,4,7,10] to [5,6,7,8])\n5. Use the prefix sum to speed up the calculation for total number of swaps\n->[0,0,3,7,14,24]\n\nExample:\nFor the window [0,3,4,7]\n1.the number of swaps is (4-3-1)+(4-0-2)+(7-4-1), here (4-3-1)+(4-0-2) is to aggregate the left 1s, and (7-4-1) is to aggregate the right 1s\n2.for left 1s:\n->4 means total[i] in the code below (it is multiplied by k/2)\n->"0+3 to minus" is the sum of the indices of left 1s and it is calculated by prefix sum\n->"1+2" to minus is because we move 0 to 2 (instead of 4, so minus 2), and move 3 to 3 (instead of 4, so minus 1), it can be calculated with the formula n*(n+1)/2, where n is the number of 1s to aggregate\n\nNote:\nIf k is odd, I aggregate (k-1)/2 left 1s and (k-1)/2 right 1s to the median 1\nIf k is even, I aggregate k/2 left 1s and k/2-1 right 1s to the median 1\n->This can be summarized to aggregate k/2 left 1s and (k-1)/2 right 1s to the median 1 for all k\n```\nint minMoves(vector<int>& nums, int k) \n{\n\tlong result=2147483647;\n\tvector<int> total; //to store indices of all 1s\n\tfor(int i=0;i<nums.size();i++)\n\t\tif(nums[i]==1) total.push_back(i);\n\t\t\t\n\tint n=total.size();\n\tvector<long> s={0}; //to store the prefix sum of the indices of 1s\n\tfor(int i=0;i<n;i++)\n\t\ts.push_back(s.back()+total[i]);\n\n\tfor(int i=k/2;i<n-(k-1)/2;i++)\n\t{\n\t\tlong current=k/2*total[i]-(s[i]-s[i-k/2])-k/2*(k/2+1)/2; //calculate the distances to combine all left k/2 1s with the median value\n\t\tcurrent+=s[i+1+(k-1)/2]-s[i+1]-(k-1)/2*total[i]-(k-1)/2*((k-1)/2+1)/2; //to calculate the distances to combine all right (k-1)/2 1s with the median value\n\t\tresult=min(result,current);\n\t}\n\treturn result;\n}\n```
[]