1088MediumArrayHash TableGreedyCounting

Fewest Changes to Make the Strip Alternate

Tracked in this browser only

Trains the technique from

LeetCode 2170Minimum Operations to Make the Array Alternating

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 strip of positive readings reads readings. The strip alternates when every two readings that sit two places apart are equal and no two neighbouring readings are equal. A strip of one reading alternates already.

One change replaces a single reading with any positive whole number. Return the fewest changes that leave the strip alternating.

Examples

Example 1

Input: readings = [2, 1, 2, 1]
Output: 0

The strip already alternates: the even positions all read two, the odd ones all read one, and the two differ.

Example 2

Input: readings = [1, 1, 1, 1]
Output: 2

Both sides want to read one, but they must differ, so one side has to change every one of its two readings.

Example 3

Input: readings = [5, 5]
Output: 1

The two readings are equal and sit next to each other, so one of them has to change.

Constraints

1 <= readings.length <= 10^5
1 <= readings[i] <= 10^5

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 minimum_operations(readings: list[int]) -> int:

Java

public int minimumOperations(int[] readings)

The intended approach

Time O(n) over the strip's length.Space O(d) for the tallies over distinct readings.

An alternating strip is settled by two readings: the one filling every even position and the one filling every odd position, and those two have to differ. So the job is to choose that pair to leave as many readings untouched as possible. Tally the readings at the even positions and at the odd positions separately, and note for each side the two readings appearing most often. If the commonest on the two sides differ, take both: nothing can beat keeping the most on each side. If they are the same reading, the two sides cannot both take it, so one side must settle for its runner-up. Try both ways round, keeping the better, and the answer is the strip's length less however many readings were kept. A side with no runner-up is handled by treating its runner-up as keeping nothing, since a fresh reading nobody holds is always available.

Pythonentry point: minimum_operations

def minimum_operations(readings):
    n = len(readings)
    if n == 1:
        return 0
    def top_two(values):
        tally = {}
        for value in values:
            tally[value] = tally.get(value, 0) + 1
        first = (-1, 0)
        second = (-2, 0)
        for value in tally:
            count = tally[value]
            if count > first[1]:
                second = first
                first = (value, count)
            elif count > second[1]:
                second = (value, count)
        return first, second
    even_first, even_second = top_two(readings[0::2])
    odd_first, odd_second = top_two(readings[1::2])
    if even_first[0] != odd_first[0]:
        return n - even_first[1] - odd_first[1]
    one = even_first[1] + odd_second[1]
    two = even_second[1] + odd_first[1]
    return n - (one if one > two else two)

The obvious version

Try every pair of readings the strip might settle on. Only the readings already present are worth trying, plus one value nobody holds to stand for a fresh reading, since all fresh readings are alike. For each pair that differs, count how many positions would have to change, and keep the smallest count. Costs the distinct readings squared times the strip's length rather than a pair of tallies.

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_minimum_operations(readings):
    n = len(readings)
    if n == 1:
        return 0
    choices = set(readings)
    choices.add(0)
    best = None
    for even in choices:
        for odd in choices:
            if even == odd:
                continue
            changes = 0
            for at in range(n):
                want = even if at % 2 == 0 else odd
                if readings[at] != want:
                    changes += 1
            if best is None or changes < best:
                best = changes
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 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