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 theminimum number of increment operations needed to make _nums beautiful.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5

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 <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

Solution

Method 1 – Sliding Window with Greedy Increment

Intuition

For every subarray of length 3, its maximum must be at least k. To minimize increments, we can use a sliding window of size 3 and ensure that at least one element in each window is at least k. We greedily increment the rightmost element in each window if needed, so that all overlapping windows are covered with minimal operations.

Approach

  1. Iterate through the array with a sliding window of size 3.
  2. For each window, check if its maximum is at least k.
  3. If not, increment the rightmost element in the window to reach k, and count the operations.
  4. Continue to the next window, always updating the array as you go.
  5. Return the total number of operations performed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    long long minIncrementOperations(vector<int>& nums, int k) {
        int n = nums.size();
        long long ans = 0;
        vector<int> arr(nums);
        for (int i = 2; i < n; ++i) {
            int mx = max({arr[i-2], arr[i-1], arr[i]});
            if (mx < k) {
                int need = k - arr[i];
                arr[i] += need;
                ans += need;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func minIncrementOperations(nums []int, k int) int64 {
    n := len(nums)
    arr := make([]int, n)
    copy(arr, nums)
    var ans int64
    for i := 2; i < n; i++ {
        mx := arr[i-2]
        if arr[i-1] > mx { mx = arr[i-1] }
        if arr[i] > mx { mx = arr[i] }
        if mx < k {
            need := k - arr[i]
            arr[i] += need
            ans += int64(need)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        int n = nums.length;
        long ans = 0;
        int[] arr = nums.clone();
        for (int i = 2; i < n; i++) {
            int mx = Math.max(arr[i-2], Math.max(arr[i-1], arr[i]));
            if (mx < k) {
                int need = k - arr[i];
                arr[i] += need;
                ans += need;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minIncrementOperations(nums: IntArray, k: Int): Long {
        val n = nums.size
        val arr = nums.copyOf()
        var ans = 0L
        for (i in 2 until n) {
            val mx = maxOf(arr[i-2], arr[i-1], arr[i])
            if (mx < k) {
                val need = k - arr[i]
                arr[i] += need
                ans += need
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def min_increment_operations(nums: list[int], k: int) -> int:
    n = len(nums)
    arr = nums[:]
    ans = 0
    for i in range(2, n):
        mx = max(arr[i-2], arr[i-1], arr[i])
        if mx < k:
            need = k - arr[i]
            arr[i] += need
            ans += need
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn min_increment_operations(nums: Vec<i32>, k: i32) -> i64 {
        let n = nums.len();
        let mut arr = nums.clone();
        let mut ans = 0i64;
        for i in 2..n {
            let mx = arr[i-2].max(arr[i-1]).max(arr[i]);
            if mx < k {
                let need = k - arr[i];
                arr[i] += need;
                ans += need as i64;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minIncrementOperations(nums: number[], k: number): number {
        const n = nums.length;
        const arr = nums.slice();
        let ans = 0;
        for (let i = 2; i < n; i++) {
            const mx = Math.max(arr[i-2], arr[i-1], arr[i]);
            if (mx < k) {
                const need = k - arr[i];
                arr[i] += need;
                ans += need;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each window is checked once.
  • 🧺 Space complexity: O(n), for the working array.