Greedy | Prefix Sum + Sliding window | Linear time and space
Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n\nclass Solution {\n  public int minMoves(int[] nums, int k) {\n    if (k == 1) {\n
# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\n  public int minMoves(int[] nums, int k) {\n    if (k == 1) {\n      return 0;\n    }\n\n    List<Integer> gaps = new ArrayList<>();\n\n    int prev = -1, i = 0;\n\n    while (i < nums.length) {\n      if (nums[i] == 1) {\n        if (prev == -1) {\n          gaps.add(0);\n        } else {\n          gaps.add(gaps.get(gaps.size() - 1) + (i - prev - 1));\n        }\n        prev = i;\n      }\n      i++;\n    }\n\n    int minimumMoves = Integer.MAX_VALUE;\n    int j = 0;\n    i = 0;\n    int countMoves = 0;\n    while (j < gaps.size() - 1) {\n      if (j < k - 1) {\n        countMoves += (gaps.get(j + 1) - gaps.get(j)) * Math.min(j + 1, k - j - 1);\n        j++;\n        if (j == k - 1) {\n          minimumMoves = Math.min(minimumMoves, countMoves);\n        }\n        continue;\n      }\n\n      int deltaL = gaps.get(i + k / 2) - gaps.get(i);\n      int deltaR = gaps.get(j + 1) - gaps.get(j + 1 - k / 2);\n      countMoves += deltaR - deltaL;\n\n      minimumMoves = Math.min(minimumMoves, countMoves);\n      i++;\n      j++;\n    }\n\n    return minimumMoves;\n  }\n}\n```
['Greedy', 'Sliding Window', 'Prefix Sum', 'Java']