Minimum Increment Operations to Make Array Beautiful

Minimum Increment Operations to Make Array Beautiful - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,0,0,2], k = 4

› Output: 8

💡 Note: For window [2,3,0], max=3<4, so increment nums[2] to 4 (cost: 4). For window [3,4,0], max=4≥4, no change. For window [4,0,0], max=4≥4, no change. For window [0,0,2], max=2<4, so increment nums[4] to 4 (cost: 2). Total: 4+4=8 operations.

Example 2 — Already Beautiful

$ Input: nums = [0,0,0,4], k = 4

› Output: 0

💡 Note: The only window of size 3+ is [0,0,0,4] which has max=4≥k=4, so no operations needed.

Example 3 — Small Array

$ Input: nums = [1,2], k = 10

› Output: 0

💡 Note: Array has length < 3, so no subarray of size 3+ exists. Already beautiful by definition.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is that we only need to ensure every consecutive triplet has at least one element ≥ k. The greedy approach works optimally: scan left to right, and whenever a window [i-2,i-1,i] violates the constraint, increment the rightmost element nums[i] to k. This is optimal because incrementing the rightmost position affects the fewest future constraints. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n)	O(1)	Process array left to right, ensuring every 3-element window has one element >= k
Dynamic Programming	O(n²)	O(n)	Use DP to track minimum cost for different ending positions
Check All Subarrays	O(n³)	O(1)	Check every subarray of length 3+ and fix violations greedily

Greedy Approach — Algorithm Steps

Step 1: Iterate through array starting from index 2
Step 2: For each position i, check window [i-2, i-1, i]
Step 3: If max in window < k, increment nums[i] to k
Step 4: Count all increment operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Window

For each position i≥2, check window [i-2,i-1,i]

Greedy Choice

If max < k, increment rightmost element to k

Continue

Move to next position and repeat

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max3(int a, int b, int c) {
    int max_val = a;
    if (b > max_val) max_val = b;
    if (c > max_val) max_val = c;
    return max_val;
}

long long solution(int* nums, int numsSize, int k) {
    if (numsSize < 3) return 0;
    
    long long operations = 0;
    
    for (int i = 2; i < numsSize; i++) {
        // Check if window [i-2, i-1, i] has any element >= k
        int windowMax = max3(nums[i-2], nums[i-1], nums[i]);
        if (windowMax < k) {
            // Increment nums[i] to k (greedy choice)
            long long diff = k - nums[i];
            nums[i] = k;
            operations += diff;
        }
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for counting operations

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler