Gap array, pitcher pouring
A gap array has the count of zeros between consecutive ones.\n\n10001 1001000001\nx 3 x0x2 x  5  x (replaced 1 with x, and 0 with their wedge count)\n\nSimplifi
A gap array has the count of zeros between consecutive ones.\n```\n10001 1001000001\nx 3 x0x2 x  5  x (replaced 1 with x, and 0 with their wedge count)\n\nSimplified: 3,0,2,5\n```\nStarting from left, the x-es need `3+0+2+5`, `0+2+5`,`2+5`,`5`  swaps to go to the right side.\nGrouping by gap frequencies the configuration cost is: `1*3 + 2*0 + 3*2 + 4*5`\nThe best cost is to move both outside x-es inwards repeatedly, getting: `1*3 + 2*0 + 2*2 + 1*5`\n\nFor additional gaps, a sliding window delta approach can be used to calculate the\nnew cost from the previous one.\n\nThe initial cost is composed of an equally long left and right range (left is one bigger, when k-1 is odd ):\n```\n3,0,2,5|4\np...q..|r\np is outgoing\nq is changing sides from right to left\nr is incoming\n```\n\n\n```\nclass Solution {\n    public int minMoves(int[] nums, int k) {\n        var gaps = new ArrayList<Integer>();\n        for(int i = 0, last = -1; i < nums.length; ++i){\n            if (nums[i] == 1){\n                if (last > -1){\n                    gaps.add(i-1-last);\n                }\n                last = i;\n            }\n        }\n        int lsum = 0, rsum = 0, wlsum = 0, wrsum = 0;\n        for(int i = k/2-1; i >= 0; --i){\n            lsum += gaps.get(i);//lsum = 3+0\n            wlsum += lsum;//wlsum = 1*3+2*0\n        }\n        for(int i = k/2; i < k-1; ++i){\n            rsum += gaps.get(i);//rsum = 2+5\n            wrsum += rsum;//wrsum = 2*2+1*5\n        }\n        int ans = wlsum+wrsum;\n        for(int p = 0, q = k/2, r = k-1; r < gaps.size(); ++p, ++q, ++r){\n            wlsum += (k/2)*gaps.get(q) - lsum;\n            lsum += gaps.get(q) - gaps.get(p);\n            \n            rsum += gaps.get(r) - gaps.get(q);\n            wrsum += rsum-((k-1)/2)*gaps.get(q);\n            \n            ans = Math.min(ans,wlsum+wrsum);\n        }\n        return ans;\n    }\n}\n```
['Greedy', 'Sliding Window', 'Java']