##### Short Problem Definition:

Given an array of integers, determine whether the array can be sorted in *ascending order* using only one of the following operations one time.

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

Determine whether one, both or neither of the operations will complete the task. If both work, choose *swap*. For instance, given an array [2, 3, 5, 4] either swap the 4 and 5; or reverse them to sort the array. Choose swap.

##### Link

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

I wrote this code 4 years ago and I already have no clue what it does. It is linear time and it works even today.

Today, I would have broken this logic down into smaller functions with clear purpose.

If you have solved this in a readable way, please share!

##### Solution:

#!/usr/bin/py def getReverseAction(arr): is_sorted = True low_idx = 0 high_idx = len(arr)-1 while (low_idx < high_idx and arr[low_idx] < arr[low_idx+1]): low_idx += 1 if low_idx == high_idx: print "yes" return while (high_idx > 0 and arr[high_idx] > arr[high_idx-1]): high_idx -= 1 #print "low", low_idx, arr[low_idx] #print "high", high_idx, arr[high_idx] if low_idx == 0 or arr[high_idx] > arr[low_idx -1]: #print "high index swapable" if arr[high_idx] < arr[low_idx +1] or low_idx+1 == high_idx: #print "high index swapable" if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]: #print "low index swapable" if arr[low_idx] > arr[high_idx -1] or low_idx == high_idx-1: #print "low index swapable" low_idx_runner = low_idx+1 while (low_idx_runner < high_idx and arr[low_idx_runner] < arr[low_idx_runner+1]): low_idx_runner += 1 if low_idx_runner == high_idx-1 or low_idx == high_idx-1: print "yes" print "swap", low_idx+1, high_idx+1 return low_idx_runner = low_idx+1 while (low_idx_runner < high_idx and arr[low_idx_runner] > arr[low_idx_runner+1]): low_idx_runner += 1 if low_idx_runner == high_idx: if low_idx == 0 or arr[high_idx] > arr[low_idx -1]: if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]: print "yes" print "reverse", low_idx+1, high_idx+1 return print "no" if __name__ == '__main__': n = input() arr = map(int, raw_input().split()) getReverseAction(arr)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.