Sliding Window | Prefix Sum O(n) Time Complexity
Intuition\n- We are going to use the sliding window along with mathematics involved in it.\n- We use prefix sum as well to compute cost.\n\n# Approach\n\n\n\n# 
# Intuition\n- We are going to use the sliding window along with mathematics involved in it.\n- We use prefix sum as well to compute cost.\n\n# Approach\n![image.png](https://assets.leetcode.com/users/images/789b1b19-a666-4425-ac37-67a4277e78ad_1731634197.653128.png)\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<int> index;\n        for(int i = 0;i < n;i++) {\n            if(nums[i]) {\n                index.push_back(i);\n            }\n        }\n        vector<long long> prefix;\n        long long sum = 0;\n        for(int i = 0;i < index.size();i++) {\n            sum += index[i];\n            prefix.push_back(sum);\n        }\n\n        long long ans = INT_MAX;\n        long long radius = (k & 1) ? k/2 : (k-2)/2;\n        //make a window of size k\n        //move the window\n        for(int i = 0,j = k-1;j < index.size();i++,j++) {\n            long long cost = 0;\n            if(k & 1) {\n                long long pivot = (i+j)/2;\n                long long right = prefix[j] - prefix[pivot];\n                long long left = (pivot > 0 ? prefix[pivot-1] : 0) - (i>0 ? prefix[i-1] : 0);\n                long long save = (radius+1)*radius;\n                cost = right - left - save;\n            }\n            else {\n                long long pivot = (i+j)/2;\n                long long right = prefix[j] - prefix[pivot];\n                long long left = (pivot > 0 ? prefix[pivot-1] : 0) - (i>0 ? prefix[i-1] : 0);\n                long long save = (radius+1)*radius + (radius+1);\n                cost = right - left - index[pivot] - save;\n            }\n            ans = min(ans,cost);\n        }\n        return ans;\n    }\n};\n```
['C++']