1188HardArrayDynamic ProgrammingStackGreedyMonotonic Stack

Nudging a Bank of Sliders into Place

Tracked in this browser only

Trains the technique from

LeetCode 3229Minimum Operations to Make Array Equal to Target

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 mixing desk carries a row of sliders. levels[i] is the notch the i-th slider sits on and wanted[i] is the notch it should sit on.

In one gang move you pick a run of neighbouring sliders and either raise every slider in that run by one notch or lower every slider in that run by one notch. A run may be a single slider.

Return the fewest gang moves that bring every slider onto the notch it should sit on.

Examples

Example 1

Input: levels = [2, 2, 2], wanted = [3, 4, 3]
Output: 2

The shortfalls are one, two and one notch, all upward. One move raises all three sliders and a second raises the middle slider alone.

Example 2

Input: levels = [4, 1], wanted = [1, 4]
Output: 6

The first slider has to drop three notches and the second has to climb three, and no run serves both directions, so each is worked on its own.

Example 3

Input: levels = [1, 1, 1], wanted = [2, 1, 2]
Output: 2

The middle slider is already in place, which splits the row. A run covering all three would push it off its notch, so the outer two are raised separately.

Constraints

1 <= levels.length <= 10^5
levels.length == wanted.length
1 <= levels[i] <= 10^8
1 <= wanted[i] <= 10^8

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(levels: list[int], wanted: list[int]) -> int:

Java

public long minimumOperations(int[] levels, int[] wanted)

The intended approach

Time O(n) for the single sweep.Space O(1) beyond the input.

Only the shortfall of each slider matters: `gap[i] = wanted[i] - levels[i]`, the notches it still has to travel and the direction it has to travel them. A gang move covers a run, so think of the shortfalls as a profile to be built out of runs. A raising move can only ever help sliders with a positive shortfall, and a lowering move only sliders with a negative one, so a useful run never straddles two sliders that want opposite directions, nor a slider that is already in place. That cuts the row into blocks of sliders that all want the same direction, and the blocks are settled independently. Inside a block, read the shortfall magnitudes as a skyline to be built out of horizontal runs, one notch tall. Walking the block, a slider needing more than its left neighbour has to start fresh runs for the extra notches, while a slider needing the same or less can be served by runs already passing over it, which just stop earlier. So the block's cost is its first magnitude plus every rise from one slider to the next, and the whole answer is that sum over the blocks: the first slider of a block counts as rising from zero. One sweep does it. The tally reaches the length of the row times the largest shortfall, which overflows a 32-bit integer, so it wants a wide type.

Pythonentry point: minimum_operations

def minimum_operations(levels, wanted):
    total = 0
    before = 0
    for i in range(len(levels)):
        gap = wanted[i] - levels[i]
        if gap > 0:
            if before > 0:
                if gap > before:
                    total += gap - before
            else:
                total += gap
        elif gap < 0:
            if before < 0:
                if gap < before:
                    total += before - gap
            else:
                total += -gap
        before = gap
    return total

The obvious version

Search over the layers instead of reasoning about blocks. Let `up[i]` be how many raising runs pass over slider `i`; then the lowering runs passing over it are forced to be `up[i] - gap[i]`, and both counts have to be at least zero. Any pair of such profiles can be cut into runs, and the fewest runs realising a profile is the sum of its rises, counting the first slider as a rise from zero. So run a table over the sliders whose state is `up[i]`, charging the rises in both profiles at each step, and take the cheapest ending state. The range tried for `up[i]` goes a few above the largest shortfall, which leaves room for cancelling layers rather than assuming they never pay.

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(levels, wanted):
    n = len(levels)
    gaps = [wanted[i] - levels[i] for i in range(n)]
    top = 0
    for gap in gaps:
        if abs(gap) > top:
            top = abs(gap)
    cap = top + 3
    best = {}
    for up in range(cap + 1):
        down = up - gaps[0]
        if down < 0:
            continue
        best[up] = up + down
    for i in range(1, n):
        step = {}
        for up, cost in best.items():
            down = up - gaps[i - 1]
            for nup in range(cap + 1):
                ndown = nup - gaps[i]
                if ndown < 0:
                    continue
                extra = 0
                if nup > up:
                    extra += nup - up
                if ndown > down:
                    extra += ndown - down
                if nup not in step or cost + extra < step[nup]:
                    step[nup] = cost + extra
        best = step
    answer = -1
    for cost in best.values():
        if answer < 0 or cost < answer:
            answer = cost
    return answer

How this problem was checked

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