HackerRank: New Year Chaos

Here is my solution to New Years Chaos problem from HackerRank. The first solution had a bug:

function minimumBribes(q) {
    let bribes = 0;
    
    for (let i=0; i<q.length-2; i++) {
        if (q[i] - (i+1) > 2) {
            console.log('Too chaotic');
            return;
        }
        // compare index to element, works great except when a smaller element is pushed way back
        if (q[i] - (i+1) > 0) {
          bribes += q[i] - (i+1);
        } 
    }
    console.log(bribes);
}

Second solution had O(n^2) complexity:

function minimumBribes(q) {
    let bribes = 0;
    
    for (let i=0; i<q.length; i++) {
        if (q[i] - (i+1) > 2) {
            console.log('Too chaotic');
            return;
        }
        // if there is a bigger  element before this element
        // then that element must have bribed this element
        for (let j=0; j<i; j++) {
            if (q[i]<q[j]) {
                bribes++;
            }
        }
    }
    console.log(bribes);
}

At this point, I looked up in comments and found an optimal solution:

function minimumBribes(q) {
    let bribes = 0;
    let expectedFirst = 1;
    let expectedSecond = 2;
    let expectedThird = 3;
    
    for (let i=0; i<q.length-0; i++) {
        if (q[i] == expectedFirst) {
            expectedFirst = expectedSecond;
            expectedSecond = expectedThird;
            ++expectedThird;
        } else if (q[i] == expectedSecond) {
            ++bribes;
            expectedSecond = expectedThird;
            ++expectedThird;
        } else if (q[i] == expectedThird) {
            bribes += 2;
            ++expectedThird;
        } else {
            console.log("Too chaotic");
            return;
        }
    }
    console.log(bribes);
}

Leave a Reply