Beats 100% runtime & memory using prefix sum and sliding window.
Intuition\n Describe your first thoughts on how to solve this problem. \nThere are 2 possible operations Dylan can do\n- op1: \n    - Set a y adjacent to dylanI
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere are 2 possible operations Dylan can do\n- op1: \n    - Set a y adjacent to `dylanIndex`, then swap to pick it.\n    - cost: 2\n- op2: \n    - For some y where nums[y] == 1, performing swaps toward the direction `dylanIndex` at until Dylan picks it.\n    - cost: distance from `dylanIndex` to y\n\nTo minimize the cost from op2, we can use a sliding window with a size of `ws` that covers all the ones we want through op2 and select the middle `1` of the window as the `dylanIndex`.\nThe minimum and maximum size of the sliding window should be\n```\nmin_ws = max(k - maxChanges, 0)\nmax_ws = min([k, min_ws + 3, len(prefix) - 1])\n```\nNoted that if `ws` > `min_ws+3`, we try to move some 1 too far away, and this operation should be replaced with op1.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIterate through all possible sliding windows, calculate the sum of distances between all ones and `dylanIndex`, and then complete the rest using op1.\nTo quickly calculate the sum of distances, we can make a prefix sum array for all indices of `1`.\n\n# Complexity\n![image.png](https://assets.leetcode.com/users/images/dafb7c32-eb52-463a-a4f1-d633f7854ca0_1710661447.2739258.png)\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        ans = inf\n        prefix = [0]\n        for i in range(len(nums)):\n            if nums[i] == 1:\n                prefix.append(prefix[-1] + i)\n        # case all zero\n        if len(prefix) == 1:\n            return k * 2\n        # numbers that must use op2\n        min_ws = max(k - maxChanges, 0)\n        # if ws > min_ws+3, the cost must be greater than 2 -> some op2 should be replace with op1\n        max_ws = min([k, min_ws + 3, len(prefix) - 1])\n        for ws in range(min_ws, max_ws + 1):\n            for start_idx in range(len(prefix) - ws):\n                end_idx = start_idx + ws\n                mid_left = (start_idx + end_idx) // 2\n                mid_right = (start_idx + end_idx + 1) // 2\n                # cost = min dis sum from start_idx to end_idx\n                cost = prefix[end_idx] - prefix[mid_left] - (prefix[mid_right] - prefix[start_idx])\n                # fill rest with op1\n                cost += (k - ws) * 2\n                ans = min(ans, cost)\n        return ans\n\n```
['Sliding Window', 'Prefix Sum', 'Python3']