Rearranging array - with empty strings in front and non-empty strings at back

Question

Given a string array that either contains empty strings or non-empty strings, arrange the contents such that all the empty strings are at front and non-empty strings at back, retaining their order from original array.

For example, input:

{"","a","","d","","o","","g",""}
{"d","o","g"}
{"","","",""}

Output:

[, , , , , a, d, o, g]
[d, o, g]
[, , , ]

I wrote two implementations below:

1. In-place re-arrangement

   //in-place arrangement with two pointers running towards starting index from back
   public static void arrangeString(String...arr) {
       for (int i=arr.length-1, j=i; i>=0 && j >=0; ) {
           boolean needSwap  =false;
           boolean exit = false;
           while (!exit && arr[i].equals("")) {
               i--; needSwap = true;
               if (i==-1) exit = true;
           }
           while (!exit && !arr[j].equals("")) {
               j--; needSwap = true;
               if (j==-1) exit = true;
           }
           if (exit) break;
           if (needSwap) {
               String temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
           i--; j--;
       }
   }
   

2. Re-arranging using a temp array

   public static String[] arrangeString(String...arr) {
       int len = arr.length;
       String[] temp = new String[len];
       for (int i=0, t1=0, j=len-1, t2=len-1; i<len && j>=0; i++, j--) {
           if(arr[i].equals(""))
               temp[t1++] = arr[i];
           else if(!arr[j].equals(""))
               temp[t2--] = arr[j];
       }
       return temp;
   }
   

Please give me suggestions on how to improve them. It'll be great if you can provide an alternative code snippet replacing my code.

Answer 1

Your code snippets are interesting... both of them.

The second is interesting because I feel it is your better-executed system, you used an interesting bi-directional approach, and it is efficient.

The first is interesting because I prefer the in-place solution, but your implementation is kludgey.... and hard to follow.

Temp-array solution

Notes:

• use String.isEmpty().
• make len final, it's not a big deal, but I find it helps readability.

As an aside, I would seriously consider a simpler temp-array solution, even though it loops twice:

final int len = arr.length;
final String[] temp = new String[len];
int pos = 0;
for (String s : arr) {
    if (s.isEmpty()) {
        temp[pos++] = s;
    }
}
for (String s : arr) {
    if (!s.isEmpty()) {
        temp[pos++] = s;
    }
}
return temp;

The above solution may be slightly slower (would need testing), but it is also clear, and scales in linear time still. It's not horrible.

In-place solution

This solution is just.... messy. I think a better option is to have two pointers..... one to the first non-empty, and the next to the first empty after that....

private static final int findEmptyState(final String[] data, int index, final boolean empty) {
    while (index < data.length && data[index].isEmpty() != empty) {
        index++;
    }
    return index;
}

with the above helper function, you can:

    final int len = arr.length;
    int notempty = findEmptyState(arr, 0, false);
    int empty = findEmptyState(arr, notempty + 1, true);

    while (notempty < len && empty < len) {

        // shift the next empty value in before the not-empty.
        String e = arr[empty];
        System.arraycopy(arr, notempty, arr, notempty + 1, empty - notempty);
        arr[notempty] = e;

        // find the next coordinates.
        notempty = findEmptyState(arr, notempty, false);
        empty = findEmptyState(arr, notempty + 1, true);
    }
    return arr;

Alternatives

A cheating alternative is to rely on the fact that Java sorts are stable... you can do:

Arrays.sort(arr, Comparator.comparingInt(value -> value.isEmpty() ? 0 : 1));
return arr;

which puts empty values first.

Or, as a duplicated solution, you can:

 return Stream.of(arr)
          .sorted(Comparator.comparingInt(value -> value.isEmpty() ? 0 : 1))
          .toArray(sz -> new String[sz]);