5
\$\begingroup\$

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.

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

1 Answer 1

4
\$\begingroup\$

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]);
\$\endgroup\$
2
  • \$\begingroup\$ edited with fixes and alternatives \$\endgroup\$
    – rolfl
    Commented Jun 9, 2015 at 12:37
  • \$\begingroup\$ 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 :-) \$\endgroup\$
    – xploreraj
    Commented Jun 9, 2015 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.