FunctionRacerProblemsRace

Fewest Swaps to Gather the Ones

MediumTwo pointersPython, JavaScript, TypeScript, Java, C++

bits holds only 0s and 1s. In one swap you exchange the items at any two positions. Return the fewest swaps needed so that all the 1s end up in one contiguous block, which may sit anywhere in the list.

If the list has m ones, the final block is some window of exactly m positions, and filling a window costs one swap per 0 inside it. A list with no 1s, or whose 1s are already together, needs 0 swaps.

Example 1

bits [1,0,1,0,1]
returns 1

There are three 1s; the window [1, 0, 1] holds two of them, so one 0 must be swapped out.

Example 2

bits [0,0,0,1,0]
returns 0

The single 1 is already a block of its own.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Two pointers problems