LeetCode 1526 - Minimum Number of Increments on Subarrays to Form a Target Array

LeetCode Problem 1526

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Stack, Greedy, Monotonic Stack

Solution

Problem Understanding

The problem gives us a target array and asks us to build it starting from an array of all zeros. The only operation allowed is selecting any contiguous subarray and incrementing every element in that subarray by exactly one.

The goal is to determine the minimum number of such operations required to transform the zero array into the target array.

For example, if the target is [1,2,3,2,1], we can think of the array as a landscape of heights. Each operation adds one horizontal layer across some contiguous region. The challenge is to cover the landscape using the fewest layers possible.

The input consists of:

• An integer array target
• Each value represents the desired final height at that position

The output is:

• A single integer representing the minimum number of increment operations needed

The constraints are important:

• target.length can be as large as 100000
• Each target[i] can also be as large as 100000

These constraints immediately rule out expensive quadratic or cubic algorithms. We need an algorithm that runs in linear time or close to it.

An important observation is that every operation affects a contiguous segment. That means when heights increase from left to right, we need additional operations to create the extra height. However, when heights decrease, we do not need to remove anything because operations only add values. The previously created layers can simply stop extending.

Important edge cases include:

• Arrays with only one element
• Strictly increasing arrays
• Strictly decreasing arrays
• Flat arrays where all values are identical
• Large alternating rises and drops

The problem guarantees:

• Every value is positive
• The answer fits in a 32-bit integer
• The array is non-empty

These guarantees simplify implementation because we never need to handle negative numbers or empty input.

Approaches

Brute Force Approach

A brute-force strategy would try to simulate the actual operations.

One possible method is:

1. Find contiguous ranges where values are still below the target
2. Increment those ranges
3. Repeat until the constructed array matches the target

For example, with [1,2,3]:

• Increment [0..2]
• Increment [1..2]
• Increment [2..2]

This eventually works, but repeatedly scanning and modifying the array is extremely inefficient.

Another brute-force interpretation is recursively splitting intervals and trying to construct layers manually. This resembles painting problems where we repeatedly identify minimum heights and subtract layers.

While these approaches are logically correct, they become far too slow for arrays of size 100000.

Key Insight

The critical observation is that we only need new operations when the height increases compared to the previous position.

Suppose we process the array from left to right.

• If target[i] <= target[i-1], no extra operations are needed at position i
• If target[i] > target[i-1], we must start target[i] - target[i-1] new operations

Why?

Because operations can extend forward across contiguous regions. Any height already built at the previous index can continue into the current index for free. Only the additional height requires new operations.

This transforms the problem into a very simple greedy formula:

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

This works in linear time and constant extra space.

Although the problem lists monotonic stack as a topic, the greedy observation alone is sufficient and optimal.

Approaches Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × max(target)) or worse	O(n)	Simulates operations layer by layer
Optimal Greedy	O(n)	O(1)	Count only positive height increases

Algorithm Walkthrough

1. Initialize the answer with target[0].

The first element starts from zero, so we need exactly target[0] operations to build its height. 2. Traverse the array from index 1 to n - 1.

At each position, compare the current value with the previous value. 3. If target[i] > target[i - 1], add the difference to the answer.

This difference represents new layers that could not have been extended from the left side. 4. If target[i] <= target[i - 1], do nothing.

Existing operations from earlier positions can simply stop at the current point or continue through it. 5. Return the accumulated answer.

Why it works

Every increment operation creates one horizontal layer across some contiguous interval.

When moving from left to right:

• Any previously created layer can continue into the next position
• Therefore, previously existing height does not require new operations
• Only additional height above the previous position requires starting new intervals

By summing all positive increases, we count exactly the minimum number of new operations needed.

This greedy strategy is optimal because every extra unit of height increase must come from a newly started operation.

Python Solution

from typing import List

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        operations = target[0]

        for i in range(1, len(target)):
            if target[i] > target[i - 1]:
                operations += target[i] - target[i - 1]

        return operations

The implementation directly follows the greedy observation.

We initialize operations with the first element because the array starts from all zeros. Building the first column requires exactly that many operations.

Next, we iterate through the remaining elements.

Whenever the current height exceeds the previous height, we add the difference to the answer. This represents the number of newly started increment operations needed to achieve the additional height.

If the current height is smaller or equal, no new operations are required because existing layers can terminate naturally.

The algorithm uses only a single pass through the array and constant extra memory.

