0428MediumArraySliding Window

Alternating Windows on the Carousel

Tracked in this browser only

Trains the technique from

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 fairground carousel has cushions bolted all the way round its rim, numbered 0 upward in the direction it turns. The rim closes on itself, so the last cushion sits right beside cushion 0. cushions[i] is 0 when cushion i is plain and 1 when it is striped.

A window is k cushions taken in turning order from some starting cushion, carrying on past the last cushion and round to cushion 0 whenever it has to. Every cushion starts one window, so the rim has exactly cushions.length windows and two windows are different whenever they start at different cushions.

A window is alternating when no two cushions that sit side by side inside it carry the same pattern.

Return how many of the rim's windows are alternating.

Examples

Example 1

Input: cushions = [0, 1, 0, 1], k = 3
Output: 4

Patterns swap at every step all the way round, including across the seam between the last cushion and cushion 0, so each of the four windows of three has no matching neighbours inside it.

Example 2

Input: cushions = [0, 1, 0, 0, 1, 1], k = 3
Output: 2

The window starting at cushion 0 reads plain, striped, plain. The window starting at cushion 5 runs striped, plain, striped by carrying on past the seam. Every other window contains a matching pair.

Example 3

Input: cushions = [0, 0, 0], k = 3
Output: 0

Every cushion is plain, so any two side by side match and no window qualifies.

Example 4

Input: cushions = [0, 1, 0, 1], k = 4
Output: 4

Each window now covers the whole rim from a different starting cushion, and all four of them alternate throughout.

Example 5

Input: cushions = [0, 1, 0], k = 3
Output: 1

The rim has an odd number of cushions, so the last cushion and cushion 0 are both plain. Only the window that starts at cushion 0 avoids having those two side by side.

Constraints

3 <= cushions.length <= 10^5
0 <= cushions[i] <= 1
3 <= k <= cushions.length

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 number_of_alternating_groups(cushions: list[int], k: int) -> int:

Java

public int numberOfAlternatingGroups(int[] cushions, int k)

The intended approach

Time O(n + k) for a rim of n cushions: one pass of n + k - 2 steps with constant work each.Space O(1): two counters, nothing built from the input.

Keep one number as the rim is walked: how many cushions the alternating stretch ending at the cushion just reached is long. Stepping onto a cushion whose pattern matches the one behind it starts that stretch over at 1, otherwise the stretch grows by one, and a stretch of at least k means the window finishing here is alternating. The walk covers the whole rim and then k - 2 cushions past the seam, which is exactly enough for the windows that straddle it, with positions taken modulo the rim size.

Pythonentry point: number_of_alternating_groups

def number_of_alternating_groups(cushions, k):
    # Walk once round the rim and then k - 2 cushions past the seam, carrying the
    # length of the alternating stretch that ends at the cushion just stepped on.
    # Whenever that stretch is at least k long, the run finishing there is one of
    # the answers. Wrapping is handled by taking positions modulo the rim size.
    size = len(cushions)
    stretch = 1
    found = 0
    for step in range(1, size + k - 1):
        if cushions[step % size] == cushions[(step - 1) % size]:
            stretch = 1
        else:
            stretch += 1
        if stretch >= k:
            found += 1
    return found

The obvious version

Take every starting cushion in turn and check that window's k - 1 side-by-side pairs one at a time, counting the windows that survive. O(n * k).

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_number_of_alternating_groups(cushions, k):
    size = len(cushions)
    found = 0
    for start in range(size):
        good = True
        for offset in range(1, k):
            if cushions[(start + offset) % size] == cushions[(start + offset - 1) % size]:
                good = False
                break
        if good:
            found += 1
    return found

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
5 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