Is there a simpler solution for Codingbat fix45?

Question

I am trying to solve this CodingBat problem:

(This is a slightly harder version of the fix34 problem.) Return an array that contains exactly the same numbers as the given array, but rearranged so that every 4 is immediately followed by a 5. Do not move the 4's, but every other number may move. The array contains the same number of 4's and 5's, and every 4 has a number after it that is not a 4. In this version, 5's may appear anywhere in the original array.

fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9}
fix45({1, 4, 1, 5}) → {1, 4, 5, 1}
fix45({1, 4, 1, 5, 5, 4, 1}) → {1, 4, 5, 1, 1, 4, 5}

I initially used a method which passed all of the sites tests, but I don't think it would work for longer arrays. The initial method used 2 loops and did not use a new array. I have created a solution which introduces a new array and a 3rd nested loop and I believe will work for all instances of the problem. However, the site states that the problems in this section can be solved with 2 loops, so I am wondering if there actually is a 2 loop solution that will work for anyinstance of the problem. Here is the question and my 3 loop solution:

public int[] fix45(int[] nums) {

    int[] locations = {-1};

    for (int i = 0; i < nums.length - 1; ++i) {

        if (nums[i] == 4) {

            JLoop:
            for (int j = nums.length-1; j >= 0; --j) {
                if (nums[j] == 5) {
                    for (int k = locations.length-1; k>=0 ; --k) {
                        if (locations[k] == j) {
                            continue JLoop;
                        } 
                    }
                    nums[j] = nums[i + 1];
                    nums[i + 1] = 5;
                    locations[locations.length - 1] = i+1;
                    locations = java.util.Arrays.copyOf(locations,
                            locations.length + 1);
                    locations[locations.length-1] = -1;
                    break;
                }
            }
        }
    }
    return nums;

}

Answer 1

Restarting the search for a suitable 5 from one end of the array every time a 4 is found seems wasteful. Part of the array has already been scanned and is known not to contain a 5 that can be moved. This is O(n) time and O(1) space.

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

      int j = 0;
      for (int i = 0; i < nums.length - 1; ++i) {
        if (nums[i] == 4 && nums[i + 1] != 5) {
          /*
           * Need to find the next movable 5 That means an element that is 5 and
           * either is the first element or is preceded by anything other than 4
           */
          while (nums[j] != 5 || (j != 0 && nums[j - 1] == 4)) {
            j++;
          }
          nums[j] = nums[i + 1];
          nums[i + 1] = 5;
        }
      }
      return nums;
    }

Answer 2

Using an extra array, here's a solution with "one loop" (loops without nested loops):

public int[] fix45(int[] nums) {
  int[] otherValues = new int[nums.length];

  for(int i = 0, c = 0; i < nums.length; i++)
    if(nums[i] != 4 && nums[i] != 5)
      otherValues[c++] = nums[i];

  for(int i = 0, c = 0; i < nums.length; i++)
    if(nums[i] == 4)
      nums[++i] = 5;
    else
      nums[i] = otherValues[c++];

  return nums;
}

We fix the fours, take out the non-fours and non-fives, and put the values all back in in order.

To improve the space usage (perhaps not by much), you can count the number of fours before you make the extra array.

Answer 3

public int[] fix45(int[] nums) {

 int t=0;
  for(int i=0; i< nums.length ; i++)
     for(int j=0;j<nums.length ; j++)

     if(nums[i]==5 && nums[j]==4)
     {
      t=nums[j+1];
      nums[j+1]=nums[i];
      nums[i]=t;
     }
     return nums;
}