Minimum Increment Operations to Make Array Beautiful - Solution & Explanation
Problem Statement
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
iin 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 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 <= 109
Approach Overview
Problem 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 1: Sliding Window with Running Maximum
This approach involves maintaining a running maximum for each subarray of size at least 3. If the maximum is less than k, increment the necessary elements to achieve the desired maximum. This can be done efficiently with a sliding window technique.
This solution uses a sliding window technique, iterating through the array and maintaining a running maximum for each subarray of size at least 3. It only increments elements when required, minimizing the total increments.
Code
Python
Java
C++
C#
JavaScript
Complexity
Time complexity: O(n) where n is the length of the array. Space complexity: O(1) as we only use constant extra space.
Approach 2: Greedy Increment Strategy
The greedy strategy involves iterating through the array and incrementing only when the current maximum found within the sliding window is less than k. The key is to immediately adjust the necessary element to meet the subarray criterion.
This greedy method directly computes and increments deficiencies from the expected maximum value iteratively, ensuring all relevant subarrays contain a maximum value >= k.
Code
Python
Java
C++
C#
JavaScript
Complexity
Time complexity: O(n). Space complexity: O(1).
Approach 3: 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)$.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Running Maximum | Time complexity: O(n) where n is the length of the array. Space complexity: O(1) as we only use constant extra space. |
| Greedy Increment Strategy | Time complexity: O(n). Space complexity: O(1). |
| Dynamic Programming | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2919. Minimum Increment Operations to Make Array Beautiful || Greedy ❌ || Dynamic Programming ✅ • Ayush Rao • 1,804 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Minimum Increment Operations to Make Array Beautiful easy or hard?
Minimum Increment Operations to Make Array Beautiful Python/Java solution
How to solve Minimum Increment Operations to Make Array Beautiful in O(n)?
What is the best approach for Minimum Increment Operations to Make Array Beautiful?
Is Minimum Increment Operations to Make Array Beautiful asked at Google/Amazon/Meta?
What data structure is used in Minimum Increment Operations to Make Array Beautiful?
What is the time complexity of Minimum Increment Operations to Make Array Beautiful?
Ready to solve this problem?
Practice Minimum Increment Operations to Make Array Beautiful with our built-in code editor and test cases.
Practice on FleetCode