Minimum Number of Increments on Subarrays to Form a Target Array

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
AppleServiceNow

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 1 1 1 1
5
1 2 3 2 1
Sample Output 1 :
1
3
Explanation of Sample output 1 :
For the first test case, 
The following operations leads to optimal answer
[0, 0, 0, 0, 0] ->       [1, 1, 1, 1, 1]
Therefore the total number of operations are 1.

For the second test case, 
The following operations leads to optimal answer
[0, 0, 0, 0, 0] -> [1, 1, 1, 1, 1] -> [1, 2, 2, 2, 1] -> [1, 2, 3, 2, 1].
Therefore the total number of operations are 3.
Sample Input 2 :
2
2
1 2
5
5 1 3 2 4
Sample output 2 :
2
9
Hint

Find  the peak elements and think of increasing about peak elements.

Approaches (1)
Greedy

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].
  • Return the ans.
Time Complexity

O(N), where N is the size of the array heights.

 

Since we are only iterating from i = 0 to N - 1. Hence the overall time complexity is O(N).

Space Complexity

O(1)

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Minimum Number of Increments on Subarrays to Form a Target Array
Full screen
Console