2919

2919. Minimum Increment Operations to Make Array Beautiful (Medium)

You are given a 0-indexed integer array nums having length n, and an integer k.

You can perform the following increment operation any number of times (including zero):

• Choose an index i in the range [0, n - 1], and increase nums[i] by 1.

An array is considered beautiful if, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k.

Return an integer denoting the minimum number of increment operations needed to make nums beautiful.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [2,3,0,0,2], k = 4
Output: 3
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 1 and increase nums[1] by 1 -> [2,4,0,0,2].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,3].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,4].
The subarrays with a size of 3 or more are: [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4].
In all the subarrays, the maximum element is equal to k = 4, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 3 increment operations.
Hence, the answer is 3.

Example 2:

Input: nums = [0,1,3,3], k = 5
Output: 2
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 2 and increase nums[2] by 1 -> [0,1,4,3].
Choose index i = 2 and increase nums[2] by 1 -> [0,1,5,3].
The subarrays with a size of 3 or more are: [0,1,5], [1,5,3], [0,1,5,3].
In all the subarrays, the maximum element is equal to k = 5, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 2 increment operations.
Hence, the answer is 2.

Example 3:

Input: nums = [1,1,2], k = 1
Output: 0
Explanation: The only subarray with a size of 3 or more in this example is [1,1,2].
The maximum element, 2, is already greater than k = 1, so we don't need any increment operation.
Hence, the answer is 0.

 

Constraints:

• 3 <= n == nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= k <= 109

Companies: Google

Related Topics:
Array, Dynamic Programming

Hints:

• There needs to be at least one value among 3 consecutive values in the array that is greater than or equal to k.
• The problem can be solved using dynamic programming.
• Let dp[i] be the minimum number of increment operations required to make the subarray consisting of the first i values beautiful, while also having the value at nums[i] >= k.
• dp[0] = max(0, k - nums[0]), dp[1] = max(0, k - nums[1]), and dp[2] = max(0, k - nums[2]).
• dp[i] = max(0, k - nums[i]) + min(dp[i - 1], dp[i - 2], dp[i - 3]) for i in the range [3, n - 1].
• The answer to the problem is min(dp[n - 1], dp[n - 2], dp[n - 3]).

Solution 1.

Let dp[i+1] be the minimum number of operations needed to make A[0..i] beautiful with the last operation applied onto A[i]. The answer is min(dp[N-1], dp[N-2], dp[N-3]).

When we apply an operation on A[i] with max(k - A[i], 0) operations, the previous operation must be applied on one of A[i-1], A[i-2] and A[i-3]. We can greedily pick the minimum of dp[i-1], dp[i-2], dp[i-3].

dp[0] = 0
dp[i+1] = max(k - n, 0)       // # of operations needed on A[i]
            + min({a, b, c})  // min # of operations needed for the previous 3 states

// OJ: https://leetcode.com/problems/minimum-increment-operations-to-make-array-beautiful
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    long long minIncrementOperations(vector<int>& A, int k) {
        long long a = 0, b = LLONG_MAX, c = LLONG_MAX;
        for (int n : A){
            long long x = max(k - n, 0) + min({a, b, c});
            c = b;
            b = a;
            a = x;
        }
        return min({a, b, c});
    }
};

Discussion

https://leetcode.com/problems/minimum-increment-operations-to-make-array-beautiful/solutions/4220728/c-iterative-dp-o-n-time-o-1-space/