C++ solution O(n + k)
\nclass Solution {\npublic:\n  int minMoves(vector<int>& nums, int k) {\n    // Print(nums);\n    if (k <= 1) return 0;\n    vector<int> min_moves_left = Calcul
```\nclass Solution {\npublic:\n  int minMoves(vector<int>& nums, int k) {\n    // Print(nums);\n    if (k <= 1) return 0;\n    vector<int> min_moves_left = CalculateMinMoves(nums, k / 2);\n    reverse(nums.begin(), nums.end());\n    vector<int> min_moves_right = CalculateMinMoves(nums, k - (k / 2));\n    reverse(min_moves_right.begin(), min_moves_right.end());\n    // Print(min_moves_left); Print(min_moves_right);\n    int64 best = INF;\n    for (int i = 0; i < nums.size() - 1; i++) {\n      int64 sum = (int64)min_moves_left[i] + min_moves_right[i + 1];\n      best = min(best, sum);\n    }\n    return best;\n  }\n\n  vector<int> CalculateMinMoves(vector<int>& nums, int k) {\n    vector<int> ans(nums.size(), INF);\n    deque<int> ones_pos; // max k size\n    int i = 0;\n    while (ones_pos.size() < k && i < nums.size()) {\n      if (nums[i] == 1) ones_pos.push_back(i);\n      i++;\n    }\n    i--;\n    if (i >= nums.size()) {\n      return ans;\n    }\n    ans[i] = MinMovesForIdx(k, i, ones_pos);\n    i++;\n    for (; i < nums.size(); i++) {\n      if (nums[i] == 0) {\n        ans[i] = ans[i - 1] + k;\n      } else {\n        int to = i - 1 - (k - 1);\n        int from = ones_pos.front();\n        ans[i] = ans[i - 1] - (to - from);\n        ones_pos.pop_front();\n        ones_pos.push_back(i);\n      }\n    }\n    return ans;   \n  }\nprivate:\n  int MinMovesForIdx(int k, int idx, deque<int> ones_pos) {\n    int ans = 0;\n    if (ones_pos.size() < k) return INF;\n    for (int i = 0; i < k; i++) {\n      ans += (idx - ones_pos.back() - i);\n      ones_pos.pop_back();\n    }\n    return ans;\n  }\n};\n```
[]