Find the number of swaps that has taken place. New Year Chaos. Hackerrank I am trying to solve the following Hackerrank Problem.



I have written the code for the problem. However, it runs for some of the test cases while for others it doesn't. It shows the message : "Your code did not execute within the time limits"

I know that bubble sort is not required for the problem. However, I have seen many people doing it using bubble sort.

I want to do the problem by employing bubble sort. Please tell me what changes do I need to make in the code in order to do so. Thanks for helping.

int N = 0 ,I = 0;
        int flag = 0;

        int n = q.length;  
        int temp = 0; 
        int noOfSwaps = 0;

        for(int i = 0 ; i &lt; q.length ; i++)
        {
            N = q[i];
            I = i;
            if((N-I)&gt;3)
            {
                flag = 1;
                break;
            }
        }

        if(flag == 1)
        {
            System.out.println("Too chaotic");
        }
        else if(flag == 0)
        {
            //System.out.println("Find Exchanges");      

         for(int i=0; i &lt; n; i++){  
                 for(int j=1; j &lt; (n-i); j++){  
                          if(q[j-1] &gt; q[j]){  
                                 //swap elements  
                                 temp = q[j-1];  
                                 q[j-1] = q[j];  
                                 q[j] = temp;  

                                 noOfSwaps++;
                         }  

                 }  
         } 

         System.out.println(noOfSwaps);

        }
Time limit improvements


You don't need to implement a full bubble sort (as the maximum distance is 2 bribes!)
You can skip if a person is in the correct position if you know the processed part is correct.
You don't need to process the list twice, you only need to check if the person you are checking is within the maximum swap distance.


I commented my algorithm below; it is basically a bubble sort, only with a limit on how far the inner loop goes.

public class Solution {

    static final int MAX_SWAPS = 2;

    // Complete the minimumBribes function below.
    static void minimumBribes(int[] q) {
           int bribes = 0;

           int n=q.length;

           //we process from right to left
           for (int i=n-1; i&gt;=0; i--)
           { 
               int pos = i+1;
               int s;

               //if we are correct, we can proceed LEFT, 
               //we know the right tail is correctly sorted
               //so after this step, the tail is 1 longer ans STILL correctly sorted
               if (q[i] == pos) continue;

               //try swap our position with previous positions, look MAX_SWAPS left.

               //for example:   1 5 2 4 3

               //if we are investigating position 5 (currently number 3)
               //we start swapping the items at position 3 and 4 if number 5 is at position 3.

               //if number 5 was not at position 3, 
               //we try to find it at position 4
               //if number 5 was also not at position 4, we are too chaotic, as you 
               //cannot bribe yourself more than MAX_SWAPS to the left.
               //so we are TOO CHAOTIC!

               //for example:   1 2 5 4 3

               //if number 5 is in position 5, we can skip it
               //(it is not)
               //if number 5 is at position 3
               //we swap the numbers 5 and 4 (at position 3 and 4) and have 1 bribe (bribes++)
               //situation becomes: 1 2 4 5 3
               //if now number 5 is at position 4, we have bribed again (bribes++)
               //situation becomes: 1 2 4 3 5

               //now we know 5 is in the correct position, and can scan from position 4
               //situation becomes: 1 2 4 3 [5]    // [] mark list that is DONE :)
               //if number 4 is in position 4, we add it
               //(it is not)
               //now if number 4 is in position 2, swap,
               //(it is not) 
               //now if number 4 is in position 3, swap
               //it IS, swap them and bribes++
               //1 2 3 [4 5]

               //if number 3 is in position 3, we add it
               //1 2 [3 4 5]
               //etc.

               for (int m = MAX_SWAPS; m&gt;0; m--)
               {
                   int left = i-m;
                   if (left&gt;=0 &amp;&amp; q[left]==pos)
                   {
                        s = q[left];
                        q[left]= q[left+1];
                        q[left+1]  = s;
                        bribes++;
                   }
                   else 
                   {
                        if (m == 1) //if we didn't find the correct number at the last left position
                                    //after MAX swaps left, we are too chaotic 
                        {
                           System.out.println("Too chaotic"); return;
                        }
                   }
               }
           }
           System.out.println(bribes);


    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr &lt; t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] q = new int[n];

            String[] qItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i &lt; n; i++) {
                int qItem = Integer.parseInt(qItems[i]);
                q[i] = qItem;
            }

            minimumBribes(q);
        }

        scanner.close();
    }
}