Last Updated: 3 Apr, 2021
Minimum Number of Increments on Subarrays to Form a Target Array
Hard
Asked in companies
You are given two arrays “initial” and “final”. All the elements in the array “initial” are zero initially. And all the elements of the array “final” are positive integers.
You have to find the minimum number of operations to convert the “initial” array into the “final” array using the following operation:
1. In one operation, you can select any contiguous subsequence of the “initial” array and increment each value by 1.
Note :
A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. If S is {5, 15, -30, 10, -5, 40, 10} then 15, -30, 10 is a contiguous subsequence.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains one integer ‘N’ denoting the number of elements in the array.
The second line of each test case contains N space-separated integers denoting the elements of the array “final”.
Output Format :
For each test case, print the minimum number of operations to convert the array “initial” to the array “final” using the given operation.
Print the output of each test case on a new line.
Note :
You don’t need to print anything; It has already been taken care of.
Constraints :
1 <= T <= 5
1 <= N <= 10^5
1 <= final[i] <= 10^9
Where ‘T’ represents the number of test cases, ‘N’ represents the number of elements in the array “final” and final[i] represents the i-th element.
Time Limit: 1 sec
Approaches
The idea here is that when we have a peak element (i.e for two elements at index ‘i’ and index ‘i+1’, final[i+1]-final[i] > 0), we need to perform exactly final[i+1]-final[i] operations to make the two adjacent elements equal..
Example:
initial = [0, 0, 0, 0, 0, 0], final = [1, 2, 3, 2, 1]
i = 0, final[0] is always a peak element so we need to perform exactly one operation to convert 0 to 1.
i = 1, final[1] > final[0] so a peak element,
We need to convert the 0 to 2 here, we can be greedy here as we have already converted initial[0] to final[0], so we can think like we have chosen a subarray starting from 0 to 1 and applied this operation before as it is always optimal to do this. And then apply final[1] - final[0] number of operations to convert it finally.
i = 2, final[2] > final[1] so a peak element,
Therefore, we only need final[2] - final[1] operations.
i = 3, final[3] < final[2] not a peak element,
We skip this iteration because let’s say you have [2,1]. You only need 2 operations here i.e [0, 0] -> [1, 1] -> [2, 1]. As, 2 > 1 It’s always optimal to do [1, 1] -> [2, 1] here rather than [1,0] -> [2, 0] -> [2, 1].
i = 4, final[4] < final[3] not a peak element,
So, we skip this.
The algorithm is as follows:
- Declare a variable ans and initialize it to final[0], where ans represents the minimum number of operations to convert the initial array to the final array.
- Iterate from i = 1 to N - 1,
- If final[i] > final[i - 1],
- Increment ans by final[i] - final[i - 1], as we need to perform exactly final[i] - final[i-1] operations to make initial[i] = final[i].
- If final[i] > final[i - 1],
- Return the ans.