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 ... dnConstraints 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 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 #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()