Minimum Increment Operations to Make Array Beautiful

Medium
1450.

Minimum Increment Operations to Make Array Beautiful

Minimum Increment Operations to Make Array Beautiful is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

You are given an array nums of length n and an integer k. In one operation you pick any index and add 1 to that element.

The array is beautiful when every contiguous subarray of length 3 or more has a maximum of at least k.

Return the minimum number of operations that makes nums beautiful.

The original allows values up to 10^9; here values are capped at 10^4 so the answer always fits in a 32-bit integer.

Example 1

Input
nums = [2,3,0,0,2], k = 4
Output
3
Explanation
Raise `nums[1]` once and `nums[4]` twice: `[2,4,0,0,4]`. Every window of three now contains a 4.

Example 2

Input
nums = [0,1,3,3], k = 5
Output
2
Explanation
Raising `nums[2]` to 5 covers both windows of length 3.

Example 3

Input
nums = [1,1,2], k = 1
Output
0

Constraints

  • 3 <= n == nums.length <= 10^5
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minIncrementOperations = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Increment Operations to Make Array Beautiful Solution

Minimum Increment Operations to Make Array Beautiful solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Increment Operations to Make Array Beautiful is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of length n and an integer k. In one operation you pick any index and add 1 to that element.

The array is beautiful when every contiguous subarray of length 3 or more has a maximum of at least k.

Return the minimum number of operations that makes nums beautiful.

The original allows values up to 10^9; here values are capped at 10^4 so the answer always fits in a 32-bit integer.

Example 1

Input: nums = [2,3,0,0,2], k = 4
Output: 3
Explanation: Raise `nums[1]` once and `nums[4]` twice: `[2,4,0,0,4]`. Every window of three now contains a 4.

Example 2

Input: nums = [0,1,3,3], k = 5
Output: 2
Explanation: Raising `nums[2]` to 5 covers both windows of length 3.

Example 3

Input: nums = [1,1,2], k = 1
Output: 0

Constraints

  • 3 <= n == nums.length <= 10^5
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4

Hints for Minimum Increment Operations to Make Array Beautiful

  1. Hint 1

    A subarray longer than 3 contains a window of length 3, so only the windows of exactly three matter.

  2. Hint 2

    There is never a reason to raise an element above k, and every window of three needs at least one element at k or more.

  3. Hint 3

    Let dp[i] be the cheapest cost when element i is the last one raised to k: it is max(0, k - nums[i]) plus the best of the three previous dp values.

How to solve Minimum Increment Operations to Make Array Beautiful

The condition just says: no three consecutive elements may all stay below k. So we choose a set of positions to lift to k, with gaps of at most two between them — a DP over the last chosen position.

Approach

  1. Let cost(i) = max(0, k - nums[i]), the price of making nums[i] reach k.
  2. dp[i] = cost(i) + min(dp[i-1], dp[i-2], dp[i-3]), where an index before the array counts as 0 — the first three positions may be the first chosen one.
  3. Keep only the last three values in three variables.
  4. The answer is min(dp[n-1], dp[n-2], dp[n-3]): the last chosen position must be within the final window.

Why it works

Raising an element past k or raising two elements of one window is never forced, so an optimal solution lifts a set of positions exactly to k (already-large elements cost 0). The set is valid exactly when every window of three contains one of them, i.e. consecutive chosen positions are at most three apart and the first and last lie in the first and last windows — which is what the recurrence and the final minimum enforce.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Elements already at least k cost nothing — use max(0, k - x), not k - x.
  • The answer is the minimum of the last three states, not just dp[n-1].
  • With the original 10^9 bounds the total needs 64 bits; the tightened bounds keep it in int32.

Reference solution

Python

from typing import List

def minIncrementOperations(nums: List[int], k: int) -> int:
    a = b = c = 0
    for x in nums:
        cur = max(0, k - x) + min(a, b, c)
        a, b, c = b, c, cur
    return min(a, b, c)

Java

public static int minIncrementOperations(int[] nums, int k) {
    long a = 0, b = 0, c = 0;
    for (int x : nums) {
        long cur = Math.max(0, k - x) + Math.min(a, Math.min(b, c));
        a = b; b = c; c = cur;
    }
    return (int) Math.min(a, Math.min(b, c));
}

C++

int minIncrementOperations(vector<int>& nums, int k) {
    long long a = 0, b = 0, c = 0;
    for (int x : nums) {
        long long cur = max(0, k - x) + min(a, min(b, c));
        a = b; b = c; c = cur;
    }
    return (int) min(a, min(b, c));
}

JavaScript

var minIncrementOperations = function(nums, k) {
    var a = 0, b = 0, c = 0;
    for (var i = 0; i < nums.length; i++) {
        var cur = Math.max(0, k - nums[i]) + Math.min(a, b, c);
        a = b; b = c; c = cur;
    }
    return Math.min(a, b, c);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming