Treat 1s as particles of constant mass
Intuition\nMy first thought was to use a tree, aiming for O(log(n)). It kind of worked, but it was challenging to deal with the boundaries between partitions.\n
# Intuition\nMy first thought was to use a tree, aiming for $$O(log(n))$$. It kind of worked, but it was challenging to deal with the boundaries between partitions.\n\n# Approach\nThis approach treats the 1s as particles and the 0s as spaces between them Each particle (`1`) takes up no space.\n\nWe want to find the minimum total distance that is needed to move the particles to clump them together. The easiest way to satisfy that is to find the centre of mass and bring the particles on either side inwards.\n\n## Steps\n1. **Convert to particles.** Ultimately we only care about their positions, so accumulate the distances between them and then discard the gaps. This leaves us with a contiguous list of all particle positions, relative to the start of the list.\n2. **Number of moves:** Since it\'s contiguous we can just slide a fixed-width window over the list. For each span:\n    1. Find the centre of mass. Since the particles are all the same, this is simply the midpoint of the window.\n    2. Sum the distances of each particle from the centre of mass.\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```python\nimport numpy as np\n\n\nclass Solution:\n    def minMoves(self, nums: list[int], k: int) -> int:\n        particles = to_particles(nums)\n        min_moves = None\n        for i in range(len(particles)+1-k):\n            span = particles[i:i+k]\n            moves = count_moves(span)\n            if min_moves == None or moves < min_moves:\n                min_moves = moves\n            if moves == 0:\n                break\n        return min_moves\n\n\ndef count_moves(span) -> int:\n    center_coord = span[len(span) // 2]\n    relative_positions = np.abs(span - center_coord)\n    return np.sum(relative_positions)\n\n\ndef to_particles(nums: list[int]):\n    particles = np.array(nums)\n\n    # Add up spaces. Invert so that zeros are accumulated\n    coords = np.cumsum(1 - particles)\n\n    # Remove spaces and just keep particle positions\n    return coords[particles == 1]\n\n```
['Python3']