Minimum Increment Operations to Make Array Beautiful Solution
Minimum Increment Operations to Make Array Beautiful solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Increment Operations to Make Array Beautiful is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of length n and an integer k. In one operation you pick any index and add 1 to that element.
The array is beautiful when every contiguous subarray of length 3 or more has a maximum of at least k.
Return the minimum number of operations that makes nums beautiful.
The original allows values up to 10^9; here values are capped at 10^4 so the answer always fits in a 32-bit integer.
Example 1
Input: nums = [2,3,0,0,2], k = 4
Output: 3
Explanation: Raise `nums[1]` once and `nums[4]` twice: `[2,4,0,0,4]`. Every window of three now contains a 4.
Example 2
Input: nums = [0,1,3,3], k = 5
Output: 2
Explanation: Raising `nums[2]` to 5 covers both windows of length 3.
Example 3
Input: nums = [1,1,2], k = 1
Output: 0
Constraints
3 <= n == nums.length <= 10^50 <= nums[i] <= 10^40 <= k <= 10^4
Hints for Minimum Increment Operations to Make Array Beautiful
Hint 1
A subarray longer than 3 contains a window of length 3, so only the windows of exactly three matter.
Hint 2
There is never a reason to raise an element above
k, and every window of three needs at least one element atkor more.Hint 3
Let
dp[i]be the cheapest cost when elementiis the last one raised tok: it ismax(0, k - nums[i])plus the best of the three previousdpvalues.
How to solve Minimum Increment Operations to Make Array Beautiful
The condition just says: no three consecutive elements may all stay below k. So we choose a set of positions to lift to k, with gaps of at most two between them — a DP over the last chosen position.
Approach
- Let
cost(i) = max(0, k - nums[i]), the price of makingnums[i]reachk. dp[i] = cost(i) + min(dp[i-1], dp[i-2], dp[i-3]), where an index before the array counts as0— the first three positions may be the first chosen one.- Keep only the last three values in three variables.
- The answer is
min(dp[n-1], dp[n-2], dp[n-3]): the last chosen position must be within the final window.
Why it works
Raising an element past k or raising two elements of one window is never forced, so an optimal solution lifts a set of positions exactly to k (already-large elements cost 0). The set is valid exactly when every window of three contains one of them, i.e. consecutive chosen positions are at most three apart and the first and last lie in the first and last windows — which is what the recurrence and the final minimum enforce.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Elements already at least
kcost nothing — usemax(0, k - x), notk - x. - The answer is the minimum of the last three states, not just
dp[n-1]. - With the original 10^9 bounds the total needs 64 bits; the tightened bounds keep it in int32.
Reference solution
Python
from typing import List
def minIncrementOperations(nums: List[int], k: int) -> int:
a = b = c = 0
for x in nums:
cur = max(0, k - x) + min(a, b, c)
a, b, c = b, c, cur
return min(a, b, c)Java
public static int minIncrementOperations(int[] nums, int k) {
long a = 0, b = 0, c = 0;
for (int x : nums) {
long cur = Math.max(0, k - x) + Math.min(a, Math.min(b, c));
a = b; b = c; c = cur;
}
return (int) Math.min(a, Math.min(b, c));
}C++
int minIncrementOperations(vector<int>& nums, int k) {
long long a = 0, b = 0, c = 0;
for (int x : nums) {
long long cur = max(0, k - x) + min(a, min(b, c));
a = b; b = c; c = cur;
}
return (int) min(a, min(b, c));
}JavaScript
var minIncrementOperations = function(nums, k) {
var a = 0, b = 0, c = 0;
for (var i = 0; i < nums.length; i++) {
var cur = Math.max(0, k - nums[i]) + Math.min(a, b, c);
a = b; b = c; c = cur;
}
return Math.min(a, b, c);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming