HackerRank ‘Almost Sorted’ Solution

H
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.

  1. Swap two elements.
  2. 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

Almost Sorted

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:
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)

About the author

Add comment

Archives

Categories