Here is my solution to New Years Chaos problem from HackerRank. The first solution had a bug:
<pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-js" data-lang="js">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:
<pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-js" data-lang="js">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:
<pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-js" data-lang="js">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 );
}