[C++ / Go] Sliding Window - O(n) time + O(m) space solution
Intuition\n### Choosing a Starting Position\n- Select a starting position which is already 1.\n=> Reduce target to k - 1.\n### Earning Point Ways\n- There are 2
# Intuition\n### Choosing a Starting Position\n- Select a starting position which is already `1`.\n=> Reduce target to k - 1.\n### Earning Point Ways\n- There are 2 ways to earn points:\n    - Use multiple **type 1 actions** to swap another `1` to current position.\n    => Cost equals distance between that `1` and the current position.\n    - Use a **type 2 action** to convert an adjacent elements to `1` and then use a **type 1 action** to swap to current position.\n    => Cost equals 2 actions and 1 change.\n### Type 2 actions is more optimal in most of cases.\n- Use most of **Type 2 Actions** for better cost:\n    - There are corner case that the two adjacent elements of current position is already `1`, so the cost just 1.\n    - Do not use more changes than the target.\n    => The number of used **type 2 actions** ranges from from `maxChanges - 2` to `maxChanges`\n### Gathering Remaining Ones:\n- The remaining `1` elements are collected from both sides of the starting position to minimize the overall cost.\n\n# Approach\n- Extract an array of all positions of `1`.\n- For each number of used type 2 actions, there are `r` remaining `1`s.\n    - Use a sliding window of size `r` in the new array.\n    - Gather `1` to middle of sliding window, calculate the cost efficiently using **prefix sum**, **suffix sum**\n    - Another cost is change cost.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {\n        vector<int> pos;\n        for (int i = 0; i < nums.size(); i++) {\n            if (nums[i] != 0) {\n                pos.push_back(i);\n            }\n        }\n\n        if (pos.empty())\n            return 2 * k;\n\n        if (k == 1)\n            return 0;\n\n        int m = pos.size();\n        vector<long long> prefixSum(m);\n        prefixSum[0] = pos[0];\n        for (int i = 1; i < m; i++)\n            prefixSum[i] = prefixSum[i - 1] + pos[i];\n\n        vector<long long> suffixSum(m);\n        suffixSum[m - 1] = 0;\n        for (int i = m - 2; i >= 0; i--)\n            suffixSum[i] = suffixSum[i + 1] + (pos[m - 1] - pos[i]);\n\n        long long res = LLONG_MAX;\n        maxChanges = min(maxChanges, k - 1);\n        for (int change = max(0, maxChanges - 2); change <= maxChanges; change++) {\n            int required = k - change;\n            long long changeCost = change * 2;\n\n            int l = 0;\n            int r = l + required - 1;\n            int mid = (l + r) / 2;\n            while (r < m) {\n                long long tmp = changeCost;\n                tmp += suffixSum[l] - suffixSum[mid] - (long long)(mid - l) * (pos[m - 1] - pos[mid]);\n                tmp += prefixSum[r] - prefixSum[mid] - (long long)(r - mid) * pos[mid];\n\n                res = min(res, tmp);\n\n                l++;\n                r++;\n                mid++;\n            }\n        }\n        return res;\n    }\n};\n```\n```Go []\nfunc minimumMoves(nums []int, k int, maxChanges int) int64 {\n    pos := make([]int, 0)\n\tfor i, num := range nums {\n\t\tif num != 0 {\n\t\t\tpos = append(pos, i)\n\t\t}\n\t}\n\n\tif len(pos) == 0 {\n\t\treturn int64(2 * k)\n\t}\n\n\tif k == 1 {\n\t\treturn int64(0)\n\t}\n\n    m := len(pos)\n\tprefixSum := make([]int64, m)\n\tprefixSum[0] = int64(pos[0])\n\tfor i := 1; i < m; i++ {\n\t\tprefixSum[i] = prefixSum[i - 1] + int64(pos[i])\n\t}\n\n\tsuffixSum := make([]int64, m)\n\tfor i := m - 2; i >= 0; i-- {\n\t\tsuffixSum[i] = suffixSum[i + 1] + int64(pos[m - 1] - pos[i])\n\t}\n\n    res := int64(math.MaxInt64)\n\tmaxChanges = min(maxChanges, k - 1)\n\tfor change := max(0, maxChanges - 2); change <= maxChanges; change++ {\n\t\trequired := k - change\n\t\tchangeCost := int64(change * 2)\n\n\t\tl := 0\n\t\tr := l + required - 1\n\t\tmid := (l + r) / 2\n\t\tfor r < m {\n\t\t\ttmp := changeCost\n\t\t\ttmp += suffixSum[l] - suffixSum[mid] - int64(mid - l) * int64(pos[m - 1] - pos[mid])\n\t\t\ttmp += prefixSum[r] - prefixSum[mid] - int64(r - mid) * int64(pos[mid])\n\n\t\t\tres = min64(res, tmp)\n\n\t\t\tl++\n\t\t\tr++\n\t\t\tmid++\n\t\t}\n\t}\n\treturn res\n}\n\nfunc min(x, y int) int {\n    if x < y {\n        return x\n    }\n    return y\n}\n\nfunc max(x, y int) int {\n    if x < y {\n        return y\n    }\n    return x\n}\n\nfunc min64(x, y int64) int64 {\n    if x < y {\n        return x\n    }\n    return y\n}\n```\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(m)$, `m` is number of `1` elements
['Sliding Window', 'C++', 'Go']