0681MediumArraySliding Window

Group the Red Discs on the Carousel

Tracked in this browser only

Trains the technique from

LeetCode 2134Minimum Swaps to Group All 1's Together II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_swaps(discs: list[int]) -> int:

Java

public int fewestSwaps(int[] discs)

The intended approach

Time O(n): one pass to count the red discs and one pass round the circle.Space O(1).

Once the red discs are grouped they fill a run of trays exactly as wide as the number of red discs, so every candidate answer is one such run, and the swaps it needs is the number of blue discs inside it, since each of those trades with a red disc outside. Count the red discs, then slide a window of that width once round the circle, dropping the tray that leaves and adding the tray that enters with the index taken modulo the tray count. The answer is the red count minus the most red discs any window holds.

Pythonentry point: fewest_swaps

def fewest_swaps(discs):
    # slide a window as wide as the number of red discs once round the circle
    n = len(discs)
    reds = 0
    for v in discs:
        reds += v
    if reds == 0:
        return 0
    inside = 0
    for i in range(reds):
        inside += discs[i]
    best = inside
    for start in range(1, n):
        inside -= discs[start - 1]
        inside += discs[(start + reds - 1) % n]
        if inside > best:
            best = inside
    return reds - best

The obvious version

Count the red discs, then take each tray in turn as the first tray of a run that wide, stepping round the circle and counting the blue discs the run covers. The smallest count over all starting trays is the answer.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_swaps(discs):
    n = len(discs)
    reds = sum(discs)
    if reds == 0:
        return 0
    best = None
    for start in range(n):
        blues = 0
        for step in range(reds):
            if discs[(start + step) % n] == 0:
                blues += 1
        if best is None or blues < best:
            best = blues
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in