Solution to the CodingBat Array-3 [fix34]

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 others = new ArrayList();

    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?

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:

• 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.

• Traverse the array from the last to get the last position of 4, say lastIdx. Now you know that lastIdx can be replaced.

-
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(curIdx0 && 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.

StackExchange Code Review Q#75224, answer score: 4