Algorithms
Medium
2919
3178
Minimum Increment Operations to Make Array Beautiful
minimum-increment-operations-to-make-array-beautiful
"""
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
"""
class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        
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


Please complete the code below to solve above prblem:
```python
class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [2,3,0,0,2], "k": 4 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [0,1,3,3], "k": 5 }
assert my_solution.minIncrementOperations(**test_input) == 2

test_input = { "nums": [1,1,2], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [0,5,5], "k": 8 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [0,18,28], "k": 93 }
assert my_solution.minIncrementOperations(**test_input) == 65

test_input = { "nums": [0,24,14], "k": 7 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [2,3,4], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [3,5,9], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [4,3,0], "k": 2 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [5,6,5], "k": 9 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [6,9,6], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [7,9,0], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [7,47,16], "k": 39 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [9,6,1], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [41,44,37], "k": 55 }
assert my_solution.minIncrementOperations(**test_input) == 11

test_input = { "nums": [48,3,13], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [1,2,6,9], "k": 8 }
assert my_solution.minIncrementOperations(**test_input) == 2

test_input = { "nums": [1,3,1,6], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [2,35,41,20], "k": 4 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [3,9,9,7], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [7,7,2,7], "k": 9 }
assert my_solution.minIncrementOperations(**test_input) == 2

test_input = { "nums": [10,2,0,2], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 4

test_input = { "nums": [20,2,22,30], "k": 67 }
assert my_solution.minIncrementOperations(**test_input) == 45

test_input = { "nums": [22,49,0,20], "k": 52 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [25,2,1,41], "k": 9 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [31,86,1,2], "k": 354 }
assert my_solution.minIncrementOperations(**test_input) == 268

test_input = { "nums": [43,31,14,4], "k": 73 }
assert my_solution.minIncrementOperations(**test_input) == 42

test_input = { "nums": [44,24,28,47], "k": 16 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [1,9,5,2,0], "k": 2 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [3,7,9,6,0], "k": 7 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [5,9,0,10,3], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [6,2,8,10,6], "k": 9 }
assert my_solution.minIncrementOperations(**test_input) == 1

test_input = { "nums": [6,14,17,4,7], "k": 22 }
assert my_solution.minIncrementOperations(**test_input) == 5

test_input = { "nums": [10,9,5,2,4], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [20,38,29,34,6], "k": 95 }
assert my_solution.minIncrementOperations(**test_input) == 66

test_input = { "nums": [21,45,33,14,22], "k": 58 }
assert my_solution.minIncrementOperations(**test_input) == 25

test_input = { "nums": [32,14,31,43,29], "k": 46 }
assert my_solution.minIncrementOperations(**test_input) == 15

test_input = { "nums": [39,21,10,46,40], "k": 81 }
assert my_solution.minIncrementOperations(**test_input) == 71

test_input = { "nums": [42,7,32,19,4], "k": 66 }
assert my_solution.minIncrementOperations(**test_input) == 34

test_input = { "nums": [74,91,93,96,12], "k": 964 }
assert my_solution.minIncrementOperations(**test_input) == 871

test_input = { "nums": [84,17,58,61,72], "k": 432 }
assert my_solution.minIncrementOperations(**test_input) == 374

test_input = { "nums": [4,0,10,2,10,6], "k": 8 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [4,0,22,41,29,28], "k": 30 }
assert my_solution.minIncrementOperations(**test_input) == 8

test_input = { "nums": [4,1,8,0,3,9], "k": 2 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [4,7,6,9,2,6], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [5,1,3,9,8,8], "k": 4 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [6,5,8,6,0,9], "k": 9 }
assert my_solution.minIncrementOperations(**test_input) == 1

test_input = { "nums": [7,4,10,2,0,8], "k": 7 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [8,10,7,1,9,6], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [9,5,0,10,9,0], "k": 8 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [13,34,0,13,9,19], "k": 82 }
assert my_solution.minIncrementOperations(**test_input) == 117

test_input = { "nums": [16,50,23,35,38,13], "k": 34 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [20,1,40,48,32,24], "k": 38 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [28,5,10,26,38,6], "k": 17 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [30,42,46,45,23,31], "k": 13 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [3,8,0,6,46,24,31], "k": 30 }
assert my_solution.minIncrementOperations(**test_input) == 22

test_input = { "nums": [4,7,2,10,4,10,5], "k": 10 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [8,10,1,5,8,9,7], "k": 4 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [10,7,2,5,9,6,3], "k": 2 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [10,24,21,42,6,10,43], "k": 55 }
assert my_solution.minIncrementOperations(**test_input) == 56

test_input = { "nums": [18,48,1,19,43,25,49], "k": 21 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [37,82,95,82,77,87,93], "k": 239 }
assert my_solution.minIncrementOperations(**test_input) == 296

test_input = { "nums": [40,17,28,38,41,32,9], "k": 97 }
assert my_solution.minIncrementOperations(**test_input) == 125

test_input = { "nums": [41,22,4,41,4,47,36], "k": 25 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [42,19,52,36,8,5,9], "k": 656 }
assert my_solution.minIncrementOperations(**test_input) == 1252

test_input = { "nums": [45,58,6,16,70,69,87], "k": 26 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [48,24,41,16,4,20,38], "k": 97 }
assert my_solution.minIncrementOperations(**test_input) == 133

test_input = { "nums": [50,3,17,36,16,10,2], "k": 19 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [57,41,90,16,41,25,2], "k": 934 }
assert my_solution.minIncrementOperations(**test_input) == 1737

test_input = { "nums": [74,33,13,74,75,95,11], "k": 426 }
assert my_solution.minIncrementOperations(**test_input) == 744

test_input = { "nums": [83,54,75,22,32,59,30], "k": 298 }
assert my_solution.minIncrementOperations(**test_input) == 462

test_input = { "nums": [1,9,3,6,3,1,10,4], "k": 2 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [1,29,18,3,38,4,7,47], "k": 67 }
assert my_solution.minIncrementOperations(**test_input) == 87

test_input = { "nums": [2,1,1,7,2,3,5,6], "k": 9 }
assert my_solution.minIncrementOperations(**test_input) == 13

test_input = { "nums": [2,3,6,3,0,0,7,4], "k": 8 }
assert my_solution.minIncrementOperations(**test_input) == 8

test_input = { "nums": [2,9,6,9,1,9,4,0], "k": 6 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [5,1,6,9,5,4,9,2], "k": 10 }
assert my_solution.minIncrementOperations(**test_input) == 6

test_input = { "nums": [5,10,8,7,6,7,1,10], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [6,7,9,5,0,2,7,7], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [7,2,2,6,7,5,0,2], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [7,12,36,8,27,48,39,35], "k": 36 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [15,47,34,46,42,26,23,11], "k": 15 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [19,40,43,32,15,7,43,5], "k": 85 }
assert my_solution.minIncrementOperations(**test_input) == 120

test_input = { "nums": [22,45,6,7,7,23,6,3], "k": 43 }
assert my_solution.minIncrementOperations(**test_input) == 56

test_input = { "nums": [25,1,70,71,54,96,46,77], "k": 549 }
assert my_solution.minIncrementOperations(**test_input) == 932

test_input = { "nums": [33,41,14,18,43,20,49,23], "k": 25 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [39,26,16,36,19,5,6,28], "k": 98 }
assert my_solution.minIncrementOperations(**test_input) == 175

test_input = { "nums": [44,44,31,36,1,8,39,46], "k": 45 }
assert my_solution.minIncrementOperations(**test_input) == 16

test_input = { "nums": [2,17,43,26,33,12,37,28,34], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [3,1,6,1,0,5,4,5,7], "k": 10 }
assert my_solution.minIncrementOperations(**test_input) == 12

test_input = { "nums": [3,10,4,2,9,8,2,1,4], "k": 7 }
assert my_solution.minIncrementOperations(**test_input) == 3

test_input = { "nums": [7,5,4,7,6,5,10,8,8], "k": 8 }
assert my_solution.minIncrementOperations(**test_input) == 2

test_input = { "nums": [7,40,36,45,42,23,10,33,17], "k": 25 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [10,4,7,4,8,7,8,4,6], "k": 3 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [12,32,12,13,18,38,21,15,13], "k": 95 }
assert my_solution.minIncrementOperations(**test_input) == 214

test_input = { "nums": [17,50,14,27,10,37,24,35,23], "k": 45 }
assert my_solution.minIncrementOperations(**test_input) == 36

test_input = { "nums": [20,17,29,44,18,20,17,26,2], "k": 1 }
assert my_solution.minIncrementOperations(**test_input) == 0

test_input = { "nums": [28,4,38,38,37,13,47,48,49], "k": 61 }
assert my_solution.minIncrementOperations(**test_input) == 60

test_input = { "nums": [29,0,34,5,5,24,43,23,27], "k": 98 }
assert my_solution.minIncrementOperations(**test_input) == 193

test_input = { "nums": [41,53,77,44,79,66,2,46,64], "k": 204 }
assert my_solution.minIncrementOperations(**test_input) == 405