Java | Sliding Window | T.C O(N) single traversal | No prefix Array
Approach -\n1. Save the indices of all 1\'s in a separate List (list).\n2. Use sliding window of size k. For first window from 0 to k-1 index. Find mid and then
**Approach** -\n1. Save the indices of all 1\'s in a separate List (list).\n2. Use sliding window of size k. For first window from 0 to k-1 index. Find mid and then Let Le = number of elements on left of mid and Re = number of element on right of mid inside the window only. Le and Re will be fixed for all the elements. Calculate cost for every element in Left and Right of mid in window.\n3. To calculate cost, cost() is used to move an index to other index in the list.\n4. Now, Fill L and R for all the elements on left and right of mid for first window and save (L+R) it in minCost.\n5. Start with loop from i = 1 upto i<=n-k, where n = list.size();\n6. New mid is prevMid + 1, as we can notice that mid value is increasing by 1 for each window.\n7. We have to update L and R for current window to calculate the cost for this window.\n8. Calculate L and R as mentioned in code. and let cost = L + R\n9. Compare this cost with minCost.\n10. Return minCost.\n\n**Why we are taking mid of sliding window?**\nRefer - https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/discuss/988056/Python-O(n)-Sliding-Window-with-detailed-explanation\n\nT.C is O(N) with single traversal and S.C is O(N).\n\n\n```\nclass Solution {\n    private List<Integer> list;\n    public int minMoves(int[] nums, int k) {\n        // Base case - \n        if(nums.length == k) return 0;\n        int Le = 0, Re = 0, mid, L = 0, R = 0, cost, minCost = Integer.MAX_VALUE, j;\n        list = new ArrayList<>();\n        for(int i = 0; i<nums.length; ++i){\n            if(nums[i] == 1){\n                list.add(i);\n            }\n        }\n        // System.out.println(list.toString());\n        int n = list.size(), prevMid;\n        // Initialising sliding window\n        mid = 0 + ((k-1)-0)/2;\n        Le = mid; Re = k-mid-1;\n        for(int i = 0; i < mid; ++i){\n            L += (list.get(mid) - list.get(i)) - (mid-i);\n        }\n        for(int i = mid + 1; i < k; ++i){\n            R += (list.get(i) - list.get(mid)) - (i-mid);\n        }\n        minCost = L + R;\n        // System.out.printf("L:%d, R:%d, mid:%d, minCost:%d, Le:%d, Re:%d\\n\\n", L, R,  mid, minCost, Le, Re);\n        for(int i = 1; i <= n-k; ++i){\n            j = i + k - 1;\n            prevMid = mid;\n            mid = mid + 1;\n            /*\n            L is cost of moving all 1\'s from index i-1 to prevNode. But now, we need to change it for current window. \n            So, for L we need to remove the cost of 1 for moving from(i-1)th index to left prevNode which is equal to -cost(i-1, pervMid).\n            And as mid changed from prevMid to current mid. So, for all the elements on left of mid i.e. Le must be shifted from prevMid to mid which\n            has cost of Le * (prevMid, mid).\n            */\n            L = L - cost(i-1, prevMid) + Le * cost(prevMid, mid);\n            /*\n            Similary, we need to update R for current window. Prevously, R is cost of moving Re elements or 1\'s on right of prevMid to prevMid. \n            So, to update it for current mid, we have to decrease Re * cost(prevMid, mid) from it and also we have to add cost of new element \n            j which is added to the right of current window. As we are moving to right of mid. So, we have to add cost(mid, j) to R\n            */\n            R = R - Re * cost(prevMid, mid) + cost(mid, j);\n            cost = L + R;\n            minCost = (int)Math.min(cost, minCost);\n            // System.out.printf("i:%d, j:%d, L:%d, R:%d, prevMid:%d, mid:%d, cost:%d\\n", i, j, L, R, prevMid, mid, cost);\n        }\n        return minCost;\n    }\n    \n    /*\n    i < j\n    Suppose the list is like \n    indices  0  1  2\n    list    [0, 2, 5]\n    Let mid is at index 1, So, element at index 0 have to be moved to index 1 to get consecutive ones on left of mid.\n    So, cost of moving 1 from index 0 to left of index of mid which is 2 is list.get(j) - list.get(i) - (j-i), where i = 0 and j = 1\n    */\n    private int cost(int i, int j){\n        return list.get(j) - list.get(i) - (j-i);\n    }\n}\n```
[]