Build a target array from zeros using the fewest operations, where each operation can increment a chosen contiguous subarray by 1.
Minimum Operations to Make Array Equal to Target
gfgProblem
You start with an array of zeros of length . You are given a target array of length .
In one operation, you may choose any contiguous subarray and increment every element in that subarray by 1.
Return the minimum number of operations required to transform the zero array into the target array.
Intuition
Each operation can add 1 to a consecutive block. The goal is to count how many new increments must begin as you move from left to right.
Input Format
- An integer array
target. - The array represents the desired final values.
Output Format
- Return an integer: the minimum number of operations needed.
Constraints
1 <= target.length- Values in
targetare non-negative integers. - The exact official constraints may vary by platform, but the solution should be linear in the array length.
Hints
- Compare each element with the previous one.
- A rise from
target[i-1]totarget[i]means additional operations must start at indexi. - Think of the array as stacks of horizontal layers.
Input Format
target: integer array
The array stores the final heights that must be formed from an all-zero array.
Output Format
- Return the minimum number of contiguous increment operations needed to construct
target.
Constraints
- Non-empty array
- Non-negative integers
- Aim for time and extra space
Example 1
Input
target = [1,2,3,2,1]
Output
3
Explanation
One way is to start 1 operation for [0..4], then 1 more for [1..3], and 1 more for [2..2]. Total = 3.
Example 2
Input
target = [3,1,1,2]
Output
4
Explanation
Start with 3 operations at index 0 to reach 3. The value drops to 1, so no new operations are needed there. At the last index, the value increases from 1 to 2, so one additional operation is needed. Total = 3 + 1 = 4.
Show 1 more example
Example 3
Input
target = [1,1,1]
Output
1
Explanation
A single operation on the whole array is enough.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.