[Java] Non-Prefix Sum Solution + Explanation
There are two parts to solving this problem. First part is that you need realize for any window size of k of all 1s, the minimum moves aka the greedy approach w
There are two parts to solving this problem. First part is that you need realize for any window size of k of all 1s, the minimum moves aka the greedy approach would be to move them all towards the middle, the median. Now, you don\'t have to move them all to the middle per say; you only have to move them to their right positions in a sequential fashion with the middle element being the median. To do this, you first move them all the middle and then remove the extra steps at the end. Second part is the sliding window distance sum to the median problem. As we move from one median to another, we take out the distance to old element and add the distance to the new element. Then, we add (new_median - old_median) steps to the first halve of the window because we need to move them forward. Then, we remove (new_median - old_median) steps from the second halve of the window because we also need to move them forward. Then, we would have our result, which the minimum sum among all possibilities minus the extra steps.\n```\nclass Solution {\n    public int minMoves(int[] nums, int k) {\n        List<Integer> pos = new ArrayList<>();\n        int sum = 0;\n        for (int i = 0; i < nums.length; i++) {\n            if (nums[i] == 1) {\n                pos.add(i);\n            }\n        }\n        for (int i = 0; i < k; i++) {\n            sum += Math.abs(pos.get(k / 2) - pos.get(i));\n        }\n        int res = sum;\n        for (int i = 0; i + k < pos.size(); i++) {\n            int mid = i + k / 2;\n            sum -= pos.get(mid) - pos.get(i);\n            sum += pos.get(i + k) - pos.get(mid + 1);\n            sum += (k / 2) * (pos.get(mid + 1) - pos.get(mid));\n            sum -= (k - k / 2 - 1) * (pos.get(mid + 1) - pos.get(mid));\n            res = Math.min(res, sum);\n        }\n        int extra = k % 2 == 1 ? (k / 2 + 1) * (k / 2) : (k / 2 + 1) * (k / 2) / 2 + (k / 2) * (k / 2 - 1) / 2;\n        return res - extra;\n    }\n}\n```
[]