Skip to content

2919. Minimum Increment Operations to Make Array Beautiful 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  long long minIncrementOperations(std::vector<int>& nums, int k) {
    // the minimum operations to increase nums[i - 3] and nums[0..i - 3)
    long prev3 = 0;
    // the minimum operations to increase nums[i - 2] and nums[0..i - 2)
    long prev2 = 0;
    // the minimum operations to increase nums[i - 1] and nums[0..i - 1)
    long prev1 = 0;

    for (const int& num : nums) {
      const long dp = min({prev1, prev2, prev3}) + max(0, k - num);
      prev3 = prev2;
      prev2 = prev1;
      prev1 = dp;
    }

    return min({prev1, prev2, prev3});
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public long minIncrementOperations(int[] nums, int k) {
    // the minimum operations to increase nums[i - 3] and nums[0..i - 3)
    long prev3 = 0;
    // the minimum operations to increase nums[i - 2] and nums[0..i - 2)
    long prev2 = 0;
    // the minimum operations to increase nums[i - 1] and nums[0..i - 1)
    long prev1 = 0;

    for (final int num : nums) {
      final long dp = Math.min(prev1, Math.min(prev2, prev3)) + Math.max(0, k - num);
      prev3 = prev2;
      prev2 = prev1;
      prev1 = dp;
    }

    return Math.min(prev1, Math.min(prev2, prev3));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minIncrementOperations(self, nums: list[int], k: int) -> int:
    # the minimum operations to increase nums[i - 3] and nums[0..i - 3)
    prev3 = 0
    # the minimum operations to increase nums[i - 2] and nums[0..i - 2)
    prev2 = 0
    # the minimum operations to increase nums[i - 1] and nums[0..i - 1)
    prev1 = 0

    for num in nums:
      dp = min(prev1, prev2, prev3) + max(0, k - num)
      prev3 = prev2
      prev2 = prev1
      prev1 = dp

    return min(prev1, prev2, prev3)