HackerRank ‘Almost Sorted’ Solution

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:
#!/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.

Facebooktwittergoogle_plusredditpinterestlinkedin