Fewest Swaps to Gather the Ones
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
0 <= len(bits) <= 100- each item of
bitsis 0 or 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Two pointers problems
- Find All Anagrams in a StringMedium
- Fruit Into BasketsMedium
- Longest Complete Vowel StretchMedium
- Longest Ones After Deleting OneMedium
- Longest Palindromic SubstringMedium
- Longest Repeating Character ReplacementMedium
- Longest Stretch With No Letter ThriceMedium
- Longest Substring Without Repeating CharactersMedium