Simple | Beginner friendly ✅ | C++ | Sliding Window | Clean
Intuition\nThe first thought that should strike you is which operation is more optimal? The operation two is better because it guarantees a 1 in exactly 2 moves
# Intuition\nThe first thought that should strike you is which operation is more optimal? The operation two is better because it guarantees a 1 in exactly 2 moves, though exception is when the the alice index has adjacent ones, which will yield a 1 in merely a swap or 1 move, so how to decide which operation to use when?\nIn all other cases where distance to the neighbour 1 is >= 2, the second operation will cost >= 2\n\nSince there can only be 3 cases when operation 2 is better than operation 1 (when a 1 is present at i, i-1 or i+1), we will consider this case as edge case and use a check in the very beginning for the cases where k can be covered using adjacent ones and maxChanges only\n\nNow this first sub problem is easy, just iterate over nums and check if the adjacent ones + maxChanges can fullfill the requirement, if yes then return ans.\n\nAfter this, if we have not yet returned the ans, this means the k requirement can not be fullfilled using maxChanges and adjacent ones and thus now we also need to use the swap operations costing >= 2\n\n\nSince we are now sure about using maxChanges, the target ones which we require from operation 2 is reduced to $$target$$ = k - maxChanges.\n\nNow the second sub problem is we want to take a window with $$target$$ ones and select a optimal index in the window where we will aggregate all the ones, calculate the moves required for this aggregation over all such windows and return the minimum value found\n\nFor this take and array to store the indices of ones so that we can slide our fixed size window over this array\n\n# Approach\nAfter we have divided our problem into the sub-problems we need to code it out:\n1) Coding the fisrt sub problem to check the best cases where maxChanges and adjacent ones are enough is pretty straight forward we check adjacent elements for each element and check if the ones collected + maxChanges >= k or not\n\n2) Coding the second problem is also pretty simple once you are clear with the idea of which index in the window should be selected to get the minimum moves, The idea is simple just select the middle element of the window and if the window size is even then select any of the two middle indexes.\n\nOnce you are clear that we just need to choose the middle element for each window it is pretty simple, just use basic mathematics and come up with a formula to update the moves over a sliding window.\n\nThe formula i have used may look overwhelming at first look, but it is pretty simple, take an example where indices of ones are as\n$$2,3,4,5,6,7,8,9,10,$$ $$target = 8$$\nthe first window will be $$[2,3,4,5,6,7,8,9]$$\nand $$mid = (0+7)/2 = 3$$  --> $$5$$\nCalculate moves as (5-2) + (5-3) + (5-4) + (6-5) + (7-5) + (8-5) + (9-5)\n\nFor the next window $$[3,4,5,6,7,8,9,10]$$\n$$mid --> 6$$\nmoves: (6-3) + (6-4) + (6-5) + (7-6) + (8-6) + (9-6) + (10-6)\nNow observe carefully:\n1) The mid increases by one for next window\n2) We just have to replace all the prev mid\'s (5) with new mid(6) in the moves equation and add the excluded as well as new included element (2 and 10)\n\nThe second step is a bit tricky so i suggest using pen and paper to understand clearly\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    long long int minimumMoves(vector<int>& nums, int k, int maxChanges) {\n        int n = nums.size(); vector<int> ones;\n        long long ans = LONG_MAX;\n        bool flag = 0;\n        for(int i = 0; i < n; i++){\n            int curr = nums[i], moves = 0;\n            \n            //push the indices of ones in the array\n            if(  nums[i] )\n                ones.push_back(i);\n            \n            if( i > 0 && nums[i-1] == 1 && curr < k ){\n                moves++;\n                curr++;\n            }\n\n            if( i + 1 < n && nums[i+1] == 1 && curr < k ){\n                moves++;\n                curr++;\n            }\n\n            //check if our requirement can be fullfilled\n            if( curr + maxChanges >= k ){\n                flag = 1;\n                moves += ( k - curr )*2;\n                ans = min(ans, 1LL*moves);\n            }\n        }\n\n        if( flag )\n            return ans;\n\n        int rem = k - maxChanges, noOfOnes = ones.size(), l = 0, r = rem-1;\n\n        //since we are sure about using maxChanges initial moves = 2*maxChanges\n        long long currMoves = 2*maxChanges;\n\n        //calculate moves for the first window\n        for(int i = 0; i < rem; i++){\n            currMoves += abs(ones[r/2] - ones[i]);\n        }\n        \n        ans = min(ans, currMoves);\n        l++; r++;\n\n        //slide over all possible windows to find optimal\n        while( r < noOfOnes ){\n            int mid = (l+r)/2;\n            int curr = ones[mid], prev = ones[mid-1], lc = mid - l, rc = r - mid;\n            \n            //updating moves dynamically\n            currMoves = currMoves - curr*(rc-lc+1) + prev*(rc-lc-1) + ones[l-1] + ones[r];\n            ans = min(ans, currMoves);\n            l++; r++;\n        }\n        return ans;\n    \n    }\n};\n```\nPLEASE UPVOTE IF THE EXPLANATION WAS HELPFULL\u2705\n\n
['Sliding Window', 'C++']