Last Updated: 28 Mar, 2021
Sort Array
Moderate
Asked in companies
You are given an array of size ‘n’ to find the minimum number of steps to either convert it into either non-decreasing or non-increasing array. In one step you can either increment or decrement the element of the array.
Input Format
The first line of input contains an integer T, the number
of test cases.
The first line of the test case contains a single integer
‘n’.
The second line contains ‘n’ space integers denoting the
elements of the array.
Output Format
Return the minimum number of steps to convert it into
either a non-decreasing or non-increasing array
Constraints
1<= T <=4
1<= n <=1000
1<= arr[i] <=1000
Where i varies from 1 to ‘n’.
Time Limit : 1 sec
Approaches
The key idea is that the value of a modified array cannot be more than the maximum of the given array and cannot be less than the minimum of the given array. Hence we will consider every case for non-decreasing or non-increasing array separately. The one with minimum steps will be the answer.
Algorithm:-
- Create a base case such that if the current index is equal to the size of the array return 0.
- Create the answer variable with default value infinite.
- We will run a loop from the minimum value to the maximum value of an array. In non-increasing if the value of the current index is ‘i’ then the value of the next index can be from ‘i’ to the minimum(In non-decreasing it will be from ‘i’ to maximum). Thus answer will be the absolute value of ‘i’ and current index value plus the answer from recursion where the maximum is ‘i’.If this value is less than the answer replace the answer with this.
- Return the answer. Similarly, calculate it for non-decreasing. The one with the minimum value will be the answer.
In the First Approach, there are overlapping subcases. Hence we will use dynamic programming to optimize it. In case on non-increasing dp[i][j] represents to make first ‘i’ elements non-increasing when the ith element is ‘j’ and vice versa in non-decreasing.dp[i][j] equals to min(dp[i-1][k]+abs(arr[i]-’j’) where ‘k’ varies from ‘j’ to minimum.Similarly for non-decreasing ‘k’ varies from ‘j’ to maximum.
Algorithm:-
- Calculate for non-decreasing and non-increasing separately.
- Create a dp auxiliary 2-d array of size ‘n’*(Max+1).
- For index=0 dp[0][j]=abs(arr[0]-j).
- Run a loop from i=1 to n. Inside this run a loop from j=minimum to the maximum.
- dp[i][j] equals abs(arr[i]-’j’)+dp[i-1][‘k’] where ‘k’ varies from ‘j’ to minimum.Similarly for non-decreasing ‘k’ varies from ‘j’ to maximum.
- The one with minimum steps between non-decreasing and non-increasing will be the answer.