Treat 1s as point-like particles and 0s as space
Intuition\nMy first thought was to use a tree, aiming for logarithmic time. It kind of worked, but it was challenging to deal with the boundaries between partit
# Intuition\nMy first thought was to use a tree, aiming for logarithmic time. It kind of worked, but it was challenging to deal with the boundaries between partitions. Then I tried using run-length encoding to simplify the logic of calculating the number of moves for a span (window). Unfortunately the encoding made it difficult to _slide_ the window, but I noticed that runs of 0s looked like distances, while the 1s moved like particles \u2014 which led me to the solution below.\n\n# Approach\nThis approach treats the 1s as point-like particles and the 0s as spaces between them.\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 identical, 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```
['Sliding Window', 'Prefix Sum', 'Python3']