Minimum Increments on Subarrays to Form a Target Array: Greedy Stacking

You are given an integer array target. You start with an initial array of the same length filled with all zeros. In one operation, you can choose any subarray and increment each element by 1. Return the minimum number of operations needed to form target from the initial array.

This is LeetCode 1526: Minimum Number of Increments on Subarrays to Form a Target Array, a hard problem that looks like it needs dynamic programming or a monotonic stack, but actually collapses into a single greedy scan.

Why this problem matters

This problem teaches you to think about operations as layers. Each operation adds 1 to a contiguous subarray, so you can visualize the target as a stack of horizontal slabs. The question becomes: how many distinct slabs do you need?

That reframing turns a seemingly complex optimization into a one-pass scan. You only need a new operation when the "terrain" rises, because a rising bar cannot be covered by any existing operation that was already handling the previous (shorter) bar.

This same "count the increases" pattern shows up whenever you are stacking contiguous operations or counting the number of paint strokes needed to draw a histogram.

The brute force intuition

You could try to simulate the process: find the minimum value in the target array, subtract it everywhere (that many operations cover the whole array), then recurse on the remaining non-zero segments. This gives a divide-and-conquer approach, but it can degrade to O(n^2) in the worst case when the array is strictly increasing.

The key observation is that you do not actually need to recurse. You can compute the answer in a single left-to-right pass.

The key insight: count the upward steps

Think of building the target array from left to right. At each position, you need target[i] layers. If target[i] is greater than target[i-1], the extra target[i] - target[i-1] layers cannot be extensions of any existing operation, because those operations were only target[i-1] tall at the previous position. You need that many brand new operations.

If target[i] is less than or equal to target[i-1], you do not need any new operations. The existing operations can simply stop at this position (if target[i] is smaller) or continue (if equal).

The first element always needs target[0] operations to go from 0 to target[0].

So the answer is:

result = target[0] + sum of max(0, target[i] - target[i-1]) for i from 1 to n-1

Every time the bars go up, you need new operations. Every time they stay the same or go down, existing operations handle it.

Walking through it step by step

Let's trace through target = [1, 2, 3, 2, 1]. The answer is 3.

The first bar requires 1 operation. Each time the next bar is taller, we add the difference. When bars go down, no new operations are needed. The running total hits 3 and stays there.

The greedy solution

Here is the complete solution in Python:

def minNumberOperations(target: list[int]) -> int:
    result = target[0]
    for i in range(1, len(target)):
        if target[i] > target[i - 1]:
            result += target[i] - target[i - 1]
    return result

Here is what each piece does:

1. Initialize result = target[0]. The first bar needs exactly target[0] operations to go from 0 to its value.
2. Scan left to right (indices 1 through n-1). At each position, check if the current bar is taller than the previous one. If so, the difference target[i] - target[i - 1] is the number of new operations that must start here.
3. Return result.

That is the entire solution. No stack, no DP table, no recursion. Just one pass.

Why the greedy approach is correct

Consider two adjacent bars where target[i] > target[i-1]. The first target[i-1] layers at position i can be continuations of the operations that were active at position i-1. But the remaining target[i] - target[i-1] layers at position i must come from brand new operations, because at position i-1 there were only target[i-1] active operations.

Conversely, when target[i] is less than or equal to target[i-1], every layer at position i can be a continuation of some operation that was active at position i-1. No new operations are needed.

Since every new operation is accounted for exactly once (at the position where the height first rises), the total is exact and minimal.

Complexity analysis

You cannot do better than O(n) time because you need to inspect every element at least once. The O(1) space is optimal since you only need one variable beyond the input.

Building blocks

This problem is built on one core pattern that CodeBricks drills independently.

1. Greedy difference accumulation

The pattern of scanning an array and accumulating only the positive increments between consecutive elements:

result = arr[0]
for i in range(1, len(arr)):
    if arr[i] > arr[i - 1]:
        result += arr[i] - arr[i - 1]

This skeleton appears whenever you need to count the number of "new starts" across a sequence. In this problem, each positive difference represents new operations. In Candy, the left-to-right pass has a similar structure. In stock-buying problems, the sum of positive differences gives the maximum profit with unlimited transactions.

2. Layer stacking visualization

The idea that a set of contiguous subarray operations "stack" into horizontal layers. Visualizing the target as a stack of slabs clarifies why you only need to count upward steps. This mental model helps with problems like Trapping Rain Water (where you think about horizontal water layers) and Largest Rectangle in Histogram (where you think about horizontal rectangles).

Edge cases

Before submitting, make sure your solution handles these:

• Single element [5]: the loop does not execute. Answer is 5.
• Strictly increasing [1, 2, 3, 4]: every pair contributes. result = 1 + 1 + 1 + 1 = 4.
• Strictly decreasing [4, 3, 2, 1]: only target[0] contributes. Answer is 4.
• All equal [3, 3, 3]: no pair has an increase. Answer is 3 (just target[0]).
• Mountain shape [1, 3, 5, 3, 1]: result = 1 + 2 + 2 + 0 + 0 = 5. You need 5 operations.
• Valley shape [3, 1, 3]: result = 3 + 0 + 2 = 5. The drop to 1 does not add new ops, but climbing back to 3 does.

The single-pass solution handles all of these without special-case logic.

Common mistakes

1. Forgetting the first element. The result must start at target[0], not 0. Every layer in the first bar is a new operation with nothing to extend from.

2. Summing all differences, not just positive ones. When target[i] is less than target[i-1], the difference is negative. You should only add positive differences (or equivalently, only add when target[i] > target[i-1]).

3. Trying to use a monotonic stack. While you can solve this with a stack, it is unnecessary complexity. The one-pass greedy scan is simpler and equally efficient. If you find yourself building a stack, step back and check whether a direct scan works.

From understanding to recall

You have read the greedy solution and it makes sense. One loop, one condition, done. But can you write it from scratch in an interview without looking at it?

The details matter: initializing result to target[0], only adding positive differences, and understanding why drops do not contribute. These are small points, but under interview pressure they are easy to get wrong if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy difference accumulation from scratch at increasing intervals. After a few rounds, seeing "build target from subarray increments" immediately triggers the pattern.

The greedy difference accumulation pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Candy - Another greedy problem where you scan for increases and decreases to determine minimum values
• Trapping Rain Water - Layer-based thinking about bar charts, where horizontal slabs determine water levels
• Largest Rectangle in Histogram - Another histogram problem where you reason about contiguous horizontal spans

CodeBricks breaks LeetCode 1526 into its greedy difference accumulation building block, then drills it with spaced repetition. You type the solution from scratch until the pattern is automatic. When a greedy stacking question shows up in your interview, you do not think about it. You just write it.