# Minimum Increment Operations to Make Array Beautiful
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-increment-operations-to-make-array-beautiful)
Canonical: https://scaleengineer.com/dsa/problems/minimum-increment-operations-to-make-array-beautiful
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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.

**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 <= 105`
* `0 <= nums[i] <= 109`
* `0 <= k <= 109`

# Approaches
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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:

1.  Make `nums[i] >= k`. The cost is `max(0, k - nums[i])` plus the cost to make the prefix `nums[0...i-1]` beautiful, which is `solve(i-1)`.
2.  Make `nums[i-1] >= k`. The cost is `max(0, k - nums[i-1])` plus the cost to make the prefix `nums[0...i-2]` beautiful, which is `solve(i-2)`.
3.  Make `nums[i-2] >= k`. The cost is `max(0, k - nums[i-2])` plus the cost to make the prefix `nums[0...i-3]` beautiful, which is `solve(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.

```java
// 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));
    }
}
```
### Algorithm
1. Define a recursive function `solve(i)` that computes the minimum cost to make the prefix `nums[0...i]` beautiful.
2. 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.
3. For `i >= 2`, the function explores three possibilities to satisfy the condition for the window `[nums[i-2], nums[i-1], nums[i]]`:
    a. Increment `nums[i]`: The cost is `max(0, k - nums[i])` plus the cost for the prefix `nums[0...i-1]`, which is `solve(i-1)`.
    b. Increment `nums[i-1]`: The cost is `max(0, k - nums[i-1])` plus the cost for the prefix `nums[0...i-2]`, which is `solve(i-2)`.
    c. Increment `nums[i-2]`: The cost is `max(0, k - nums[i-2])` plus the cost for the prefix `nums[0...i-3]`, which is `solve(i-3)`.
4. The function returns the minimum cost among these three options.
5. The final answer is obtained by calling `solve(n-1)`.

## Dynamic Programming with O(N) Space
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.
**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.
**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.
### Explanation
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]]`:
1.  Increment `nums[i-1]` to `k`. The cost for this operation is `cost(i-1) = max(0L, k - nums[i-1])`. The prefixes up to `i-2` must also be beautiful, which costs `dp[i-1]`. Total cost: `dp[i-1] + cost(i-1)`.
2.  Increment `nums[i-2]` to `k`. The cost is `dp[i-2] + cost(i-2)`.
3.  Increment `nums[i-3]` to `k`. The cost is `dp[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.

```java
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];
}
```
### Algorithm
1. Create a `dp` array of size `n + 1` of type `long`.
2. Define `dp[i]` as the minimum cost to make the prefix `nums[0...i-1]` beautiful.
3. Initialize base cases: `dp[0] = 0`, `dp[1] = 0`, `dp[2] = 0`, as prefixes shorter than 3 are trivially beautiful.
4. Iterate `i` from `3` to `n`.
5. Inside the loop, calculate the cost to increment `nums[i-1]`, `nums[i-2]`, and `nums[i-3]` to `k`.
6. 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))`.
7. After the loop, `dp[n]` holds the minimum total cost for the entire array. Return `dp[n]`.

## Space-Optimized Dynamic Programming
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).
**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.
**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.
### Explanation
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.

```java
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;
}
```
### Algorithm
1. Initialize three `long` variables: `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.
2. Iterate `i` from `3` to `n`.
3. Inside the loop, calculate `cost1 = max(0L, k - nums[i-1])`, `cost2 = max(0L, k - nums[i-2])`, and `cost3 = max(0L, k - nums[i-3])`.
4. Calculate the current DP value: `current_dp = min(dp_i_1 + cost1, dp_i_2 + cost2, dp_i_3 + cost3)`.
5. 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`.
6. After the loop, `dp_i_1` will hold the final answer for the entire array. Return `dp_i_1`.

# Solutions
### CSharp

```csharp
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);
    }
}
```

### Java

```java
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);
  }
}

```

### CPP

```cpp
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});
  }
};

```

### Python

```python
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)

```