[Java/C++] Two pointers with Prefix Sums
First, notice that in order to move a 1 towards another position, the amount of moves required is just the number of 0\'s that you pass.\n\nThen, notice that if
First, notice that in order to move a 1 towards another position, the amount of moves required is just the number of 0\'s that you pass.\n\nThen, notice that if you want to group k consecutive ones together, you can always keep at least one \'1\' in the same position, and moves other 1\'s around it towards this \'1\'.\nEx. 1001. \nIf you want to group 2 together, choosing to group them as 0110 is the same as grouping them as 1100 (kept left 1 at the same position).\n\nUsing these two observations, you only need to keep track of two things: the positions of the 1\'s, and how many 0\'s a \'1\' could pass if it were to move to another position. \n\nFor the latter, just use prefix sums. For the former, you can use two pointers. \n\nFirst, let me define what I mean by \'center\'.\nThis means the \'1\' at this position stays at the same place, everything else moves towards this \'1\')\nEx. 10110101. If I want k=4, and I center at index 2, the end result will be 01111001, because the \'1\' at index 2 did not change positions. If I center at index 7, then the result will be 10001111, meaning the \'1\' at index 7 does not change position.\n\nThe idea is that if we were to center everything at one position, we could have a \'right\' pointer and a \'left\' pointer (right - left + 1 = k). This range, from left to right, defines all of the 1\'s that I want to currently make consecutive.\n\nThen, you can just perform normal two pointers.\nNote the edge case in my code "if (right == i && right+1 < n)". This is because, the right and left pointers define the range I want to make consecutive, and therefore must include the point I am centering all the 1\'s to!\n\nJava\n```\npublic static int minMoves(int[] nums, int k) {\n        ArrayList<Integer> ones = new ArrayList<>();\n        for (int i=0; i<nums.length; i++) {\n        \tif (nums[i] == 1) ones.add(i);\n        }\n        int[] zeroespref = new int[nums.length];\n        for (int i=0; i<nums.length; i++) {\n        \tif (i == 0) {\n        \t\tzeroespref[0] = (nums[0] == 0 ? 1 : 0);\n        \t}\n        \telse {\n        \t\tzeroespref[i] = zeroespref[i-1] + (nums[i] == 0 ? 1 : 0);\n        \t}\n        }\n        \n        int n = ones.size();\n        int right=k-1;\n        int left=0;\n        int mindist = 0;\n        \n        \t// centered at 0\n        for (int i=0; i<k; i++) {\n        \tmindist += zeroespref[ones.get(i)] - zeroespref[ones.get(0)];\n        }\n        \n        int curdist = mindist;\n        \n        \t// centered at i\n        for (int i=1; i<n; i++) {\n        \tint zeroeschange = zeroespref[ones.get(i)] - zeroespref[ones.get(i-1)];\n        \tcurdist += (i - left)*zeroeschange;\n        \tcurdist -= (right - i + 1)*zeroeschange;\n        \t\n        \twhile (right+1<n) {\n        \t\tint zeroesleft = zeroespref[ones.get(i)] - zeroespref[ones.get(left)];\n        \t\tint zeroesright = zeroespref[ones.get(right+1)] - zeroespref[ones.get(i)];\n        \t\tif (zeroesright < zeroesleft) {\n        \t\t\tcurdist -= zeroesleft;\n        \t\t\tcurdist += zeroesright;\n            \t\tright++;\n            \t\tleft++;\n        \t\t}\n        \t\telse break;\n        \t}\n        \tmindist = Math.min(mindist, curdist);\n        \t\n        \tif (right == i && right+1 < n) {\n        \t\tint zeroesleft = zeroespref[ones.get(i)] - zeroespref[ones.get(left)];\n        \t\tint zeroesright = zeroespref[ones.get(right+1)] - zeroespref[ones.get(i)];\n    \t\t\tcurdist -= zeroesleft;\n    \t\t\tcurdist += zeroesright;\n        \t\tright++;\n        \t\tleft++;\n        \t}\n        }\n        \n        return mindist;\n        \n    }\n```\n\nC++\n```\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int k) {\n        vector<int> ones;\n        for (int i=0; i<nums.size(); i++) {\n        \tif (nums[i] == 1) ones.push_back(i);\n        }\n        long zeroespref[nums.size()];\n        for (int i=0; i<nums.size(); i++) {\n        \tif (i == 0) {\n        \t\tzeroespref[0] = (nums[0] == 0 ? 1 : 0);\n        \t}\n        \telse {\n        \t\tzeroespref[i] = zeroespref[i-1] + (nums[i] == 0 ? 1 : 0);\n        \t}\n        }\n        \n        int n = ones.size();\n        int right=k-1;\n        int left=0;\n        long mindist = 0;\n        \n        \t// centered at 0\n        for (int i=0; i<k; i++) {\n        \tmindist += zeroespref[ones[i]] - zeroespref[ones[0]];\n        }\n        \n        long curdist = mindist;\n        \n        \t// centered at i\n        for (int i=1; i<n; i++) {\n        \tlong zeroeschange = zeroespref[ones[i]] - zeroespref[ones[i-1]];\n        \tcurdist += (i - left)*zeroeschange;\n        \tcurdist -= (right - i + 1)*zeroeschange;\n        \t\n        \twhile (right+1<n) {\n        \t\tlong zeroesleft = zeroespref[ones[i]] - zeroespref[ones[left]];\n        \t\tlong zeroesright = zeroespref[ones[right+1]] - zeroespref[ones[i]];\n        \t\tif (zeroesright < zeroesleft) {\n        \t\t\tcurdist -= zeroesleft;\n        \t\t\tcurdist += zeroesright;\n            \t\tright++;\n            \t\tleft++;\n        \t\t}\n        \t\telse break;\n        \t}\n        \tmindist = min(mindist, curdist);\n        \t\n        \tif (right == i && right+1 < n) {\n        \t\tlong zeroesleft = zeroespref[ones[i]] - zeroespref[ones[left]];\n        \t\tlong zeroesright = zeroespref[ones[right+1]] - zeroespref[ones[i]];\n    \t\t\tcurdist -= zeroesleft;\n    \t\t\tcurdist += zeroesright;\n        \t\tright++;\n        \t\tleft++;\n        \t}\n        }\n        \n        return mindist;\n    }\n};\n```
['Two Pointers', 'C', 'Prefix Sum', 'Java']