MikeJamesHamm

Student, Developer, Technology Advocate
Welcome to my personal website



Hackerrank Solution: Almost Sorted

on Oct. 31, 2016, 6:16 p.m.

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




The code listed above may or may not be the "best" solution. Please be advised that this is just the way I did it. There are normally thousands of different ways to solve the same programming problem. Find an error? Let me know in the contact form below.




Contact Me

Feel free to email me feedback, suggestions, notes, or to just say hello!