Sliding Window, DP, C++ Solution with Intuition
Intuition\n1. If k <= maxChanges, if i-1, i, i+1 have 1 on it, it is best solution to use them first, because it cost only 0 or 1 move.  Then use operation 1 fo
# Intuition\n1. If k <= maxChanges, if i-1, i, i+1 have 1 on it, it is best solution to use them first, because it cost only 0 or 1 move.  Then use operation 1 for the rest, which cost 2 moves.\n2. If k > maxChanges, maxChanges is not enough we can\'t add new 1s, we need to move 1s to aliceIndex from the original array. we use (maxChanges-C) of operation 1, and find the minimum distance sum for every position to it\'s nearest k-(maxChanges-C) 1s.\nC could be 0~3 depends on number of 1 in position i-1, i, i+1, can try every possible C to find minimum cost.\n\n# Approach\n1. When k > maxChanges:\n   To find the minimum distance, use the sliding window to record \n   the nearest 1s, window size is fixed: k-(maxChanges-C). \n   l is the index of window\'s leftmost 1, nextR is the first 1 in   \n   the right of window\'s rightmost 1. Re-compute the distance sum  \n   when nextR is closer to current index then l\n2. When k <= maxChanges:\n   Use the 1 in i-1, i, i+1 first, then use operation 1 for the rest.\n\n# Complexity\n- Time complexity:\n  O(N)\n\n- Space complexity:\n  O(N)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> findMinMovesForXNearest(vector<int>& nums, int x) {\n        int l = 0, r = 0;\n        vector<long long> nearest(nums.size(), 0);\n        // find the leftmost 1\n        for (int i=0; i<nums.size(); i++) {\n            if (nums[i] == 1) {\n                l = i;\n                break;\n            } \n        }\n\n        // find the distance sum for index 0\n        long long moveSum = 0;\n        int cntOne = 0;\n        for (int i=l; i<nums.size(); i++) {\n            if (nums[i]==1) {\n                moveSum += i;\n                cntOne++;\n            }\n            if (cntOne == x) {\n                r = i;\n                break;\n            }\n        }\n\n        long long cntPass1 = 0;\n        int nextR = r+1;\n        // Find the new nextR\n        while(nextR<nums.size()) {\n            if (nums[nextR] == 1) {\n                break;\n            }\n            nextR++;\n        }\n        \n        nearest[0] = moveSum;\n        if (nums[0] == 1) cntPass1 = 1;\n        else cntPass1 = 0;\n        for (int i=1; i<nums.size(); i++) {\n            nearest[i] = nearest[i-1] + cntPass1 - (x-cntPass1);\n            // adjust the window, remove l add nextR if nextR is more close to i\n            if (nextR<nums.size() && abs(i-l) > abs(i-nextR)) {\n                int nextL = l + 1;\n                while(nextL<nums.size()) {\n                    if (nums[nextL] == 1) {\n                        break;\n                    }\n                    nextL++;\n                }\n\n                nearest[i] -= abs(i - l);\n                nearest[i] += abs(i - nextR);\n\n                if (l<i && nextR>i) {\n                    cntPass1 --;\n                }\n\n                // Find the next 1\n                nextR = nextR + 1;\n                while(nextR<nums.size()) {\n                    if (nums[nextR] == 1) {\n                        break;\n                    }\n                    nextR++;\n                }\n                l = nextL;\n            }\n\n            if (nums[i] == 1) {\n                cntPass1 ++;\n            } \n        }\n\n        return nearest;\n    }\n    \n    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {\n        long long res = LLONG_MAX;\n        map<int, vector<long long>> minStepsMap;\n        // zero 1\n        vector<vector<long long>> nearest(4);\n        if (k > maxChanges) {\n            for (int i=0; i<=3; i++) {\n                nearest[i] = findMinMovesForXNearest(nums, k-maxChanges+i);\n            }\n        }\n\n        int numOnes = 0;\n        for (auto &num: nums) {\n            if (num == 1) numOnes++;\n        }\n        \n        for (int i=0; i<nums.size(); i++) {\n            long long curSteps = 0;\n            if (k > maxChanges) {\n                int cnt1 = 0;\n                if (i>0 && nums[i-1]==1) cnt1++;\n                if (nums[i]==1) cnt1++;\n                if (i<nums.size()-1 && nums[i+1]==1) cnt1++;\n                int useNei = min(maxChanges, cnt1);\n                long long minSteps = LLONG_MAX;\n                // Try different C\n                for (long long un=0; un<=useNei; un++) {\n                    if (k-maxChanges+un > numOnes) continue;\n                    long long steps = 0;\n                    steps += (maxChanges - un)*2;\n                    steps += nearest[un][i];\n                    //cout << "steps " << steps << endl;\n                    minSteps = min(minSteps, steps);\n                }\n                curSteps = minSteps;\n\n            } else {\n                int needOnes = k;\n                if (nums[i]==1) {\n                    needOnes--;\n                }\n                if (needOnes==0) return 0;\n                if (i>0 && nums[i-1]==1) {\n                    needOnes--;\n                    curSteps ++;\n                }\n                if (needOnes==0) {\n                    res = min(res, curSteps);\n                    continue;\n                }\n                if (i<nums.size()-1 && nums[i+1]==1) {\n                    needOnes--;\n                    curSteps ++;\n                }\n                if (needOnes==0) {\n                    res = min(res, curSteps);\n                    continue;\n                }\n                curSteps += needOnes*2;\n            }\n\n            res = min(res, curSteps);\n        }\n\n        return res;\n    }\n};\n\n```
['Dynamic Programming', 'Greedy', 'Sliding Window', 'C++']