Show problems as
Classic problem #3229HardArrayDynamic ProgrammingStackGreedyMonotonic Stack

Minimum Operations to Make Array Equal to Target

Real-world version: Nudging a Bank of Sliders into Place
Tracked in this browser only
Read Minimum Operations to Make Array Equal to Target on LeetCode(opens in a new tab)

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

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

Python
def minimum_operations(levels: list[int], wanted: list[int]) -> int:
Java
public long minimumOperations(int[] levels, int[] wanted)

More on the same topics