almost_sorted.js

// source: https://www.hackerrank.com/challenges/almost-sorted/problem
// video: https://youtu.be/deEW0pxWwsA

function almostSorted(arr) {
    const isSortedAroundIndex = index => {
        /*
        Return true if value at and around index are sorted.
        Handles edge "bounces".
        */
        const val = arr[index]
        
        const leftIndex = index - 1
        if(0 <= leftIndex){
            const leftVal = arr[leftIndex]
            if(val < leftVal){
                return false
            }
        }
        
        const rightIndex = index + 1
        if(0 <= rightIndex){
            const rightVal = arr[rightIndex]
            if(rightVal < val){
                return false
            }
        }
        return true
        // O(1)
    }
    
    // Store all indices that are not ordered
    // ex. 1 2 5 4 3
    //       ^ ^      Both 2 and 5 are considered out of order
    const violatorIndices = []
    
    // For each index, if associated value is out of order store index in set 
    for(let i = 0; i < arr.length; i++){ // O(n)
        if(!isSortedAroundIndex(i)){             
            violatorIndices.push(i)
        }
    }
    
    // Assess situation based on violatorIndices
    const indicesIncrement = (prevResult, currVal, i, a) => {
        /*
        Return true if the given array is ascending ordered.
        */
        if(i == 0) return true // skip first value
        const prevVal = a[i - 1]
        return prevResult && (prevVal + 1 == currVal)
        // O(1)
    }
    
    // NOTE: violatorIndices is already sorted, because created in index order
    // if all indices are next to each other, we should consider swapping
    const maybeReverse = violatorIndices.reduce(indicesIncrement, true) // O(n)
    const maybeSwap = violatorIndices.length == 2 || violatorIndices.length == 4
    if(!violatorIndices.length){ // no violations = array already ordered
        console.log('yes')
        return
    }
    if(maybeReverse && violatorIndices.length > 2){ // Check for reverse first!
        // violation count should be greater than 2, otherwise its just a swap
        // all values from smallest to largest index must decrease...
        const smallerIndex = violatorIndices[0] // min
        const largerIndex  = violatorIndices[violatorIndices.length - 1] // max
        
        // O(n)
        for(let i = smallerIndex + 1; i <= largerIndex; i++){ // skipping first val
            const val = arr[i]
            const prevVal = arr[i-1]
            if(prevVal < val){ // if any val is greater than prevVal then too many errors
                console.log("no")
                return
            }
        }
        
        const largeVal = arr[smallerIndex]
        const smallVal = arr[largerIndex]
        let largeValIsValid = true
        let smallValIsValid = true
        // ...AND largeVal must be LESS than the value AFTER largerIndex
        // if no index after largerIndex, reverse is safe for largeVal (goes to end)
        if(largerIndex + 1 < arr.length){
            largeValIsValid = largeVal < arr[largerIndex + 1]
        }
        // AND smallVal must be GREATER than the value BEFORE the smallerIndex  
        // if no index before smallerIndex, reverse is safe for smallVal (goes to start)
        if(0 <= smallerIndex - 1){
            smallValIsValid = arr[smallerIndex - 1] < smallVal
        }
        
        const reverseIsValid = smallValIsValid && largeValIsValid
        if(reverseIsValid){
            console.log("yes")
            console.log(`reverse ${smallerIndex + 1} ${largerIndex + 1}`) // 1-indexing
            return
        }
    }
    if(maybeSwap){
        // possible swaps will show up as either 2 or 4 total violations in order
        // ex: 1 2 7 4 5 6 3 8
        //         ^ ^   ^ ^    Swap is distant
        // ex: 1 2 3 5 4 6 7 8
        //           ^ ^        Swap is close
        // swap the values at min and max index and check if order is restored 
        const smallerIndex = violatorIndices[0] // min
        const largerIndex  = violatorIndices[violatorIndices.length - 1] // max
        
        // swap values inplace
        const smallVal = arr[largerIndex]
        const largeVal = arr[smallerIndex]
        
        arr[smallerIndex] = smallVal
        arr[largerIndex]  = largeVal

        // ensure swapping both numbers worked
        const isSwappable = isSortedAroundIndex(smallerIndex) && isSortedAroundIndex(largerIndex)
        if(isSwappable){
            console.log("yes")
            console.log(`swap ${smallerIndex + 1} ${largerIndex + 1}`) // 1-indexing
            return
        }
        
    }
    // anything else fails
    console.log("no")
    
    // Total Time Complexity: O(n) + O(n) + O(n) = O(3n) => O(n)
}