2919. Minimum Increment Operations to Make Array Beautiful

MediumArrayDynamic Programming
Leetcode Link

Problem Description

This problem involves an integer array nums which is 0-indexed and has length n. Along with the array, you're given an integer k. You have the ability to execute an increment operation on any element of the array. The increment operation involves choosing an index i (where i ranges from 0 to n - 1) and increasing nums[i] by 1.

The main goal is to perform as few operations as possible so that the array becomes beautiful. An array is deemed beautiful if any subarray of size 3 or more contains at least one element that is greater than or equal to k. A subarray, by definition, is a contiguous non-empty sequence within the array.

You are asked to determine and return the minimum number of increment operations required to make the nums array beautiful.

Intuition

For this problem, we utilize a dynamic programming approach, keeping track of a set of variables f, g, and h. These variables represent the minimum increment operations needed to get at least one element equal to or greater than k in the last three elements of each subarray within the array.

We initialize f, g, and h to 0, as no operations have been performed yet. We then iterate over the array nums and for each element x, we perform the following:

  • We update f to the old value of g because f stands for the minimum operations considering the subarray ending one element before the current one.
  • Similarly, g is updated to the old value of h to move the window one step ahead.
  • h is updated to be the minimum of the previous f, g, and h plus the number of operations required to make the current element x greater than or equal to k. If x is already greater than or equal to k, no operations are needed (max(k - x, 0) ensures this).

By iterating in this manner, we make sure to consider the minimum required operations for each element while taking the previous elements into account, leading us to the solution for the entire array.

In the end, since we only care about any subarray of size 3 or more being beautiful, we return the minimum of f, g, and h, which represents the fewest number of operations needed across all considered subarrays.

Learn more about Dynamic Programming patterns.

Solution Approach

In the implemented solution, the dynamic programming approach is key. The algorithm avoids the need for a traditional 2D dynamic programming table that would take into account every subarray by using three variables f, g, and h to store states. This is an example of space optimization within dynamic programming.

The algorithm processes the array nums from left to right. As described previously, f is the count of increment operations for the subarray ending two elements before the current, g is for the subarray ending one element before the current, and h is for the subarray ending with the current element.

Let's take a closer look at how we update these three states as we iterate through each element, x, in nums:

  • We first store the old values of g and h. These represent the best solutions (minimum operation count) for subarrays ending one and two elements before x.
  • We update f to be equal to the old value of g. This is assuming that for the next element, f will represent the best previous solution excluding the current element (x).
  • The old value of h becomes the new g, adjusting the window to include x.
  • To calculate the new value for h, we find the minimum among the old values of f, g, and h, and add the number of operations needed to make x at least k. The expression max(k - x, 0) yields the number of operations needed—if x is already equal to or larger than k, no operations are required, hence the max function ensures that the increment is zero in such cases.
  • The dynamic update for h is h = min(f, g, h) + max(k - x, 0).

By performing the above steps for each element in nums, we continually update the count of required operations for all relevant subarrays. This way, we achieve an O(n) time complexity since we pass through the array only once without the need for a nested loop.

At the code's conclusion, we return the minimum operations needed across all subarrays of size 3 or greater, which is the least of f, g, and h after processing all elements of nums. This final step delivers the minimum number of increment operations needed to make the array beautiful.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with the array nums = [1, 2, 3, 4] and k = 5. We want to find the minimum number of increment operations to make the array beautiful according to our problem description.

Applying the solution approach described:

  1. We initialize f = g = h = 0 because no operations have been carried out yet, and we are looking at the subarrays ending before the first element.
  2. We look at the first element of nums which is 1. Since k = 5, the number of operations to make 1 at least 5 is 5 - 1 = 4.
    • We update h to min(f, g, h) + max(5 - 1, 0) = min(0, 0, 0) + 4 = 4.
    • Now, f remains 0, g remains 0, and h becomes 4.
  3. We move to the second element, 2. We first need to update our variables:
    • f becomes the old g, which is 0.
    • g becomes the old h, which is 4.
    • The number of operations to make 2 at least 5 is 5 - 2 = 3.
    • Update h with h = min(f, g, h) + max(5 - 2, 0) = min(0, 4, 4) + 3 = 3.
    • Now, f is 0, g is 4, and h is 3.
  4. Next, we look at the third element, 3. Again, update the variables:
    • f becomes the old g, which is 4.
    • g becomes the old h, which is 3.
    • The number of operations for 3 is 5 - 3 = 2.
    • Update h with h = min(f, g, h) + max(5 - 3, 0) = min(4, 3, 3) + 2 = 3 + 2 = 5.
    • After this, f is 4, g is 3, and h is 5.
  5. Lastly, we consider the fourth element, 4:
    • Update f to the old value of g, which is 3.
    • Update g to the old value of h, which is 5.
    • The number of operations to make 4 at least 5 is 5 - 4 = 1.
    • Update h with h = min(f, g, h) + max(5 - 4, 0) = min(3, 5, 5) + 1 = 3 + 1 = 4.
    • The final values are f is 3, g is 5, and h is 4.

