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:

-
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--;
    }
}

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

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

StackExchange Code Review Q#93082, answer score: 4