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?