We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Increment Operations to Make Array Beautiful

Number: 3178

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array nums and an integer k, you may increment any element by 1 any number of times. An array is considered beautiful if every subarray of length 3 or more has at least one element with a value greater than or equal to k. Return the minimum number of increments required to make nums beautiful.

Key Insights

  • The condition “beautiful” is equivalent to ensuring no three consecutive elements are all less than k.
  • Some array elements may already be at least k (they incur no cost) and automatically “cover” nearby windows.
  • For any element that is less than k, you have two options: leave it as is (if allowed by the “no three consecutive fails” rule) or upgrade it by incrementing it until it reaches k (which costs exactly k – nums[i]).
  • A dynamic programming approach can be designed that processes the array sequentially while keeping track of the count of consecutive indices that are not “good” (i.e. less than k and not upgraded).
  • The state is small (only need to track the last 0, 1, or 2 consecutive “bad” elements), so the solution runs in O(n) time and O(1) space.

Space and Time Complexity

Time Complexity: O(n) – We process every element once. Space Complexity: O(1) – Only a few state variables are maintained.

Solution

We can reformulate the problem by thinking of it as ensuring that in the resulting array (after some upgrades) there are no three consecutive indices whose value is below k. For each index i, if nums[i] is already at least k, then no action is needed. Otherwise, we have a choice:

  1. Do nothing and mark the index as “bad” (value still < k). This move is only allowed if it does not create a run of 3 bad elements.
  2. Upgrade the number at index i (by adding k – nums[i] to it) to “good” so that its value becomes k; this resets the bad streak count to 0.

We define dp[i][r] as the minimum cost required after processing the i-th element with r consecutive “bad” elements at the end (r can be 0, 1, or 2). We iterate from left to right. Whenever nums[i] is already at least k, we have no cost and can reset the consecutive bad count to 0. For a “not naturally good” element, we try both leaving it (if doing so does not result in 3 consecutive bad indices) and upgrading it (accumulating the cost of (k – nums[i]) and resetting the bad streak). Finally, the answer is the minimum cost among all valid ending states.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java. Each solution includes line-by-line comments.

# Python solution for Minimum Increment Operations to Make Array Beautiful
def minOperations(nums, k):
    n = len(nums)
    
    # dp[r] represents the minimum cost so far with `r` consecutive bad indices at the end.
    # r can be 0, 1, or 2.
    dp = [0, float('inf'), float('inf')]
    
    for num in nums:
        new_dp = [float('inf')] * 3
        # Check if current number is naturally good (>= k)
        if num >= k:
            # If naturally good, cost is 0 and resets the streak of bad elements.
            m = min(dp)
            new_dp[0] = m
        else:
            # Option 1: Upgrade current index to become good.
            # This costs (k - num) and resets the streak to 0.
            min_cost = min(dp)
            new_dp[0] = min_cost + (k - num)
            
            # Option 2: Do not upgrade if allowed.
            # We can only leave the element as "bad" if we have less than 2 consecutive bads so far.
            # Try extending the streak for each valid previous state.
            for r in range(2):  # r=0 or r=1
                if dp[r] != float('inf'):
                    # Increase streak by 1.
                    new_dp[r + 1] = min(new_dp[r + 1], dp[r])
        dp = new_dp
    return min(dp)

# Example usage:
print(minOperations([2,3,0,0,2], 4))  # Output: 3
print(minOperations([0,1,3,3], 5))      # Output: 2
← Back to All Questions