Sort by

recency

|

520 Discussions

|

  • + 1 comment

    python solution:

    def get_range(arr):
        l = r = count = 0
        for i in range(len(arr) - 1):
            if arr[i] > arr[i+1]:
                if count == 0:
                    l = i
                count += 1
                r = i + 1
        return (l, r, count)
    
    def check_neighbors(idx, val):
        return not (idx > 0 and arr[idx-1] > val or idx < n - 1 and arr[idx+1] < val)
    
    def can_be_sorted(arr):
        l, r, count = get_range(arr)
        if count == 0:
            return 'yes', 
        
        if check_neighbors(l, arr[r]) and check_neighbors(r, arr[l]):
            if count <= 2:
                return 'yes', f'swap {l+1} {r+1}'
            if r - l == count:
                return 'yes', f'reverse {l+1} {r+1}'
        return 'no',
        
    
  • + 0 comments

    Python3 Solution

    def reverse(arr, a, b):
        while a < b:
            temp = arr[a]
            arr[a] = arr[b]
            arr[b] = temp
            a += 1
            b -= 1
        
        return arr
        
    def isReversePossible(arr, sortedArr):
        possibleReverse = []
        pointer = 0
        while pointer < len(arr):
            if pointer < len(arr)-1 and arr[pointer] > arr[pointer+1]:
                a = pointer
                while pointer < len(arr)-1 and arr[pointer] > arr[pointer+1]:
                    pointer += 1 
                    
                b = pointer
                
                possibleReverse.append([a, b])
            else:
                pointer += 1
        
        for a, b in possibleReverse:
            if reverse(arr.copy(), a, b) == sortedArr:
                print("yes")
                print(f"reverse {a+1} {b+1}")
                return True
        
        
        return False
    
    def isSwapPossible(arr, sortedArr):
        possibleSwap = []
        for i in range(len(arr)):
            if arr[i] != sortedArr[i]:
                possibleSwap.append(i)
    
        if len(possibleSwap) > 2:
            return False
        a = possibleSwap[0]+1
        b = possibleSwap[1]+1
        
        print("yes")
        print(f"swap {a} {b}")
        return True
        
        
    def almostSorted(arr):
        sortedArr = sorted(arr)
        if arr == sortedArr:
            print("no")
            return
        
        if isSwapPossible(arr.copy(), sortedArr):
            return
            
        if isReversePossible(arr.copy(), sortedArr):
            return
    
        
        print("no")
    
  • + 0 comments

    Able to solve this in O(nlogn) time, is there better solution could possible for this problem? If someone knows help me to solve

  • + 0 comments

    D'oh!

    Here is the case that tricked me: almost sorted except for a range to be reversed, and that range is an odd length so the middle element is in the same order in the "almost" and "fully" sorted arrays.

    I was "seeing" that as two spans that needed adjustment so it looked "almost alomost" sorted and I rejected it when I should have passed it.

    Like most bug easy to fix once you realize the root cause.

  • + 0 comments

    D'oh!

    Here is the case that tricked me: almost sorted except for a range to be reversed, and that range is an odd length so the middle element is in the same order in the "almost" and "fully" sorted arrays.

    I was "seeing" that as two spans that needed adjustment so it looked "almost alomost" sorted and I rejected it when I should have passed it.

    Like most bug easy to fix once you realize the root cause.