Welcome to Subscribe On Youtube
2919. Minimum Increment Operations to Make Array Beautiful
Description
You are given a 0indexed 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 increasenums[i]
by1
.
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 nonempty 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 <= 10^{5}
0 <= nums[i] <= 10^{9}
0 <= k <= 10^{9}
Solutions
Solution 1: Dynamic Programming
We define $f$, $g$, and $h$ as the minimum number of increment operations needed to get the maximum value from the last three items in the first $i$ items, initially $f = 0$, $g = 0$, $h = 0$.
Next, we traverse the array $nums$. For each $x$, we need to update the values of $f$, $g$, and $h$ to meet the requirements of the problem, that is:
\[\begin{aligned} f' &= g \\ g' &= h \\ h' &= \min(f, g, h) + \max(k  x, 0) \end{aligned}\]Finally, we only need to return the minimum value among $f$, $g$, and $h$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

class Solution { public long minIncrementOperations(int[] nums, int k) { long f = 0, g = 0, h = 0; for (int x : nums) { long hh = Math.min(Math.min(f, g), h) + Math.max(k  x, 0); f = g; g = h; h = hh; } return Math.min(Math.min(f, g), h); } }

class Solution { public: long long minIncrementOperations(vector<int>& nums, int k) { long long f = 0, g = 0, h = 0; for (int x : nums) { long long hh = min({f, g, h}) + max(k  x, 0); f = g; g = h; h = hh; } return min({f, g, h}); } };

class Solution: def minIncrementOperations(self, nums: List[int], k: int) > int: f = g = h = 0 for x in nums: f, g, h = g, h, min(f, g, h) + max(k  x, 0) return min(f, g, h)

func minIncrementOperations(nums []int, k int) int64 { var f, g, h int for _, x := range nums { f, g, h = g, h, min(f, g, h)+max(kx, 0) } return int64(min(f, g, h)) }

function minIncrementOperations(nums: number[], k: number): number { let [f, g, h] = [0, 0, 0]; for (const x of nums) { [f, g, h] = [g, h, Math.min(f, g, h) + Math.max(k  x, 0)]; } return Math.min(f, g, h); }