Fewest range increments to build a target array

Restate. An array starts as all zeros. One move picks a contiguous range and adds 1 to every element in it. Find the fewest moves that turn the zeros into target. Part 2 asks for the moves themselves.

Brute force (a good first answer). Do it level by level. While the array has any nonzero value, take every maximal run of positive values, count one move for each run, and subtract 1 from every value in it. This is correct, but it costs O(n · max(target)), which is too slow when the values are large. A recursive version ("subtract the range minimum, then split at the zeros") costs O(n²) in the worst case.

Key observation. Look at neighbours. Element i must be covered by exactly target[i] ranges. When you step from i-1 to i:

• If target[i] <= target[i-1], every range that i needs can be an extension of a range that already covers i-1. No new range has to start.
• If target[i] > target[i-1], at most target[i-1] ranges can continue from the left. The other target[i] - target[i-1] ranges must start at i.

Each move starts exactly once, so

answer = target[0] + sum(max(0, target[i] - target[i-1]) for i in 1..n-1)

This is a lower bound, because every rise forces that many new starts. It is also reachable: extend ranges greedily and close them when the values drop. So it is optimal. If you treat target[-1] as 0, the formula is simply the sum of the positive differences.

Building the moves (part 2). Sweep left to right and keep a stack of start indexes of open ranges. The stack size always equals the current height.

• When the height goes up, push i once for each unit of rise.
• When it goes down, pop once for each unit of drop, and close each popped range at i-1.
• At the end, close every range still open at n-1.

Invariant: after index i is processed, the stack holds exactly target[i] open ranges, and every one of them covers i. A drop closes the ranges that started most recently, which keeps the ranges properly nested. (Nesting is not required for correctness; it only makes the output tidy.)

from typing import List, Tuple


def min_moves(target: List[int]) -> int:
    """Fewest +1-on-a-subarray moves that turn zeros into target."""
    moves = 0
    prev = 0
    for value in target:
        if value < 0:
            raise ValueError("target values must be non-negative")
        if value > prev:
            moves += value - prev
        prev = value
    return moves


def optimal_moves(target: List[int]) -> List[Tuple[int, int]]:
    """Return one optimal list of inclusive (left, right) ranges."""
    result: List[Tuple[int, int]] = []
    open_starts: List[int] = []  # len(open_starts) == current height
    prev = 0
    for i, value in enumerate(target):
        if value < 0:
            raise ValueError("target values must be non-negative")
        if value > prev:
            open_starts.extend([i] * (value - prev))
        else:
            for _ in range(prev - value):
                result.append((open_starts.pop(), i - 1))
        prev = value
    while open_starts:
        result.append((open_starts.pop(), len(target) - 1))
    return result


def apply_moves(n: int, moves: List[Tuple[int, int]]) -> List[int]:
    """Check helper: replay moves with a difference array."""
    diff = [0] * (n + 1)
    for left, right in moves:
        diff[left] += 1
        diff[right + 1] -= 1
    out, running = [], 0
    for i in range(n):
        running += diff[i]
        out.append(running)
    return out


if __name__ == "__main__":
    cases = [
        ([1, 2, 3, 2, 1], 3),
        ([3, 1, 1, 2], 4),
        ([3, 1, 5, 4, 2], 7),
        ([0, 0, 0], 0),
        ([], 0),
        ([5], 5),
        ([2, 0, 2], 4),
        ([4, 4, 4], 4),
    ]
    for target, expected in cases:
        assert min_moves(target) == expected, (target, min_moves(target))
        moves = optimal_moves(target)
        assert len(moves) == expected
        assert apply_moves(len(target), moves) == target
    print("all tests pass")

• min_moves: O(n) time and O(1) extra space. It makes a single pass.
• optimal_moves: O(n + M) time, where M is the answer. It must output M ranges, so this is optimal for the output. The stack uses O(max(target)) space. To keep the stack O(n), store (start, count) pairs instead and pop counts in bulk. The output is still M ranges.
• Brute-force level sweep, for comparison: O(n · max(target)).

• [1, 2, 3, 2, 1] → 3. The ranges are (2,2), (1,3), (0,4).
• [3, 1, 1, 2] → 4. That is 3 at the start plus 1 for the rise at the end.
• [3, 1, 5, 4, 2] → 7. That is 3 + (5 − 1).
• [2, 0, 2] → 4. A zero splits the array, so no range can cross it.
• [4, 4, 4] → 4. Four full-length ranges.
• [0, 0, 0] → 0, and [] → 0. Both are edge cases with nothing to do.
• [5] → 5. A single element.
• A strictly decreasing array such as [5, 4, 3, 2, 1] → 5. Only the first element counts.
• Large values, such as [10**9, 1, 10**9] → 2·10**9 − 1. The count formula must not simulate. The move list really is that long, so in this case you return only the count.
• A negative value raises ValueError. Zeros plus increments can never reach it.

1. Both increments and decrements, from any starting array. Let d = target − start. Positive and negative runs are independent, and a sign change works like a zero. Per index, the cost is |d[i]| if the sign changes from d[i-1] (or d[i-1] is 0). Otherwise it is max(0, |d[i]| − |d[i-1]|). Still O(n).
2. Each move may add any amount k ≥ 1 to the range. Now only the number of distinct levels matters, not their size. Keep a stack whose values strictly increase from bottom to top. For each value, pop every entry that is greater than it. If the value is positive and differs from the new top, push it and count one move. [2, 1, 2] needs 3 moves, but [2, 3, 2] needs 2, because the two 2s share one range. Still O(n).
3. Point updates with queries. target[i] changes, and you must answer the minimum after each change. Keep S = sum(max(0, target[i] − target[i−1])) with target[−1] = 0. An update changes only the two terms that touch i, so each update is O(1).
4. Range-add updates with queries. Adding v to target[l..r] changes only the boundary differences at l and r+1. Store the difference array, and recompute those two max(0, ·) terms. Each update is O(1).
5. Circular array, or ranges with a maximum length L. In a circular array, rotate it so the scan starts at a global minimum. Then use the formula with prev = min, plus min itself. A length cap breaks the simple formula. A greedy approach works: sweep left to right, keep a queue of open ranges with their expiry index, and start new ranges when coverage falls short. That is an O(n) sliding-window greedy, and you must check feasibility, because a range cannot extend past L.

Mid-level (L4)

• Gets a working solution, even the level-by-level simulation, and then finds the neighbour-difference formula with a hint.
• Handles empty input, zeros and single elements, and states O(n) time and O(1) space.
• Writes a few asserts, ideally including replaying the moves.

Senior (L5)

• Reaches the formula without hints and argues both sides: rises force new starts (lower bound) and greedy extension reaches it (upper bound).
• Builds the actual move list with the stack invariant, and notes that output size, not n, is the true cost.
• Handles the increments-and-decrements follow-up and the point-update follow-up quickly.

Staff (L6+)

• Frames the problem in terms of difference arrays and explains why range-add updates touch only two terms. Connects this to the related cousin problems: rising water, and the minimum number of strokes for a skyline.
• Raises the gaps in the spec: whether input can be negative, whether moves or only the count are needed, overflow for huge values, and streaming input where only prev is kept.
• Reasons carefully about the variants where the formula breaks (variable step size, length caps), and suggests checking against a brute force rather than guessing.