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.

• Prashant: First case is not working for few condition !!
• xploreraj: My first solution is just wrong! It breaks, for example, for {"5","","1","2","3","4"}

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]);

• rolfl: edited with fixes and alternatives
• xploreraj: Upvoted, nice logic 'rolfl'. Though I am not comfortable with your alternatives as I am still doing Java 6 code on Java 7. Overall, elegant :-)