larrysArray.js

// source: https://www.hackerrank.com/challenges/larrys-array/problem
// video: https://youtu.be/XWXVRdpYE0I

function larrysArray(A) {
    // Since each value in the given array is unique we can map backwards
    // the index of each value (allows us to quickly "find" where a desired val is)
    const value_index_map = {}
    for(let i = 0; i < A.length; i++){ // O(n)
        const val = A[i]
        value_index_map[val] = i
    }
    
    // The following 2 functions handle the appropriate 
    // rotation of the given number
    const abc_to_bca = b_val => {
        // given num assumed to be the "b" (number to go leftmost)
        const b_index = value_index_map[b_val]
        
        // get 'a' and 'c' indices
        const a_index = b_index - 1
        const c_index = b_index + 1
        
        const a_val = A[a_index]
        const c_val = A[c_index]
        
        // handle rotation swap
        // update array
        A[a_index] = b_val
        A[b_index] = c_val
        A[c_index] = a_val
        
        // update value_index_map
        value_index_map[b_val] = a_index
        value_index_map[c_val] = b_index
        value_index_map[a_val] = c_index
        // O(1)
    }

    const abc_to_cab = c_val => {
        // given num assumed to be the "c" (number to go leftmost)        
        const c_index = value_index_map[c_val]
        
        // get 'a' and 'c' indices
        const a_index = c_index - 2
        const b_index = c_index - 1
        
        const a_val = A[a_index]
        const b_val = A[b_index]
        
        // handle rotation swap
        // update array
        A[a_index] = c_val
        A[b_index] = a_val
        A[c_index] = b_val
        
        // update value_index_map
        value_index_map[c_val] = a_index
        value_index_map[a_val] = b_index
        value_index_map[b_val] = c_index
        // O(1)
    }

    // The last 3 numbers will be used to assess the final answer
    // but we must process (pre-sort) the other numbers first
    const pre_process_max = A.length - 3 // max num to pre-sort up to

    for (let num = 1; num <= pre_process_max; num++){ // O(n-3) => O(n)
        const proper_num_index = num - 1 // 0-based indexing
        // align number as close as possible to proper_num_index using abc_to_cab
        while(proper_num_index < value_index_map[num] - 1){
            abc_to_cab(num)
        }
        // if necessary, use abc_to_bca to position num into proper_num_index
        if (proper_num_index != value_index_map[num]){
            abc_to_bca(num)
        }
    }
    
    // Assess if last 3 values are in a "rotatable" order
    const last_a_index = value_index_map[pre_process_max + 1]
    const last_b_index = value_index_map[pre_process_max + 2]
    const last_c_index = value_index_map[pre_process_max + 3]
    // already in order A, B, C
    if (last_a_index < last_b_index && last_b_index < last_c_index) return "YES"

    // in rotatable order B, C, A
    if (last_b_index < last_c_index && last_c_index < last_a_index) return "YES"

    // in rotatable order C, A, B
    if (last_c_index < last_a_index && last_a_index < last_b_index) return "YES"
    
    return "NO"
    // Total Time Complexity: O(n) + O(n) = O(2n) => O(n)
}