Minimum Number of Increments on Subarrays to Form a Target Array
01 · Problem
You are given an array target of positive integers. You start with an array initial of the same length filled with zeros.
In a single operation you choose any contiguous subarray of initial and add 1 to each of its elements.
Return the minimum number of operations needed to turn initial into target.
02 · Examples
target = [1,2,3,2,1]
3
Increment [0..4], then [1..3], then [2..2]. Three operations are needed because the peak value is 3.
target = [3,1,1,2]
4
Increment the whole array once, then index 0 twice more, then index 3 once more: 1 + 2 + 1 = 4 operations.
target = [3,1,5,4,2]
7
Each rise must be paid for with new operations: 3 to start, 0 for the drop to 1, 4 for the climb from 1 to 5, and nothing for the later drops. That totals 3 + 4 = 7.
03 · Constraints
- 011 <= target.length <= 105
- 021 <= target[i] <= 105
- 03The initial array is all zeros, with the same length as target
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.