Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in one sentence

Start with an array of zeros. One operation chooses any contiguous subarray and raises every value in it by one; the goal is to build target in as few operations as possible.

For target = [1, 2, 3, 2, 1], three operations suffice: raise the whole array once, the middle three elements once, and the center element once more.

The constraints make direct simulation impractical. A value can be as large as $10^5$, and each operation changes its chosen interval by only one. The solution must count the necessary operations without performing them.

See the array as horizontal layers

Imagine target as a skyline made from unit-height blocks. A subarray increment paints one uninterrupted horizontal layer. While moving from left to right, a layer that already exists can continue across the next position at no additional cost. Only a rise in height forces new layers to begin.

The first position starts target[0] layers. At every later position i:

  • If target[i] <= target[i - 1], all required layers can be continued from the left, so no new operation is forced.
  • If target[i] > target[i - 1], exactly target[i] - target[i - 1] new layers must start at i.

Therefore the answer is

$$ \text{target}[0] + \sum_{i=1}^{n-1} \max(0, \text{target}[i] - \text{target}[i-1]). $$

For [3, 1, 5, 4, 2], the first height contributes 3, the rise from 1 to 5 contributes 4, and every other transition is flat or downward. The minimum is therefore 7.

Why counting rises is optimal

There are two parts to an optimality proof.

First, the formula is a lower bound. At index 0, each operation can add only one unit, so reaching target[0] requires at least target[0] operations. Whenever the height rises by $d$ between adjacent positions, those $d$ extra units at the right position cannot come from operations that also cover the left position: such operations would make the left side too tall. At least $d$ new intervals must begin there.

Second, the bound is achievable. Start exactly the required number of new layer-intervals at each rise. Continue each interval to the right for as long as that layer is still needed, ending intervals whenever the skyline falls. This constructs every column exactly and uses one operation for every term in the formula.

Because every valid construction needs at least that many operations and one construction uses exactly that many, the greedy count is optimal.

Python solution

class Solution:
    def minNumberOperations(self, target: list[int]) -> int:
        """Return the fewest subarray increments needed to build target."""
        if not target:
            return 0

        operation_count = target[0]

        for previous_height, current_height in zip(target, target[1:]):
            # Existing layers can continue across flat or falling edges.
            # A rise is the only place where new layer-intervals must begin.
            if current_height > previous_height:
                operation_count += current_height - previous_height

        return operation_count

The algorithm scans the array once, so it takes $O(n)$ time. It stores only the running count and two neighboring heights, so it uses $O(1)$ auxiliary space. It does not modify target.

A useful mental model

This problem looks as though it needs dynamic programming or a monotonic stack because each operation affects a range. The layer view collapses that global choice into a local question: how many layers begin at this boundary?

Falls do not add cost. They only tell some currently imagined intervals to stop. Rises add cost because no interval that covered the shorter previous column can create height above it without overshooting that column. This asymmetry is the reason the positive differences contain the entire answer.

Interview follow-ups

Can this be derived as a dynamic program?

Yes. Let dp[i] be the minimum number of operations needed to form the prefix ending at index i. The first state is dp[0] = target[0]. Extending a solution from i - 1 to i costs nothing when the new height is no greater, because existing layer-intervals can end as needed. When the new height is larger, the extension must start target[i] - target[i - 1] additional intervals.

Thus dp[i] = dp[i - 1] + max(0, target[i] - target[i - 1]). Since each state depends only on the previous value, the DP table compresses to the single running total used by the greedy solution. Both take $O(n)$ time, but the compressed form uses $O(1)$ space.

Why is a monotonic stack unnecessary?

A stack can track active height levels and determine when intervals end, but the problem asks only for the number of operations, not the intervals themselves. Every operation is counted exactly when its layer begins, and the number of beginnings at a boundary is simply the positive adjacent difference.

A stack therefore records more state than the answer requires. It can still be made to run in $O(n)$ time, but it uses $O(n)$ space in the worst case and has a more involved correctness argument.

How would the solution output an actual optimal sequence of intervals?

The count alone can be found in linear time, but explicitly returning one interval per operation may require output proportional to the answer. One construction starts target[i] - target[i - 1] intervals at every rise, treating the height before index 0 as zero. As the skyline falls, it closes the corresponding number of active intervals at the previous index.

A stack of interval start positions or grouped height levels can manage those active layers. The bookkeeping takes $O(n + A)$ time, where $A$ is the number of reported operations, and up to $O(n)$ compressed stack space. The output itself needs $O(A)$ space, which cannot be avoided if every interval must be listed.

What if every operation adds a fixed value greater than one?

Suppose each operation adds a fixed positive value step instead of one. The target is reachable only if every target value is divisible by step, because every array entry always remains a multiple of that value.

When it is reachable, divide every height by step and apply the same positive-difference formula to the scaled array. This normalization turns each fixed-size increment back into one unit layer. The feasibility check and count take $O(n)$ time and $O(1)$ auxiliary space if the scaled differences are computed on the fly.

What if decrements are also allowed?

Surprisingly, signed unit changes do not improve the minimum for a nonnegative target. Define a difference array with zero just outside both ends:

difference = [target[0], target[1] - target[0], ..., target[n - 1] - target[n - 2], -target[n - 1]].

An increment operation adds 1 at one difference boundary and -1 at another; a decrement does the reverse. Each operation can therefore eliminate at most one unit of positive boundary demand and one unit of negative demand. Because the differences sum to zero, at least half their total absolute value is required.

That lower bound equals the sum of positive differences, which is exactly the original greedy answer. The increment-only construction already attains it, so allowing decrements cannot reduce the operation count. Computing the bound still takes $O(n)$ time and $O(1)$ extra space.

Can the answer be updated after one target value changes?

Yes. The answer is the sum of local contributions max(0, target[i] - target[i - 1]) if a virtual target[-1] = 0 is used. Changing target[i] affects only the contribution at i and, when it exists, the contribution at i + 1.

Maintain the total answer and subtract those one or two old contributions before the update, then add their new values afterward. Each point update takes $O(1)$ time, and reading the current minimum also takes $O(1)$ time.

How would range updates and minimum-operation queries be supported?

For many range additions to target, store its difference array. Adding a value to [left, right] changes only the difference at left and the one after right. The answer is the sum of the positive difference values, so each range update changes at most two terms.

With direct access to those boundary differences, both the update and the answer query take $O(1)$ time. If the workload also needs arbitrary point or range queries on the target values, a Fenwick tree or segment tree can be added, with the precise complexity determined by those extra operations.

Takeaway

Count where work must begin, not every way intervals might be chosen. The first column starts its full height in layers, and each later rise starts only the additional layers that were not available from the left. That turns a range-operation problem into one pass over adjacent differences.