Boolean array reordering in O(1) space and O(n) time

Question

The problem is taken from Elements of Programming Interviews:

Given an array A of n objects with Boolean-valued keys, reorder the array so that objects that have the key false appear first. The relative ordering of objects with key true should not change. Use O(1) additional space and O(n) time.

I did the following, it preserves the relative ordering of objects with key true and uses O(1) additional space, but I believe its time complexity is O(n*n!).

public static void rearrangeVariant4(Boolean[] a) {
  int lastFalseIdx = 0;
  for (int i = 0; i < a.length; i++) {
    if (a[i].equals(false)) {
      int falseIdx = i;
      while (falseIdx > lastFalseIdx) {
        swap(a, falseIdx, falseIdx-1);
        falseIdx--;
      }
      lastFalseIdx++;
    }
  }
}

Anyone has an idea on how to solve it in O(n) time?

Answer 1

boolean array[n]; // The array
int lastTrue = n;
for (int i = n-1; i >= 0; --i) {
  if (array[i]) {
    swap(array[--lastTrue], array[i]);
  }
}

After every iteration all elements after lastTrue are true. No two true elements are swapped because if there was a true element between i and lastTrue it would have been encountered already and moved behind lastTrue. This runs in O(n) time and O(1) memory.

Answer 2

Java Code - if you are using a Boolean[] - objects:

Time - O(1), Space - O(1)

public static <T> void swap(T[] a, int i, int j) {
    T t = a[i];
    a[i] = a[j];
    a[j] = t;
}

Time - O(N), Space - O(1)

public static Boolean[] getReorderBoolObjects(Boolean[] array) {
    int lastFalse = 0;

    for (int i = 0; i < array.length; i++) {
        if (!array[i]) {
            swap(array, lastFalse++, i);
        }
    }

    return array;
}

Spock Test Case:

def "reorder bools - objects"() {
    given:
    Boolean[] b = [false, true, true, true, false, true]

    when:
    getReorderBoolObjects(b)

    then:
    b == [false, false, true, true, true, true]
}

Java Code - if you are using a boolean[] - primitives:

Time - O(N), Space - O(1)

public static boolean[] getReorderBoolPrimitives(boolean[] array) {
    int falseCount = 0;
    for (final boolean bool : array) {
        if (!bool) {
            falseCount++;
        }
    }
    for (int i = 0; i < array.length; i++) {
        array[i] = i >= falseCount;
    }
    return array;
}

Spock Test Case:

def "reorder bools - primitives"() {
    given:
    boolean[] b = [false, true, true, true, false, true]

    when:
    getReorderBoolPrimitives(b)

    then:
    b == [false, false, true, true, true, true]
}

Answer 3

Let the array have 0 based index and let it have n elements. Then you can do the following ( pseudo code below )

     // A[] is your array
     i = 0
     k = 0
     for i from 0 to n-1
          if A[i] is true
             swap A[i] and A[k]
             increment k

Time complexity is O(n) and extra space is only used for two variables i and j so memory is O(1). This way ordering is preserved amongst false and true values. ( This method puts true ones first you can change it according to your requirement ).