Almost Sorted

Given an array with  elements, can you sort this array in ascending order using only one of the following operations?

1. Swap two elements.
2. Reverse one sub-segment.

Input Format 
The first line contains a single integer, , which indicates the size of the array. 
The next line contains  integers separated by spaces.

n  
d1 d2 ... dn  

Constraints 
 
  
All  are distinct.

Output Format 

1. If the array is already sorted, output yes on the first line. You do not need to output anything else.
2. If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:
   • If you can sort the array by swapping  and , output swap l r in the second line.  and  are the indices of the elements to be swapped, assuming that the array is indexed from  to .
   •   Else if it is possible to sort the array by reversing the segment d [l....r] , output reverse l r in the second line. l and r are the indices of the first and last elements of the sub-sequence to be reversed, assuming that the array is indexed from 1 to n.
   •  represents the sub-sequence of the array, beginning at index  and ending at index , both inclusive.  d [l....r] represents the sub-sequence of the array, beginning at index l and ending at index r , both inclusive.
   • If an array can be sorted by either swapping or reversing, stick to the swap-based method.
3. If you cannot sort the array in either of the above ways, output no in the first line

Here are my tips.

1. Create a dynamic Array A of size n+2, input the values in the array with A[0]=0 and A[ n+2] =max_value of n.
2. Starting from index 1, loop through it till you get the first anomaly (i.e when A[ i ]>A[ i+1] ) take note of the index and break the loop.
3. Now starting from index n till index j, loop though it and check for all the anomaly, take the index of the first anomaly. Now take note of all the anomaly whether it's a peak or valley as well as number of anomaly (peak in case when A[ i ]>A[ i+1] && A[ i ] >A[ i-1] and valley is case when A[ i ]<A[ i+1] && A[ i ] <A[ i-1] ). See my code below for more clarification. Keep track of the index of the peak/valley  with the help of a vector.
4. Now if the output is yes than the following will be true.
   1. if no anomaly than the array is already sorted.
   2. swap when the there are exactly 1 peak and 1 valley  OR 2 peaks and 2 valleys and difference between the consecutive index of a peak and a valley is 1.
   3. reverse when only 1 peak and 1 valley and the difference between the their index is not 1.
5.  if all of 4 is not there than we cannot sort the array in one operation so output "no".

Here are few sample input to boost your thinking.

Input:

6

1 5 4 3 2 6

Output : reverse 2 5

Input

9

1 2 9 4 5 6 7 8 3

Output: swap 3 9

Input

9

1 2 9 4 5 8 7 6 3

Output: no

Input:

10

1 2 10 4 5 8 7 6 9 3

Output: no

Input

5

1 2 4 3 5

Output: swap 2 5

 My solution:

#include <iostream>

#include <vector>

using namespace std;

int main() {

    int n,j=0,k=0,count=0,dn=0,up=0; /*initializing j and k to take note of the first anomaly from beginning and end, count to keep track of the number of anomaly, dn for valley and up for peak */ 

    cin>>n;

    vector<int> s;

    int* A=new int[n+2]; /* initializing a dynamic array A of size n+2 */

    A[0]=0;                        /* assigning A[0] =0 */

    for(int i=1 ; i<=n; i++){

        cin>>A[ i ];               /* Filling the array */

    }

    A[n+1]=1000001;       /* assigning A[n+1]= Max_value of n i.e 100001 */

    for(int i=1 ; i<=n-1 ; i++){        

         if(A[ i ]>A[ i+1] ){

                if(count==0){j=i ;count++ ;break ;    /* searching for first anomaly from index 1 */

        }    

     }}

    for(int i=n ; i>j-1 ;i--){

       if(A[i]<A[i-1]){              

               if(count==1){               /* searching for first anomaly from index n */

                          k=i ; dn++ ; s.push_back(i); /* taking note of the first anomaly from the end  i.e. k=i . this will be a valley so increasing the value of dn by 1 and also noting it's index in the vector*/

               } 

                if(A[ i ]<A[ i+1] && count>1){

                         dn++ ; s.push_back(i);          /* counting the number of valley's and noting their index in the vector */ 

                } 

                count++;   /* counting the number of anomaly */

        }

            

         if(A[ i ]>A[ i+1 ] && A[ i ]>A[ i-1]){

                up++; s.push_back(i);        /* counting the number of peaks and noting their index  in the vector*/

         } 

    }

     if(count==0){cout<<"yes";}     /* if  no anomaly */

     else if(n==2){

            if(A[1]>A[2])cout<<"yes"<<endl<<"swap "<<1<<" "<<2;  

          /* if n=2 than we can directly compare the values and output accordingly */

        }

    else if(A[ j ]<A[ k+1] && A[ k]>A[ j-1] && ((s.size()==4 &&s[0]-s[1]==1 && s[2]-s[3]==1)|| (s.size()==2 && s[0]-s[1]==1)) ) {

                cout<<"yes"<<endl<<"swap "<<j<<" "<<k; 

  /* this is a very big condition so take a look properly, remember that j is the first anomaly from beginning and k is the first anomaly from the end. After swap, the array will be sorted only when A[ j ]<A[ k+1] && A[ k]>A[ j-1]  and  i have already explained the other conditions in the points above */

    }   

   else if(A[ j ]<A[k+1] && A[k]>A[ j-1]  &&  count==(k-j+1))

                cout<<"yes"<<endl<<"reverse "<<j<<" "<<k;

/* Reverse operation will be applicable only when number of anomaly i.e. count is equal to the difference in their index +1 i.e. ( count =k-j+1 ), see the sample input's for more clarification */

            

        else cout<<"no"; /* if all the above are not true than we cannot sort the array in one operation */

    

    return 0;

}

*****

If you have a better solution in mind than please do share it in the comment section below   

Want me to explain any particular question, than comment below

*****

Question source : hackerrank.com