[Python] Simple Sliding window approach + Pointers - Detailed explanation ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nThis question can be reformulated as find the closest k points (points being indices of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis question can be reformulated as find the closest k points (points being indices of the array where the associated value is 1) from my current position on a 1-D line, and return the cumulative distance between my current point and each of the closest k neighbors.\n\nThe maxChanges does not add much, just adapts the number k to k- maxChanges, (also we need to remember to add 2 * maxChanges to the score).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nOk, so we have a line that starts at O and ends at len(nums1) - 1, points are indices i where the value of nums[i] is one.\n\nWhat we want is the following, find the closest k points to my current position i and sum their distance to my current point, here the approach is testing all possible points.\n\nFirst, we create an array that gives us all the position where there is a 1 in the nums array, and call it **ones_index**.\nFor instance :\n[0,0,1,0,1] => [2,4]\n\nWe start with i = 0, we need to take the k first points (ignoring the maxChanges), and our number of moves becomes  sum(ones_indes[:k])\n\nThe hard part now, is to infer the score of the next index in O(1) time, for that we need two steps :\n1. infer the score(since we moved index) based on the last score we had using the same elements as the last score\n2. probe to take new elements from the right if they are available, and have become closer to our current index than the elements we have on the left\n\nWhat do we need to store for this?\n- **left** : pointer for the furthest element on the left\n- **left_number** : number of elements that are on the left\n- **right** : pointer for the furthest element on the right\n\nHow do we do it ??\n\n**For 1 : inferring the new score based on the last score**\n\nWe need to remember how many elements from the left we took, then as we move right, the score increases by one for each element we took on the left\nscore += nb_left (we keep nb_left in memory)\n\nAlso the score is decreased for each element we took on the right, since they become closer\nscore -= nb_rigt (we don\'t want to keep number right in memory, so it becomes)\nscore -= k - nb_left\n\nFinally, if the current index is a 1, we consider this element we take to move from the right to the left\nif nums[i] == 1:\n    nb_left += 1\n\n**For 2 : probing elements to the right**\nThis part is easy, it\'s replacing elements from the left with elements from the right, while it decreases our current score.\n\nThe condidition is a bit tricky but after trial and error, it\'s not so hard to get right with trial and error, to replace an element from the left with one from the right, you need:\n- nb_left > 0 : there are elements on the left to replace\n- right + 1 (represents next element on the right) is in bounds (there is a next element on the right)\n- the next element on the right is closer than the furthest element on the left, i.e. i - ones_index[left] >= ones_indes[right+1] - i\n\nIf so, we do the following:\n- decrease nb_left (nb_right is inferred so no need to do anything for that)\n- increment left pointer, meaning that the last index we used on the left is bigger now\n- increment right pointer, meaning that the last index we used on the right is bigger now\n- adapt score\n\n**Appendix What about maxChanges**\nWell, really there are 2 possible cases:\n- we need to use all maxChanges, in which case it\'s the same as above with just k - maxChanges instead of just k\n- we need only some maxChanges, in this case notice that you only need to consider points that are at a distance of at most 1 from the current position ; this can be done separately in O(1)\n\nSo here what we do is the following:\n- Try to fulfill the condition only by using closeNeighbors + maxChanges, if it works great you can consider that as a potential best score (use only some maxChanges case)\n- If not, just use all maxChanges, and do the above strategy by adapting k to k- maxChanges (use all maxChanges case)\n\n\n\n# Complexity\n- Time complexity:\nO(n) at each step the computation is at most O(1) (in the ones_array we only move to the right)\n\n- Space complexity:\nO(n) we need to store the ones_array, the rest is pointers\n\n# Code\n```\nimport numpy as np\nfrom typing import List\n\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        \n        res = np.inf\n        n = len(nums)\n        ones_index = [i for i in range(n) if nums[i] == 1]\n\n        def integrateCloseNeighborsAndMaxMoves(ind):\n            score = 0\n            moves = 0\n            if nums[ind] == 1:\n                score += 1\n\n            if ind - 1 >= 0 and nums[ind-1] == 1 and score <k:\n                moves += 1\n                score += 1\n            if ind + 1 < n and nums[ind+1] == 1 and score <k:\n                moves += 1\n                score +=1\n            \n            if score < k and maxChanges > 0:\n                diff = min(k - score, maxChanges)\n                score += diff \n                moves += 2 * diff\n\n            return (score, moves)\n        \n        def compute_nearest_neighbors(ind, left, nb_left, right, score):\n\n            if needed <= 0:\n                return (0,0,0,0)\n\n            if ind == 0:\n                nb_left = 1 if nums[ind] == 1 else 0\n                left = 0 if nums[ind] == 1 else -1\n                right = needed  - 1\n                score = sum(ones_index[:needed])\n\n            else:\n                score += nb_left\n                score -= needed - nb_left\n\n                if nums[ind] == 1:\n                    nb_left += 1\n                    if left == -1:\n                        left = 0\n\n                while nb_left > 0 and right + 1 < len(ones_index) and ind-ones_index[left] >= ones_index[right + 1] - ind:\n                    score -= ind-ones_index[left]\n                    left += 1\n                    nb_left -= 1\n                    score += ones_index[right + 1] - ind\n                    right += 1\n\n            return (left, nb_left, right, score)\n        \n        left, nb_left, right, score = None, None, None, None\n        needed = k - maxChanges\n        for i in range(n):\n            \n            #situation everything works with close points\n            s,m = integrateCloseNeighborsAndMaxMoves(i)\n            if s >= k:\n                res = min(res, m)\n            \n            #situation need to fetch closest k - maxMoves neighbors\n            m = 2 * maxChanges\n            left, nb_left, right, score = compute_nearest_neighbors(i, left, nb_left, right, score)                \n            m += score\n\n            res = min(res, m)\n            \n        return res\n\n```
['Python3']