Given our variables, the minimum of f, g, and h will give us the least number of operations needed. In this case:

  • The minimum number of operations required is min(f, g, h) = min(3, 5, 4) = 3.

Therefore, according to our solution approach and this example, we would need a minimum of 3 operations to make the array nums beautiful.

Solution Implementation

1class Solution:
2    def minIncrementOperations(self, nums: List[int], k: int) -> int:
3        # Initialize the dp variables for the minimum operations
4        # needed to make the previous, current, and next numbers at least 'k'.
5        prev_op_count = cur_op_count = next_op_count = 0
6
7        # Loop through each number in the array to calculate the
8        # minimum operations required.
9        for num in nums:
10            # Update the minimum operation counts for the three states
11            # State transitions:
12            # prev_op_count -> the previous minimum operation count
13            # cur_op_count -> the current minimum operation count
14            # next_op_count -> the estimated operation count for next number
15            prev_op_count, cur_op_count, next_op_count = \
16                cur_op_count, next_op_count, min(prev_op_count, cur_op_count, next_op_count) + max(k - num, 0)
17
18        # Return the minimum of the three states' operation counts as
19        # that would be the minimum operations needed for the entire array.
20        return min(prev_op_count, cur_op_count, next_op_count)
21
1class Solution {
2    public long minIncrementOperations(int[] nums, int k) {
3        long firstPrevOperationCount = 0; // Initialize previous counts for recursive state
4        long secondPrevOperationCount = 0;
5        long currentOperationCount = 0;
6
7        // Iterate over the array of numbers
8        for (int number : nums) {
9            // Calculate the minimum count of operations required for the current number.
10            // This involves taking the minimum count from the previous two iterations
11            // and adding the required increments to reach at least k.
12            long optimalCurrentOperationCount = Math.min(
13                Math.min(firstPrevOperationCount, secondPrevOperationCount),
14                currentOperationCount
15            ) + Math.max(k - number, 0);
16
17            // Shift the operation counts for the next iteration.
18            // The second previous becomes the first previous,
19            // the current becomes the second previous,
20            // and the new current count is calculated above.
21            firstPrevOperationCount = secondPrevOperationCount;
22            secondPrevOperationCount = currentOperationCount;
23            currentOperationCount = optimalCurrentOperationCount;
24        }
25
26        // Return the minimum count of operations amongst the last three counts.
27        return Math.min(
28            Math.min(firstPrevOperationCount, secondPrevOperationCount),
29            currentOperationCount
30        );
31    }
32}
33
1#include <vector>
2#include <algorithm> // for std::min and std::max
3
4class Solution {
5public:
6    long long minIncrementOperations(std::vector<int>& nums, int k) {
7        // Initialize the variables to store the minimal operations count for the last 3 increments
8        long long prevPrevCount = 0; // f represents the count 2 steps before
9        long long prevCount = 0;     // g represents the count 1 step before
10        long long currCount = 0;     // h represents the current count
11
12        // Iterate over the values in the 'nums' array
13        for (int x : nums) {
14            // Calculate the minimal operations needed for the current element
15            // It's the minimum out of the last three results plus any increments needed to reach 'k'
16            long long newCurrCount = std::min({prevPrevCount, prevCount, currCount}) + std::max(k - x, 0);
17
18            // Shift the counts for the next iteration
19            prevPrevCount = prevCount;
20            prevCount = currCount;
21            currCount = newCurrCount;
22        }
23
24        // The final answer is the minimal operations count out of the last three calculations
25        return std::min({prevPrevCount, prevCount, currCount});
26    }
27};
28
1function minIncrementOperations(nums: number[], k: number): number {
2    // Initialize three variables to store intermediate results.
3    let [minOp1, minOp2, minOp3] = [0, 0, 0];
4  
5    // Loop through the array of numbers to determine the minimal operations needed.
6    for (const number of nums) {
7        // Update the variables to store the minimal operations.
8        // minOp3 holds the result of the current computation,
9        // which is the minimal of the previous computations (minOp1, minOp2, minOp3) plus
10        // the max between 0 and (k - current number), ensuring we never subtract.
11        [minOp1, minOp2, minOp3] = [
12            minOp2, 
13            minOp3, 
14            Math.min(minOp1, minOp2, minOp3) + Math.max(k - number, 0)
15        ];
16    }
17  
18    // Return the minimum of the three variables, which represents the minimum operations required.
19    return Math.min(minOp1, minOp2, minOp3);
20}
21

Time and Space Complexity

The time complexity of the provided code is O(n) where n is the length of the input list nums. This is because the code iterates over the list nums exactly once, and within each iteration, it performs a constant number of operations that include comparisons and basic arithmetic, which do not depend on the size of the list.

The space complexity of the code is O(1). Despite the size of the input, the code uses a fixed amount of space, represented by the variables f, g, and h. No matter how large the input list is, these variables do not require any additional space that scales with the size of the input. Hence the space required by the algorithm remains constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More