Solution to the CodingBat Array-3 [fix34]

Question

I was studying for arrays from coding-bat and encountered this:

The question is: (fix34)

Return an array that contains exactly the same numbers as the given array, but rearranged so that every 3 is immediately followed by a 4. Do not move the 3's, but every other number may move. The array contains the same number of 3's and 4's, every 3 has a number after it that is not a 3 or 4, and a 3 appears in the array before any 4.

fix34{1, 3, 1, 4} → {1, 3, 4, 1}

fix34{1, 3, 1, 4, 4, 3, 1} → {1, 3, 4, 1, 1, 3, 4}

fix34{3, 2, 2, 4} → {3, 4, 2, 2}

fix34{2, 3, 5, 3, 2, 4, 4} → {2, 3, 4, 3, 4, 5, 2 }

Code:

public static int[] fix34(int[] nums) {

    // first i stored numbers which are not 3 or 4
    ArrayList<Integer> others = new ArrayList<Integer>();

    for (int i = 0; i < nums.length; i++ )
    {
        if ( nums[i] != 3 && nums[i] != 4 )
            others.add(nums[i]);
    }       

    // i created a null array with same length as nums array
    int[] result = new int[nums.length];

    // first i replaced 3's in their specific place, then i replaced 4 near them.
    // so that other spots are 0
    for ( int i = 0; i < nums.length - 1; i++ )
    {
        if ( nums[i] == 3)
        {
            result[i] = 3;
            result[i+1] = 4;
        }           
    }

    // now i filled 0s with temped other numbers which i stored in an arraylist.
    // these numbers' size suits with the numbers of zeros
    int j = 0;
    for ( int i = 0; i < result.length; i++ )
    {
        if ( result[i] == 0 )
        {               
            int temp = others.get(j);
            j++;
            result[i] = temp;
        }

    }

    return result;

}

I like using ArrayLists, but is it a silly solution? How can I do this with a single loop?

Answer 1

It can easily be done in O(n) i.e a single loop traversal. Think simple .Modify the below program to suit your understanding and find the algorithm in the comments.
Just a brief:

1. Traverse the array from 0 to get the first position where you meet 3 say curIdx. Now you know that curIdx+1 can be replaced.
2. Traverse the array from the last to get the last position of 4, say lastIdx. Now you know that lastIdx can be replaced.

3. Swap curIdx and lastIdx if its within the array's range.

   void reArrange(int[] arr) {

   int[] arr = {2, 3, 5, 3, 2, 4, 4};
   int lastIdx = arr.length-1;
   int curIdx= 0 ;
   while(true){ //I know when to exit. Trust me!!!
       // Where art thou my 3. I need to replace the index after you.
       while(curIdx<arr.length && arr[curIdx]!=3){
           curIdx++;
       }
       curIdx++;
   
       // Gotcha Mr 4. You need to lead 3 safely.
       while(lastIdx>0 && arr[lastIdx]!=4){
           lastIdx--;
       }
   
       // As I said, trust me and I will help you exit
       if(curIdx>=arr.length || lastIdx<=0){
           break;
       }
   
       // Swap Time to rearrange Mr 4's after 3.
       int temp = arr[curIdx];
       arr[curIdx] = arr[lastIdx];
       arr[lastIdx] = temp;
   }
   
   // Did I do it correctly? Lets check.
   for(curIdx=0;curIdx<arr.length;curIdx++){
       System.out.print(arr[curIdx] + "  ");
   }
   

   }

Note:

• I am rearranging the 4's after 3's without considering the order.
• I assume that the input meets the constraints provided.