Go Solution

func minNumberOperations(target []int) int {
    operations := target[0]

    for i := 1; i < len(target); i++ {
        if target[i] > target[i-1] {
            operations += target[i] - target[i-1]
        }
    }

    return operations
}

The Go implementation mirrors the Python logic closely.

Go slices already provide efficient indexed access, so no additional data structures are needed.

Since the problem guarantees the answer fits within a 32-bit integer, using Go's default int type is sufficient.

Unlike Python, Go does not require explicit type imports or annotations for slices beyond the function signature.

Worked Examples

Example 1

Input:

target = [1,2,3,2,1]

Initial answer:

operations = 1

Traversal:

Index	Current	Previous	Increase	Operations
1	2	1	1	2
2	3	2	1	3
3	2	3	0	3
4	1	2	0	3

Final answer:

3

Example 2

Input:

target = [3,1,1,2]

Initial answer:

operations = 3

Traversal:

Index	Current	Previous	Increase	Operations
1	1	3	0	3
2	1	1	0	3
3	2	1	1	4

Final answer:

4

Example 3

Input:

target = [3,1,5,4,2]

Initial answer:

operations = 3

Traversal:

Index	Current	Previous	Increase	Operations
1	1	3	0	3
2	5	1	4	7
3	4	5	0	7
4	2	4	0	7

Final answer:

7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only a few integer variables are used

The algorithm processes each element exactly once, making the runtime linear in the size of the input.

No auxiliary arrays, stacks, or recursion are used, so the extra memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        operations = target[0]

        for i in range(1, len(target)):
            if target[i] > target[i - 1]:
                operations += target[i] - target[i - 1]

        return operations

sol = Solution()

assert sol.minNumberOperations([1,2,3,2,1]) == 3  # example 1
assert sol.minNumberOperations([3,1,1,2]) == 4  # example 2
assert sol.minNumberOperations([3,1,5,4,2]) == 7  # example 3

assert sol.minNumberOperations([1]) == 1  # single element
assert sol.minNumberOperations([5]) == 5  # single large element

assert sol.minNumberOperations([1,1,1,1]) == 1  # flat array
assert sol.minNumberOperations([1,2,3,4,5]) == 5  # strictly increasing
assert sol.minNumberOperations([5,4,3,2,1]) == 5  # strictly decreasing

assert sol.minNumberOperations([2,2,2,3,3]) == 3  # plateau then increase
assert sol.minNumberOperations([3,3,1,1,4]) == 6  # drop then rise

assert sol.minNumberOperations([1,3,2,5,4,6]) == 8  # alternating rises

assert sol.minNumberOperations([100000]) == 100000  # max value single element
assert sol.minNumberOperations([100000,100000]) == 100000  # large flat values

Test Case Summary

Test	Why
[1,2,3,2,1]	Validates standard mountain shape
[3,1,1,2]	Tests decreasing then increasing
[3,1,5,4,2]	Tests large upward jump
[1]	Smallest valid array
[5]	Single large value
[1,1,1,1]	Flat plateau case
[1,2,3,4,5]	Strictly increasing sequence
[5,4,3,2,1]	Strictly decreasing sequence
[2,2,2,3,3]	Plateau followed by increase
[3,3,1,1,4]	Multiple plateaus and jumps
[1,3,2,5,4,6]	Alternating increases and decreases
[100000]	Maximum value edge case
[100000,100000]	Large constant heights

Edge Cases

One important edge case is a strictly increasing array such as [1,2,3,4,5]. A naive implementation might incorrectly attempt to reuse previous operations too aggressively. In reality, every increase requires additional operations. The implementation handles this by adding every positive difference between adjacent elements.

Another important case is a strictly decreasing array like [5,4,3,2,1]. It may seem that additional operations are needed at every index, but all required layers already started earlier and can simply terminate gradually. The algorithm correctly avoids adding anything when the current value is smaller than the previous value.

A third critical case is large flat plateaus such as [7,7,7,7]. An incorrect implementation might repeatedly count the same height multiple times. The greedy solution handles this correctly because equal adjacent values produce a difference of zero, so no extra operations are added.

A final subtle case involves alternating peaks and valleys such as [1,5,2,6,3]. These patterns test whether the algorithm correctly distinguishes between reusable layers and genuinely new layers. By considering only positive increases, the implementation counts exactly the necessary new operations while reusing previous work whenever possible.