HackerRank: New Year Chaos

May. 4, 2021

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 ( &#34;Too chaotic&#34; );
            return ;
        }
    }
   console .log (bribes );
}