C++ | A Mathematical Explanation
Intuition\nThe first thing that comes to mind is the following subproblem:\n\nGiven 1\'s in indices a_1 < a_2 < \dots < a_k, what is the minimum number steps ne
# Intuition\nThe first thing that comes to mind is the following subproblem:\n\nGiven $$1$$\'s in indices $$a_1 < a_2 < \\dots < a_k$$, what is the minimum number steps needed to put them into the consecutive block $$x, x+1, \\dots, x+k-1$$ for a fixed $$x$$? To minimize the number of swaps, we greedily put the $1$ in position $a_1$ into position $x$ (which requires $|x - a_1|$ swaps), the $1$ in the position $a_2$ into position $x+1$ (requiring $|(x+1)-a_2|$ swaps), and so on. Therefore, the number of minimum swaps needed for this subproblem is $|x-a_1| + |(x+1)-a_2| + \\dots + |(x+k-1)-a_k|$ steps. We rewrite this functions as follows: \n\n$f(x) = |x-a_1| + |x-(a_2-1)| + \\dots + |x-(a_k - (k-1))|.$\n\nSince $a_1 < a_2 < \\dots < a_k$, therefore $a_1 \\le (a_2-1) \\le \\dots \\le a_k - (k-1)$. This is neat! We can just substitute $b_i = a_i - (i - 1)$ for each $i$, so now we want to minimize $f(x) = |x-b_1| + |x-b_2| + \\dots + |x-b_k|$ subject to $b_1 \\le b_2 \\dots \\le b_k$. This is a classic problem; in fact the minimum is attained when $x$ is located in the middle (i.e. $x = b_{\\lfloor \\frac{k+1}{2} \\rfloor}$), and the minimum value is sum of last half of $b_i$\'s minus sum of first half of $b_i$\'s. More formally, one can prove this fact by some triangle inequality (i.e. $|x-a| + |x-b| \\ge |a-b|$).\n\n# Approach\nNow we move to the original problem. We collect all indices in ```nums``` which has value of $1$, let\'s say $\\{i_1, i_2, \\dots i_m\\}$. Then we transform it, like what we did previously above, into $\\{i_1, i_2 - 1, i_3 - 2, \\dots, i_m - (m - 1)\\}$. Finally, we iterate over this new array for every window of length $k$; we find the sum of the last half minus sum of first half of the elements of the window. We can for example maintain the sum of the first half and the second half, which I did in the code below using the variable `ki` and `ka`, respectively.\n\n# Complexity\n- Time complexity:\n$O(n)$\n\n- Space complexity:\n$O(n)$\n\n# Code\n```\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int k) {\n        int n = nums.size();\n        int pos[n];\n        int sz = 0;\n        for (int i = 0; i < n; i++) {\n            if (nums[i] == 1) pos[sz++] = i;\n        }\n        for (int i = 0; i < sz; i++) {\n            pos[i] -= i;\n        }\n        int ki = 0, ka = 0;\n        for (int i = 0; i < k / 2; i++) ki += pos[i];\n        for (int i = k - 1; i >= k - (k / 2); i--) ka += pos[i];\n        int ans = INT_MAX;\n        for (int i = 0; i + k - 1 < sz; i++) {\n            ans = min(ans, ka - ki);\n            if (i + k < sz) {\n                ki -= pos[i];\n                ki += pos[i + k / 2];\n                ka -= pos[i + k - (k / 2)];\n                ka += pos[i + k];\n            }\n        }\n        return ans;\n    }\n};\n```
['Greedy', 'Sliding Window', 'C++']