1526

1526. Minimum Number of Increments on Subarrays to Form a Target Array (Hard)

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

• Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.

 

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).

Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).

Example 4:

Input: target = [1,1,1,1]
Output: 1

 

Constraints:

• 1 <= target.length <= 10^5
• 1 <= target[i] <= 10^5

Related Topics:
Segment Tree

Solution 1.

I found that a small number will break the increments into two parts. For example [2, 1, 2], you can't increment both the first and last 2 at the same time because there is a smaller number 1 in between. So we need to pay attention to those small numbers.

I also tried to see if it's possible to resolve this problem using a linear scan, and it turns out working. Take some inputs as examples.

For input [3 1 5]:

• To get 3, we need 3 increments.
• To get 1, since it's smaller than 3, we can get 1 while getting 3, so we don't need additional increment.
• To get 5, since 5 is greater than 1, we need 5 - 1 = 4 more increments to get 5.
• In total we need 3 + 0 + 4 increments.

I also verified this algorithm with inputs like [1, 2, 3] and [2, 1, 2] to check the correctness.

The algorithm would be as simple as:

• Linear scan the array.
• For A[i], if it's greater than A[i - 1], then increment answer by A[i] - A[i - 1]; otherwise, do nothing.

// OJ: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minNumberOperations(vector<int>& A) {
        int ans = A[0];
        for (int i = 1; i < A.size(); ++i) ans += max(0, A[i] - A[i - 1]);
        return ans;
    }
};

We can compress it into two lines.

// OJ: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minNumberOperations(vector<int>& A) {
        for (int i = A.size() - 1; i > 0; --i) A[i] = max(0, A[i] - A[i - 1]);
        return accumulate(begin(A), end(A), 0);
    }
};

This would be a one liner in python

# OJ: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
# Author: github.com/lzl124631x
# Time: O(N)
# Space: O(1)
class Solution:
    def minNumberOperations(self, A: List[int]) -> int:
        return sum([max(0, x - y) for x, y in zip(A, [0] + A)])