Menu Close

Check if reversing subarray makes the array sorted.

Given an array of distinct n integers. The task is to check whether reversing one sub-array make the array sorted or not. If the array is already sorted or by reversing a subarray once make it sorted, print array with “yes” or “No”.

INPUT:
[1,2,5,4,3]

Output:
Yes
[1,2,3,4,5]

def revsub(arr):
    N=len(arr)
    L,arr1 = [],arr.copy()
    arr1.sort()
    for i in range(N):
        if(arr[i]!=arr1[i]):
            L.append(i)
            
    L=list(range(L[0],L[-1]+1,1))
    l1,l2 = [],[]
    i,j = 0,0
    
    l1 = arr[L[0]:L[-1]+1]
    l1.reverse()

    while i<N:
        if j<len(L) and i==L[j]:
            l2.append(l1[j])
            j+=1
        else:
            l2.append(arr[i])
        i+=1
        
    return l2

 #DRIVER 
Array=list(map(int,input("Arr: ").split(' ')))

Arr=revsub(Array)
if  Arr == sorted(Array):
    print("Yes \n",Arr)
else:
    print("No \n",Arr)


INPUT_1:
Arr:  2  5  65  55  50  70  90

OUTPUT:
Yes
[ 2,  5,  50,  55,  65,  70,  90 ]


INPUT_2:
Arr:  1  7  6  5  4  3  2  8

OUTPUT:
Yes
[ 1,  2,  3,  4,  5,  6,  7,  8 ]


INPUT_3:
Arr:  1  2  5  4  3

OUTPUT:
Yes
[ 1,  2,  3,  4,  5 ]



INPUT_4:
Arr:  1  2  4  5  3

OUTPUT:
No
[ 1,  2,  3,  5,  4 ]


INPUT_5:
Arr:  11  20  25  30  29  28  26

OUTPUT:
Yes
[ 11,  20,  25,  26,  28,  29,  30 ]


ILLUSTRATION

Executed using python3