Minimum increment operations to make array beautiful

Array Dynamic Programming

34.7% acceptance

Feb 25, 2026

351

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 >= k. Return an integer denoting the minimum number of increment operations needed to make nums beautiful.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_increment_operations(nums: Vec<i32>, k: i32) -> i64 {
    // dp[j] = min cost where j in {0,1,2} is number of trailing elements < k
    let mut dp = [0i64, i64::MAX / 2, i64::MAX / 2];

    for &x in &nums {
      let cost_raise = 0i64.max((k - x) as i64);
      let already_ok = x >= k;
      let mut new_dp = [i64::MAX / 2; 3];

      // Option: make this element >= k
      new_dp[0] = dp[0].min(dp[1]).min(dp[2]) + cost_raise;

      if !already_ok {
        // Option: leave this element < k
        new_dp[1] = dp[0]; // prev had 0 trailing < k
        new_dp[2] = dp[1]; // prev had 1 trailing < k (now 2)
        // dp[2] + 0 would give 3 trailing < k, not allowed
      }

      dp = new_dp;
    }

    dp[0].min(dp[1]).min(dp[2])
  }
}