Show problems as
Classic problem #2134MediumArraySliding Window

Minimum Swaps to Group All 1's Together II

Real-world version: Group the Red Discs on the Carousel
Tracked in this browser only
Read Minimum Swaps to Group All 1's Together II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A carousel carries trays in a circle. discs lists the trays in the order they come round, starting from tray 0, and the tray after the last one is tray 0 again. discs[i] is 1 when tray i carries a red disc and 0 when it carries a blue disc.

One swap takes the discs in any two trays and exchanges them. The two trays do not have to be next to each other.

The red discs are grouped when the trays carrying them form one unbroken run around the circle. Such a run is allowed to pass the last tray and continue from tray 0, and a run of no trays or of a single tray counts as unbroken.

Return the fewest swaps that leave the red discs grouped.

Examples

Example 1

Input
discs = [1, 1, 0, 0, 0, 1, 1, 1]
Output
0

The five red discs already sit on trays 5, 6, 7, 0 and 1, an unbroken run that passes the last tray and continues from tray 0, so no swap is needed.

Example 2

Input
discs = [1, 0, 0, 1, 0, 1, 0, 0, 1, 1]
Output
2

Swap the discs on trays 6 and 0, then swap the discs on trays 7 and 3. The five red discs then sit on trays 5, 6, 7, 8 and 9, an unbroken run.

Example 3

Input
discs = [1, 0, 1, 0, 1]
Output
1

Swap the disc on tray 2 with the disc on tray 3. The red discs then sit on trays 3, 4 and 0, an unbroken run that passes the last tray.

Constraints

  • 1 <= discs.length <= 10^5
  • discs[i] is either 0 or 1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_swaps(discs: list[int]) -> int:
Java
public int fewestSwaps(int[] discs)

More on the same topics