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);
}