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

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.

• First case is not working for few condition !! Commented Jun 10, 2015 at 10:01
• My first solution is just wrong! It breaks, for example, for {"5","","1","2","3","4"} Commented Jun 11, 2015 at 20:53

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:

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

• edited with fixes and alternatives Commented Jun 9, 2015 at 12:37
• 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 :-) Commented Jun 9, 2015 at 21:55