Minimum Number Of Increments On Subarrays To Form A Target Array - Leetcode Solution

Problem Statement:

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.

Example:

Input: target = [1,2,3,2,1]

Output: 3

Explanation: We need 3 operations to form the target array from initial.

[0,0,0,0,0] increment 1st element: [1,0,0,0,0]

[1,0,0,0,0] increment 2nd element: [1,2,0,0,0]

[1,2,0,0,0] increment 3rd element: [1,2,3,0,0]

[1,2,3,0,0] increment (1, 4)th elements: [1,2,3,1,1]

[1,2,3,1,1] has been obtained.

Solution:

The problem requires us to find the minimum number of operations required to form target array from the array initial using only the given operation. To solve this problem we can iterate through the given target array and keep track of the maximum value encountered till that index say max_value.

We will have to take into account the previous value in the target array while comparing and adding the difference to our result.

If the current value of the target array at index i is greater than or equal to max_value, then we need to add the difference between current value and max_value to our result and update max_value to current value.

If the current value of the target array at index i is lesser than max_value, we only have to increase the values in the subarray from 0 to i so that they become equal to the current value at index i.

This can be implemented using a counter variable min_op and by updating it appropriately in the above-mentioned operations.

Pseudo Code:

1. Initialize a counter variable min_op

2. Initialize a variable max_value to 0

3. Traverse the array target from start to end using index i

4. If the value of target[i] is greater than or equal to max_value, add (target[i]-max_value) to min_op and update max_value to target[i]

5. If the value of target[i] is lesser than max_value, add (max_value-target[i]) to min_op

6. Return min_op

Implementation:

Here is the python implementation of the above algorithm:

---

class Solution: def minNumberOperations(self, target):

    min_op = target[0]
    n = len(target)
    
    for i in range(1,n):
        if target[i] > target[i-1]:   # If the value of target[i] is greater than the previous value
            min_op += target[i]-target[i-1]  # add the difference to min_op variable
            
    return min_op

---

Time Complexity:

The time complexity of the above algorithm is O(N) where N is the size of the given target array.

Space Complexity:

The space complexity of the above algorithm is O(1) as we are not using any extra data structures to store the intermediate results.

1