Hackerrank Solution: Almost Sorted


Given an array with n 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, n, which indicates the size of the array. The next line contains n integers separated by spaces.

n  
d1 d2 ... dn
Constraints 2 ≤ n ≤ 100000 0 ≤ d ≤ 1000000 All d 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. If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then: a. If you can sort the array by swapping dl and dr, output swap l r in the second line. l and r are the indices of the elements to be swapped, assuming that the array is indexed from 1 to n. b. 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 subsequence to be reversed, assuming that the array is indexed from to . 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. If you cannot sort the array in either of the above ways, output no in the first line. Sample Input #1 2 4 2 Sample Output #1 yes swap 1 2 Sample Input #2 3 3 1 2 Sample Output #2 no Sample Input #3 6 1 5 4 3 2 6 Sample Output #3 yes reverse 2 5 Explanation For #1, you can both swap(1, 2) and reverse(1, 2), but if you can sort the array using swap, output swap only. For #2, it is impossible to sort by one single operation (among those permitted). For #3, you can reverse the sub-array d[2...5] = "5 4 3 2", then the array becomes sorted.
def setup():
    array_size = int(input())
    string_array = input()
    int_array = []

    for each_int in string_array.split(' '):
        int_array.append(int(each_int))

    return int_array

def is_ascending(int_array):
    prev_int = int_array[0]
    is_ascending = True
    for each_int in int_array:
        if each_int >= prev_int:
            prev_int = each_int
        else:
            is_ascending = False
            break
    return is_ascending

def is_valid_swap(int_array, j1, j2):
    int_array[j1], int_array[j2] = int_array[j2], int_array[j1]
    return is_ascending(int_array)
    
#This func assumes int_array is not already sorted
#assumes length >= 3
def sort_array(int_array):
    length = len(int_array)
    j1 = None #index one
    j2 = None #index two
    count = 0 #counts how many numbers are in incorrect order
    prev_int = int_array[0] #previous integer to compare
    i = 0 #iterating index

    while i < length:
        curr_int = int_array[i]

        if curr_int >= prev_int:
            prev_int = curr_int

        else:
            if j1: #ie if j1 is not None
                j2 = i
            else:
                j1 = i-1
                j2 = i
            count+=1
            prev_int = curr_int
        i+=1
        
    if j1 and j2: #ie if j1 is not None and j2 is not None
        if count == 2: #aka two numbers need to be swapped that arent next to each other
            print("yes")
            print("swap", j1 + 1, j2 + 1)
            return

        elif count == 1: #aka two numbers next to each other need to be swapped or input isnt possible
            if is_valid_swap(int_array, j1, j2):
                print("yes")
                print("swap", j1 + 1, j2 + 1)
            else:
                print("no")
        else: #aka a portion needs to be reversed or not possible
            if count != j2 - j1:
                print("no")
            else:
                print("yes")
                print("reverse", j1 + 1, j2 + 1)
    else:
        print("no")
    
def main():
    int_array = setup()
    if len(int_array) == 1 or is_ascending(int_array):
        print("yes")
        return
        
    #for now on it can be assumed the array isn't sorted
    elif len(int_array) == 2:
        print("yes")
        print("swap 1 2")
        return
    
    else:
        sort_array(int_array)

if __name__ == "__main__":
    main()