current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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.

share|improve this question
    
First case is not working for few condition !! –  Prashant Jun 10 at 10:01
    
My first solution is just wrong! It breaks, for example, for {"5","","1","2","3","4"} –  xploreraj Jun 11 at 20:53

1 Answer 1

up vote 4 down vote accepted

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]);
share|improve this answer
    
edited with fixes and alternatives –  rolfl Jun 9 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 :-) –  xploreraj Jun 9 at 21:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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