Minimum Number of Increments on Subarrays to Form a Target Array

hard monotonic stack array greedy

Problem

You start with an array initial of the same length as target, filled entirely with zeros. In one operation you pick any contiguous subarray of initial and add 1 to every element of it. Return the minimum number of such operations needed to turn initial into target.

Inputtarget = [1,2,3,2,1]

Output3

Add 1 over [0..4], then 1 over [1..3], then 1 at index 2.

Inputtarget = [3,1,1,2]

Output4

3 + max(0,1−3) + max(0,1−1) + max(0,2−1) = 3 + 0 + 0 + 1 = 4.

target (comma-separated, positive integers)

def min_number_operations(target):
    ops = target[0]
    for i in range(1, len(target)):
        if target[i] > target[i - 1]:
            ops += target[i] - target[i - 1]
    return ops

function minNumberOperations(target) {
  let ops = target[0];
  for (let i = 1; i < target.length; i++) {
    if (target[i] > target[i - 1]) {
      ops += target[i] - target[i - 1];
    }
  }
  return ops;
}

int minNumberOperations(int[] target) {
    int ops = target[0];
    for (int i = 1; i < target.length; i++) {
        if (target[i] > target[i - 1]) {
            ops += target[i] - target[i - 1];
        }
    }
    return ops;
}

int minNumberOperations(vector<int>& target) {
    int ops = target[0];
    for (int i = 1; i < (int)target.size(); i++) {
        if (target[i] > target[i - 1]) {
            ops += target[i] - target[i - 1];
        }
    }
    return ops;
}

Explanation

Think of target as a skyline of bars. Every operation paints a contiguous block of bars one unit taller. We want the fewest such horizontal strokes that build the skyline up from a flat floor of zeros.

Read the bars left to right. The very first bar must be raised from 0 to target[0], and the cheapest way is target[0] strokes that each begin at index 0. So the base cost is ops = target[0].

Now consider the boundary between bar i-1 and bar i. If bar i is shorter or equal, every stroke covering bar i can simply be the tail of a stroke that already covers bar i-1 — no new strokes are forced. But if bar i is taller, then target[i] - target[i-1] of its layers cannot be extensions of the previous bar's strokes, so they must start fresh here. That difference is the extra cost.

Summing those positive jumps gives the closed form ops = target[0] + Σ max(0, target[i] - target[i-1]). Descents are free; only climbs cost. A single left-to-right sweep computes the answer.

The connection to a monotonic stack: this is exactly the "largest rectangle / histogram filling" intuition where each rise pushes new work and each fall pops it off for free. Here we don't need to materialize the stack — the running difference captures the same accounting in O(1) space.

For target = [3,1,2,4,2,3] the climbs are at indices 2 (1→2, +1), 3 (2→4, +2) and 5 (2→3, +1), giving 3 + 1 + 2 + 1 = 7 operations.

Time: O(n) Space: O(1)