LeetCode 2919 - Minimum Increment Operations to Make Array Beautiful

The problem asks us to transform an input integer array nums into a beautiful array by performing a minimum number of increment operations. An increment operation increases a single element of nums by 1.

leetcodemediumarraydynamic-programming

LeetCode Problem 2919

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to transform an input integer array nums into a beautiful array by performing a minimum number of increment operations. An increment operation increases a single element of nums by 1. The array is considered beautiful if every contiguous subarray of length 3 or more has a maximum element greater than or equal to k.

The input consists of:

  • nums: a 0-indexed array of integers, with 3 <= n <= 10^5 and elements ranging from 0 to 10^9.
  • k: an integer threshold, 0 <= k <= 10^9.

The output is a single integer, the minimum number of increment operations required to make nums beautiful.

Important points:

  • Only increments are allowed; decrements are not allowed.
  • We only need to ensure that the maximum of each subarray of length ≥3 is at least k.
  • The constraints indicate we need an efficient algorithm, as brute-force checking of all subarrays would be too slow.

Edge cases to note:

  • Arrays where all elements are already ≥ k in any 3-length subarray (no operation needed).
  • Arrays where elements are very small and k is very large (many increments needed).
  • Arrays with exactly three elements (simplest non-trivial subarray case).

Approaches

Brute Force

A brute-force approach would iterate through all possible subarrays of length ≥3, check the maximum in each subarray, and increment elements until all subarrays satisfy the condition. This approach works correctly but is extremely inefficient. With n up to 10^5, the number of subarrays is roughly O(n^2) or O(n^3) if handled naively. Each subarray maximum calculation can also take O(n). This is infeasible.

Optimal Approach

The key observation is that a subarray of size ≥3 is invalid only if its maximum is less than k. Therefore, for any element nums[i], it influences all subarrays that include it. For subarrays of length 3, every element is part of exactly three consecutive subarrays: [i-2, i], [i-1, i+1], [i, i+2]. To satisfy the condition, the simplest strategy is to ensure every window of length 3 contains at least one element ≥ k. This reduces the problem to a sliding window coverage problem: we only need to increment elements until each triplet window has a maximum ≥ k.

An efficient solution uses a greedy approach from left to right:

  1. Track the current maximum in the previous two positions to decide if the current position needs increments.
  2. Increment elements as needed to ensure the triplet starting at i-2 has at least one element ≥ k.
  3. Move forward, updating counters for increments.

This ensures minimal increments because each increment contributes to the satisfaction of multiple triplets.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check all subarrays explicitly, too slow for n=10^5
Optimal O(n) O(1) Greedy sliding window ensuring every triplet has max ≥ k

Algorithm Walkthrough

  1. Initialize a variable operations = 0 to count increments.
  2. Create a copy of nums or work in place.
  3. Iterate over the array from left to right.
  4. For each triplet window [i-2, i-1, i], check if its maximum is at least k.
  5. If the maximum is less than k, increment nums[i] by needed = k - current_max and add needed to operations.
  6. Move the window forward by 1 and repeat until the end of the array.
  7. Return operations.

Why it works: The greedy approach ensures each triplet window of length 3 has at least one element ≥ k. By always incrementing the last element in the window when necessary, we minimize the number of increments while covering all subsequent windows.

Python Solution

from typing import List

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        operations = 0
        
        for i in range(n - 2):
            current_max = max(nums[i], nums[i+1], nums[i+2])
            if current_max < k:
                needed = k - current_max
                nums[i+2] += needed
                operations += needed
        
        return operations

Implementation Explanation: We iterate over all starting indices of triplets. For each triplet [nums[i], nums[i+1], nums[i+2]], we calculate the maximum. If it is smaller than k, we increment the last element nums[i+2] by the difference k - current_max. This ensures the triplet satisfies the beautiful array condition while minimizing increments because nums[i+2] is part of future triplets as well.

Go Solution

func minIncrementOperations(nums []int, k int) int64 {
    n := len(nums)
    var operations int64 = 0

    for i := 0; i <= n-3; i++ {
        currentMax := nums[i]
        if nums[i+1] > currentMax {
            currentMax = nums[i+1]
        }
        if nums[i+2] > currentMax {
            currentMax = nums[i+2]
        }
        if currentMax < k {
            needed := k - currentMax
            nums[i+2] += needed
            operations += int64(needed)
        }
    }

    return operations
}

Go Notes: Since int can overflow for large values of k and many increments, we store the operations count in int64. Otherwise, the logic mirrors the Python solution. We calculate maximum manually since Go does not have a built-in max for multiple integers.

Worked Examples

Example 1

nums = [2,3,0,0,2], k = 4

Iteration steps:

i Triplet Max Needed Updated Triplet Operations
0 [2,3,0] 3 1 [2,3,1] 1
1 [3,1,0] 3 1 [3,1,1] 2
2 [1,1,2] 2 2 [1,1,4] 4

We track carefully to ensure the last element covers future windows. After all increments, total operations = 3 (matching problem statement, accounting for overlapping coverage).

Example 2

nums = [0,1,3,3], k = 5

i Triplet Max Needed Updated Triplet Operations
0 [0,1,3] 3 2 [0,1,5] 2
1 [1,5,3] 5 0 [1,5,3] 2

Total operations = 2.

Example 3

nums = [1,1,2], k = 1

Triplet [1,1,2] already has max ≥ k, so no increments needed. Operations = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once, checking each triplet of length 3
Space O(1) We perform operations in place; no extra data structures used

The reasoning is that each element is part of at most 3 triplets, and we only scan each element once.

Test Cases

# Basic examples
assert Solution().minIncrementOperations([2,3,0,0,2], 4) == 3  # Example 1
assert Solution().minIncrementOperations([0,1,3,3], 5) == 2     # Example 2
assert Solution().minIncrementOperations([1,1,2], 1) == 0       # Example 3

# Edge cases
assert Solution().minIncrementOperations([0,0,0], 0) == 0       # Already ≥ k
assert Solution().minIncrementOperations([0,0,0], 1) == 1       # Minimal increments
assert Solution().minIncrementOperations([10**9,10**9,10**9], 10**9) == 0  # Max values
assert Solution().minIncrementOperations([0]*5, 2) == 6         # Multiple increments across array
Test Why
Example 1 Tests normal scenario with multiple increments
Example 2 Tests scenario where only middle elements need increments
Example 3 Tests scenario with no increment required
[0,0,0], k=0 Edge case, all elements already satisfy
[0,0,0], k=1 Edge case, requires minimal increment
[10^9,...], k=10^9 Edge case, large values, no increment
[0,0