You are viewing a single comment's thread. Return to all comments →
(Updated) O(n) solution without sorting
def almostSorted(arr): def check_sorted(A): for i in range(len(A)-1): if A[i] > A[i+1]: return False return True def validate_left(i): arr[i-1], arr[i] = arr[i], arr[i-1] res = False if check_sorted(arr): res = True arr[i-1], arr[i] = arr[i], arr[i-1] return res def validate_right(i): arr[i], arr[i+1] = arr[i+1], arr[i] res = False if check_sorted(arr): res = True arr[i], arr[i+1] = arr[i+1], arr[i] return res # Write your code here n = len(arr) inv_idx = [] for i in range(n-1): if arr[i] > arr[i+1]: inv_idx.append(i) num_inversion = len(inv_idx) if num_inversion == 0: print('yes') return if num_inversion == 1: p = inv_idx[0] res = [] if p != 0 and validate_left(p): res = [p-1, p] elif p != n-1 and validate_right(p): res = [p, p+1] if res: print(f'yes\nswap {res[0]+1} {res[1]+1}') else: print('no') return if num_inversion == 2: arr[inv_idx[0]], arr[inv_idx[1]+1] = arr[inv_idx[1]+1], arr[inv_idx[0]] if check_sorted(arr): print(f'yes\nswap {inv_idx[0]+1} {inv_idx[1]+2}') else: print('no') arr[inv_idx[0]], arr[inv_idx[1]+1] = arr[inv_idx[1]+1], arr[inv_idx[0]] return # updated reverse check for i in range((num_inversion+1)//2): arr[inv_idx[i]], arr[inv_idx[-i-1]+1] = arr[inv_idx[-i-1]+1], arr[inv_idx[i]] if check_sorted(arr): print(f'yes\nreverse {inv_idx[0]+1} {inv_idx[-1]+2}') else: print('no') return
Seems like cookies are disabled on this browser, please enable them to open this website
Almost Sorted
You are viewing a single comment's thread. Return to all comments →
(Updated) O(n) solution without sorting