Minimum Increment Operations to Make Array Beautiful
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a recursive function to explore all possible ways to make the array beautiful. For each window of three elements [nums[i-2], nums[i-1], nums[i]], we have three choices: increment nums[i-2], nums[i-1], or nums[i] to be at least k. The function recursively calculates the minimum cost for each choice and returns the overall minimum. This method is simple to conceptualize but computationally expensive due to redundant calculations of the same subproblems.
Algorithm
- Define a recursive function
solve(i)that computes the minimum cost to make the prefixnums[0...i]beautiful. - The base case for the recursion is when
i < 2. For such prefixes, there are no subarrays of size 3, so the cost is 0. - For
i >= 2, the function explores three possibilities to satisfy the condition for the window[nums[i-2], nums[i-1], nums[i]]: a. Incrementnums[i]: The cost ismax(0, k - nums[i])plus the cost for the prefixnums[0...i-1], which issolve(i-1). b. Incrementnums[i-1]: The cost ismax(0, k - nums[i-1])plus the cost for the prefixnums[0...i-2], which issolve(i-2). c. Incrementnums[i-2]: The cost ismax(0, k - nums[i-2])plus the cost for the prefixnums[0...i-3], which issolve(i-3). - The function returns the minimum cost among these three options.
- The final answer is obtained by calling
solve(n-1).
Walkthrough
We define a recursive function, say solve(i), which calculates the minimum cost to make the prefix nums[0...i] beautiful. The final answer is solve(n-1). The base cases for the recursion are when i < 2, the cost is 0, as there are no subarrays of size 3. For a given i >= 2, we need to satisfy the condition for the window [nums[i-2], nums[i-1], nums[i]], in addition to all previous windows. The recursive step explores three possibilities:
- Make
nums[i] >= k. The cost ismax(0, k - nums[i])plus the cost to make the prefixnums[0...i-1]beautiful, which issolve(i-1). - Make
nums[i-1] >= k. The cost ismax(0, k - nums[i-1])plus the cost to make the prefixnums[0...i-2]beautiful, which issolve(i-2). - Make
nums[i-2] >= k. The cost ismax(0, k - nums[i-2])plus the cost to make the prefixnums[0...i-3]beautiful, which issolve(i-3).
The function solve(i) returns the minimum of these three values. This approach has overlapping subproblems. For example, solve(i) calls solve(i-1), which in turn calls solve(i-2) and solve(i-3). These subproblems are also computed directly when calculating solve(i), leading to an exponential number of redundant computations.
// This is a conceptual representation of the brute-force recursion.// A direct implementation would be too slow and result in a "Time Limit Exceeded" error.class Solution { private int[] nums; private int k; public long minIncrementOperations(int[] nums, int k) { this.nums = nums; this.k = k; // This recursive call would be the entry point. // return solve(nums.length - 1); return -1; // Placeholder for a compilable snippet } private long solve(int i) { // Base case: prefixes of length 1 or 2 are beautiful by default. if (i < 2) { return 0; } // Cost to make the current element (and previous two) >= k long cost_i = Math.max(0, k - nums[i]); long cost_i_1 = Math.max(0, k - nums[i-1]); long cost_i_2 = Math.max(0, k - nums[i-2]); // Recursive step long option1 = solve(i - 1) + cost_i; long option2 = solve(i - 2) + cost_i_1; long option3 = solve(i - 3) + cost_i_2; return Math.min(option1, Math.min(option2, option3)); }}Complexity
Time
O(3^N), where N is the length of the array. Each function call can lead to three more recursive calls, creating an exponential call tree.
Space
O(N), where N is the length of the array. This space is used by the recursion stack.
Trade-offs
Pros
Simple to derive from the problem's recursive structure.
Cons
Extremely inefficient due to exponential time complexity.
Results in 'Time Limit Exceeded' for the given constraints.
High recursion depth might lead to a stack overflow error.
This approach improves upon the brute-force recursion by using dynamic programming to avoid recomputing subproblems. We can use either memoization (top-down) or tabulation (bottom-up). We'll use an array, say dp, where dp[i] stores the minimum cost to make the prefix nums[0...i] beautiful. This leads to a solution with linear time complexity.
Algorithm
- Create a
dparray of sizen + 1of typelong. - Define
dp[i]as the minimum cost to make the prefixnums[0...i-1]beautiful. - Initialize base cases:
dp[0] = 0,dp[1] = 0,dp[2] = 0, as prefixes shorter than 3 are trivially beautiful. - Iterate
ifrom3ton. - Inside the loop, calculate the cost to increment
nums[i-1],nums[i-2], andnums[i-3]tok. - Compute
dp[i]using the recurrence:dp[i] = min(dp[i-1] + cost(i-1), dp[i-2] + cost(i-2), dp[i-3] + cost(i-3)). - After the loop,
dp[n]holds the minimum total cost for the entire array. Returndp[n].
Walkthrough
The core idea is to solve the problem for larger prefixes by using the solutions for smaller prefixes. We define dp[i] as the minimum cost to make the prefix nums[0...i-1] beautiful. Our goal is to compute dp[n].
The base cases are dp[0] = 0, dp[1] = 0, and dp[2] = 0, as prefixes of length less than 3 are trivially beautiful.
For i >= 3, we can compute dp[i] by considering three choices to satisfy the beauty condition for the last window [nums[i-3], nums[i-2], nums[i-1]]:
- Increment
nums[i-1]tok. The cost for this operation iscost(i-1) = max(0L, k - nums[i-1]). The prefixes up toi-2must also be beautiful, which costsdp[i-1]. Total cost:dp[i-1] + cost(i-1). - Increment
nums[i-2]tok. The cost isdp[i-2] + cost(i-2). - Increment
nums[i-3]tok. The cost isdp[i-3] + cost(i-3).
The recurrence relation is: dp[i] = min(dp[i-1] + cost(i-1), dp[i-2] + cost(i-2), dp[i-3] + cost(i-3)). We can implement this using a bottom-up (tabulation) approach by iterating from i = 3 to n and filling the dp table.
public long minIncrementOperations(int[] nums, int k) { int n = nums.length; long[] dp = new long[n + 1]; // dp[i] = min cost to make prefix nums[0...i-1] beautiful // Base cases dp[0], dp[1], dp[2] are 0 because prefixes of length < 3 are beautiful. for (int i = 3; i <= n; i++) { long cost1 = Math.max(0, k - nums[i - 1]); long cost2 = Math.max(0, k - nums[i - 2]); long cost3 = Math.max(0, k - nums[i - 3]); long option1 = dp[i - 1] + cost1; long option2 = dp[i - 2] + cost2; long option3 = dp[i - 3] + cost3; dp[i] = Math.min(option1, Math.min(option2, option3)); } return dp[n];}Complexity
Time
O(N), as we iterate through the array once to fill the DP table.
Space
O(N), where N is the length of the array, for the `dp` array.
Trade-offs
Pros
Efficient with linear time complexity.
Guaranteed to find the optimal solution.
Easy to understand and implement once the recurrence is found.
Cons
Uses O(N) extra space, which can be optimized.
This is the most efficient approach and is an optimization of the previous DP solution. We observe that the calculation of dp[i] only depends on the three previous values: dp[i-1], dp[i-2], and dp[i-3]. This allows us to use only a few variables to store these values instead of a full dp array, reducing the space complexity from O(N) to O(1).
Algorithm
- Initialize three
longvariables:dp_i_3 = 0,dp_i_2 = 0,dp_i_1 = 0. These correspond to the DP values for prefixes of length 0, 1, and 2. - Iterate
ifrom3ton. - Inside the loop, calculate
cost1 = max(0L, k - nums[i-1]),cost2 = max(0L, k - nums[i-2]), andcost3 = max(0L, k - nums[i-3]). - Calculate the current DP value:
current_dp = min(dp_i_1 + cost1, dp_i_2 + cost2, dp_i_3 + cost3). - Update the variables for the next iteration by shifting them:
dp_i_3 = dp_i_2,dp_i_2 = dp_i_1,dp_i_1 = current_dp. - After the loop,
dp_i_1will hold the final answer for the entire array. Returndp_i_1.
Walkthrough
The recurrence relation dp[i] = min(dp[i-1] + cost(i-1), dp[i-2] + cost(i-2), dp[i-3] + cost(i-3)) shows that we only need a sliding window of the last three DP results to compute the next one.
Instead of a full dp array, we can use three variables, say dp_i_3, dp_i_2, and dp_i_1, to store the values of dp[i-3], dp[i-2], and dp[i-1] respectively.
We initialize these variables to 0, corresponding to dp[0], dp[1], and dp[2]. We then iterate from i = 3 to n. In each iteration, we calculate the current dp value, dp_current, using dp_i_1, dp_i_2, and dp_i_3. After calculating dp_current, we update our three variables for the next iteration: dp_i_3 becomes dp_i_2, dp_i_2 becomes dp_i_1, and dp_i_1 becomes dp_current. After the loop finishes, dp_i_1 will hold the value of dp[n], which is our final answer.
public long minIncrementOperations(int[] nums, int k) { int n = nums.length; // dp_i_3, dp_i_2, dp_i_1 correspond to dp[i-3], dp[i-2], dp[i-1] from the O(N) space solution // where dp[i] is the min cost for prefix nums[0...i-1]. // Initially, they represent dp[0], dp[1], dp[2] which are all 0. long dp_i_3 = 0; long dp_i_2 = 0; long dp_i_1 = 0; for (int i = 3; i <= n; i++) { long cost1 = Math.max(0, k - nums[i - 1]); long cost2 = Math.max(0, k - nums[i - 2]); long cost3 = Math.max(0, k - nums[i - 3]); long current_dp = Math.min(dp_i_1 + cost1, Math.min(dp_i_2 + cost2, dp_i_3 + cost3)); dp_i_3 = dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = current_dp; } return dp_i_1;}Complexity
Time
O(N), as it involves a single pass through the input array.
Space
O(1), as we only use a constant number of variables to store the necessary state.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Highly efficient for large inputs.
Cons
The logic can be slightly harder to follow without the context of the full DP array.
Solutions
Solution
public class Solution { public long MinIncrementOperations(int[] nums, int k) { long f = 0, g = 0, h = 0; foreach(int x in 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 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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.