sliding window, counting the zeros
Having seen other submissions, it may have been faster to work with the indexes of each one in the given array. I decided to go by how many zeros needed to be j
Having seen other submissions, it may have been faster to work with the indexes of each one in the given array. I decided to go by how many zeros needed to be jumped to get the ones into the middle of a sliding window containing k ones. I made an array listing the number of zeros between ones, ie: an array containing the size of the (possibly zero) gaps between ones.\n\nFor k ones, we need to consider k-1 gaps. That made k <= 2 rather easy.\nThen I found visualising k odd not too bad. The tricky part was when k is even and so we have an odd number of gaps to consider. Left of the middle and right of the middle are different sizes.\n\nAs the window slides, the number of jumps changes in a way that can be measured by taking a bit from the start and adding a bit to the end. I may add a demo calculation if I have time, but I worked it out on paper and don\'t want to type it now. :)\n```\nconst sum = (arr, start, finish) => {\n    let out = 0;\n    let i = start;\n    while (i <= finish) { out += arr[i]; i++ }\n    return out\n}\n\nconst minMoves = (nums, k) => {\n    if (k === 1) { return 0 }\n    const gaps = [];\n    // console.log(nums.join(\'\'))\n    let i = 0;\n    // never want to jump past the zeros at the front\n    while (nums[i] === 0) { i++ }\n    // now i points to the first one, start measuring gaps from next element\n    i++;\n    let zeros = 0\n    while (i < nums.length) {\n        if (nums[i] === 0) {\n            zeros++\n        } else {\n            gaps.push(zeros)\n            zeros = 0\n        }\n        i++\n    }\n    // console.log(\'gaps:\', gaps);\n    // we need to consider k-1 gaps at a time\n    if (k === 2) { return Math.min(...gaps) }\n    let left = 0, mid = Math.floor((k - 1) / 2), right = k - 2;\n    i = 0;\n    let cur = 0;\n    while (i < mid) {cur += sum(gaps, i, mid-1); i++}\n    while (i <= right) {cur += sum(gaps, mid, i); i++}\n    let best = cur;\n    // console.log(\'first way to groups ones takes\', cur, \'steps\')\n    let rollingSum = 0, s = 0;\n    if (k%2 === 0) {mid++}\n    while (s < mid) { rollingSum += gaps[s]; s++ }\n    let groupedSum = [rollingSum];\n    while (s < gaps.length) {\n        rollingSum += gaps[s] - gaps[s-mid]\n        groupedSum.push(rollingSum);\n        s++\n    }\n    console.log(groupedSum)\n    right = k%2 ? mid+1 : mid;\n    while (right < groupedSum.length) {\n        cur += groupedSum[right] - groupedSum[left];\n        left++; right++;\n        // console.log(cur)\n        best = Math.min(best, cur)\n    }\n    return best\n}\n```
[]