Watch 9 video solutions for Minimum Increment Operations to Make Array Beautiful, a medium level problem involving Array, Dynamic Programming. This walkthrough by Ayush Rao has 1,782 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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):
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 <= 1050 <= nums[i] <= 1090 <= k <= 109Problem Overview: You are given an integer array nums and a target value k. You can increment any element by 1 per operation. The array is considered beautiful if every subarray of length 3 contains at least one element greater than or equal to k. The goal is to compute the minimum number of increment operations required.
Approach 1: Greedy Increment Strategy (O(n) time, O(1) space)
Start by computing the cost to raise each element to k: cost[i] = max(0, k - nums[i]). For every window of length three, at least one index must be upgraded so its value reaches k. The greedy idea is to treat each upgraded index as covering the windows that include it. Track the last few positions that could satisfy the constraint and always choose the option with the minimum accumulated cost. This works because upgrading an index automatically satisfies up to three overlapping windows, so picking the cheapest candidate among nearby indices minimizes total operations.
Approach 2: Sliding Window with Running Minimum (Dynamic Programming) (O(n) time, O(1) space)
This approach models the problem as a dynamic programming transition. Let dp[i] represent the minimum operations needed if index i is the element that satisfies the window ending at i. The cost to use this index is cost[i] = max(0, k - nums[i]). Since any window of size three must contain at least one upgraded element, the previous valid index must be within the last three positions. The recurrence becomes dp[i] = cost[i] + min(dp[i-1], dp[i-2], dp[i-3]). Maintain the running minimum over the previous three states instead of storing the entire array. This effectively behaves like a small sliding window over DP states while iterating through the array. The final answer is the minimum among the last three states because the last window may end at any of them.
Recommended for interviews: The dynamic programming formulation with a sliding window minimum is the expected solution. It clearly shows how overlapping windows translate into state transitions and achieves optimal O(n) time with constant space. Starting from the greedy intuition helps explain why only the last three indices matter, but the DP formulation demonstrates stronger problem‑solving structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Increment Strategy | O(n) | O(1) | When you reason about covering each length‑3 window with the cheapest upgrade candidate. |
| Sliding Window with Running Minimum (DP) | O(n) | O(1) | Best general solution. Converts overlapping window constraints into DP with the minimum of the last three states. |