2919. Minimum Increment Operations to Make Array Beautiful LeetCode Solution
In this guide, you will get 2919. Minimum Increment Operations to Make Array Beautiful LeetCode Solution with the best time and space complexity. The solution to Minimum Increment Operations to Make Array Beautiful problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Increment Operations to Make Array Beautiful
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.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2919. Minimum Increment Operations to Make Array Beautiful LeetCode Solution in C++
class Solution {
public:
long long minIncrementOperations(std::vector<int>& nums, int k) {
// the minimum operations to increase nums[i - 3] and nums[0..i - 3)
long prev3 = 0;
// the minimum operations to increase nums[i - 2] and nums[0..i - 2)
long prev2 = 0;
// the minimum operations to increase nums[i - 1] and nums[0..i - 1)
long prev1 = 0;
for (const int& num : nums) {
const long dp = min({prev1, prev2, prev3}) + max(0, k - num);
prev3 = prev2;
prev2 = prev1;
prev1 = dp;
}
return min({prev1, prev2, prev3});
}
}; /* code provided by PROGIEZ */
2919. Minimum Increment Operations to Make Array Beautiful LeetCode Solution in Java
class Solution {
public long minIncrementOperations(int[] nums, int k) {
// the minimum operations to increase nums[i - 3] and nums[0..i - 3)
long prev3 = 0;
// the minimum operations to increase nums[i - 2] and nums[0..i - 2)
long prev2 = 0;
// the minimum operations to increase nums[i - 1] and nums[0..i - 1)
long prev1 = 0;
for (final int num : nums) {
final long dp = Math.min(prev1, Math.min(prev2, prev3)) + Math.max(0, k - num);
prev3 = prev2;
prev2 = prev1;
prev1 = dp;
}
return Math.min(prev1, Math.min(prev2, prev3));
}
} // code provided by PROGIEZ
2919. Minimum Increment Operations to Make Array Beautiful LeetCode Solution in Python
class Solution:
def minIncrementOperations(self, nums: list[int], k: int) -> int:
# the minimum operations to increase nums[i - 3] and nums[0..i - 3)
prev3 = 0
# the minimum operations to increase nums[i - 2] and nums[0..i - 2)
prev2 = 0
# the minimum operations to increase nums[i - 1] and nums[0..i - 1)
prev1 = 0
for num in nums:
dp = min(prev1, prev2, prev3) + max(0, k - num)
prev3 = prev2
prev2 = prev1
prev1 = dp
return min(prev1, prev2, prev3) # code by PROGIEZ
