Sort Array

Moderate
0/80
Average time to solve is 35m
9 upvotes
Asked in companies
AppleAmerican ExpressDell Technologies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
4
3 1 3 1
5
1 2 3 4 5
Sample Output1
2
0

Explanation:

For First TestCase We can convert the array into 
{3,1,1,1} by decrementing 3 to 1.
Hence steps are 3-1=2
For Second TestCase
It is already in non-decreasing order. Hence steps are 0.
Sample Input 2
2
4
2 2 1 3
5
5 4 3 2 1
Sample Output 2
1
0
Hint

 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.

Approaches (2)
Recursive Approach

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.
Time Complexity

O((maximum-minimum)^n)

In every index, we are calling recursion maximum-minimum times. Hence time complexity will be (maximum-minimum)^n where ‘n’ is the size of the array, maximum is the maximum value in the array and minimum is the minimum value of the array.

Space Complexity

O(1)

We are using constant space to solve this.

Code Solution
(100% EXP penalty)
Sort Array
Full screen
Console