No median, just count steps (faster than 98%)
I like those median based solutions. Short and sweet code.\n\nBut I went with a different approach - just moving a point from left to right and adjusting 4 numb
I like those median based solutions. Short and sweet code.\n\nBut I went with a different approach - just moving a point from left to right and adjusting 4 numbers. No need to proof correctness or anything.\n\n```\nclass Solution {\n    /*\n    We will find an optimal point, where half of ones will be to the left (leftLen),\n    and the rest to the right (rightLen).\n    In case k is not even, right part will take the extra element.\n    Now we will be moving the point from left to right and counting how many\n    shifts we need to make to get leftLen of ones to be to the left of the point\n    and rightLen to the right.\n    The idea is that when we move the point, we can reuse the data we already know\n    to make sure we don\'t overcalculate the same stuff on and on.\n    For example: X00101 - to move boths points (rightLen = 2) to X, we need 2+3 moves.\n    This is easy to calculate by finding ones and substructing indexes. Now let\'s move\n    X to the right: X00101. We could use indexes again - or just take see that every one\n    became one step close -> if I take previous steps and remove rightLen, then I have the answer.\n    Similar logic applies to the left part - every move every of leftLen moves away.\n    The only catch is if we move past one. If one migrates from right part to left part, then:\n    - we need to remove the leftest one used (as we have to use only leftLen of ones)\n    - we need to add another one to the right, as we just gave it away\n    - as soon as we don\'t have enough ones to the right, we are done\n    */\n    public int minMoves(int[] nums, int k) {\n        if (k == 1) return 0;\n        final int leftLen = k/2;\n        final int rightLen = k-leftLen;// this will cover both odd and even k\n        int divider = 0; // this is the magic point, it represent the first element of right subset\n        // it is pretty clear, that it has to be set right after leftLen of ones is read\n        int onesSoFar = 0;\n        for (int i = 0; i < nums.length; i++) {\n            if (nums[i] == 1) {\n                onesSoFar++;\n            }\n            if (onesSoFar == leftLen) {\n                divider = i+1;\n                break;\n            }\n        }\n        /*\n        No for both left and right we need to get inital sums of steps\n        Also we track the most left index of one, and same for most right used so far.\n        Later, when the divider point moves over one, we will move left index to the next one,\n        and same for right.\n        */\n        int leftSum = 0;\n        int rightSum = 0;\n        int positionToFill = divider - 1;\n        /*\n        Clearly we need to track which position we want one to move to.\n        If divider is at index 10. The 3 ones (if k is 6 or 7) need to move to 7,8,9\n        Which we fill starting from divider and to the left.\n        Mirrir logic applies to the right.\n        */\n        int leftestOnePointer = -1;\n        int rightestOnePointer = 0;\n        for (int i = divider - 1; i >= 0; i--) {\n            if (nums[i] == 1) {\n                leftestOnePointer = i;\n                leftSum += positionToFill - i;\n                positionToFill--;\n            }\n        }\n        positionToFill = divider;\n        int consumedOnes = 0;\n        for (int i = divider; (i < nums.length)&&(consumedOnes < rightLen); i++) {\n            if (nums[i] == 1) {\n                rightestOnePointer = i;\n                rightSum += i - positionToFill;\n                positionToFill++;\n                consumedOnes++;\n            }\n        }\n        /*\n        This is the moment when we have intial data.\n        We know that to move leftLen of ones to divider - it takes leftSum of steps.\n        And same for right part.\n        */\n        int result = leftSum + rightSum;\n        while (divider < nums.length - rightLen) {\n            // move divider right\n            divider++;\n            if (nums[divider-1] == 0) {\n                /*\n                Simplest case, divider moved past zero:\n                1 0 0 0 1\n                    ^\n                All ones to the left became one step away: 1*left\n                All ones to the right became one step close: 1*rightLen\n                */\n                leftSum += leftLen;\n                rightSum -= rightLen;\n                result = Math.min(result, leftSum + rightSum);\n            } else {\n                /*\n                The "main" case. One migrates from right to left.\n                */\n                leftSum += leftLen;\n                /*\n                we need to remove extra steps, as we don;t use the leftest one any more\n                The new one is already at a good position, it contributes nothing\n                */\n                leftSum -= (divider - leftestOnePointer - 1);\n                leftestOnePointer++;\n                // and move left to the next one we are using\n                while (nums[leftestOnePointer] != 1) leftestOnePointer++;\n                /*\n                Now we need to find next available one to replace the one we just gave away\n                */\n                rightestOnePointer += 1;\n                while (rightestOnePointer < nums.length && nums[rightestOnePointer] != 1) {\n                    rightestOnePointer++;\n                }\n                if (rightestOnePointer == nums.length) {\n                    // happens if no more ones\n                    break;\n                }\n                rightSum += rightestOnePointer - divider - rightLen + 1;\n                result = Math.min(result, leftSum + rightSum);\n            }\n        }\n        return result;\n    }\n}\n```
['Java']