🔥JAVA🔥 Easiest approach | Sliding window, prefix sum , explanation
\n# Approach\n- Save the indices of all 1\'s in a separate List (list).\n- Use sliding window of size k. For first window from 0 to k-1 index. - Find mid and th
\n# Approach\n- Save the indices of all 1\'s in a separate List (list).\n- 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.\n- To calculate cost, cost() is used to move an index to other index in the list.\n- 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.\n- Start with loop from i = 1 upto i<=n-k, where n = list.size();\n- New mid is prevMid + 1, as we can notice that mid value is increasing by 1 for each window.\n- We have to update L and R for current window to calculate the cost for this window.\n- Calculate L and R as mentioned in code. and let cost = L + R\n- Compare this cost with minCost.\n- Return minCost.\n\n# Code\n```\nclass Solution {\n    private List<Integer> list;\n    public int minMoves(int[] nums, int k) {\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        int n = list.size(), prevMid;\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        \n        for(int i = 1; i <= n-k; ++i){\n            j = i + k - 1;\n            prevMid = mid;\n            mid = mid + 1;\n            L = L - cost(i-1, prevMid) + Le * cost(prevMid, mid);\n\n            R = R - Re * cost(prevMid, mid) + cost(mid, j);\n            cost = L + R;\n            minCost = (int)Math.min(cost, minCost);\n        }\n        return minCost;\n    }\n    \n\n    private int cost(int i, int j){\n        return list.get(j) - list.get(i) - (j-i);\n    }\n}\n```
['Sliding Window', 'Prefix Sum', 'Java']