Rearrange the array in alternating positive and negative items with O(1) extra space

The problem, simply

You get an array with negative and non-negative numbers mixed up. Rearrange it so they alternate: negative, non-negative, negative, non-negative, and so on, starting with a negative. Zero counts as non-negative.

Keep the order: the negatives must appear in the same order as before, and so must the others. If one kind runs out, the leftovers of the other kind go at the end, still in order. The title asks for O(1) extra space, so no second array.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use two extra lists. Walk the array once: negatives go in one list, the others in the other list, both in order. Then refill the array by taking one from each list in turn, and pour out whatever is left.

class Solution {
    public void rearrange(int[] arr) {
        List<Integer> neg = new ArrayList<>(), pos = new ArrayList<>();
        for (int x : arr) {
            if (x < 0) neg.add(x); else pos.add(x);
        }
        int i = 0, j = 0, k = 0;
        while (i < neg.size() && j < pos.size()) {   // take turns
            arr[k++] = neg.get(i++);
            arr[k++] = pos.get(j++);
        }
        while (i < neg.size()) arr[k++] = neg.get(i++);   // leftovers keep their order
        while (j < pos.size()) arr[k++] = pos.get(j++);
    }
}

How long it takes: two walks, O(n). Extra room: the two lists hold all n numbers, O(n). Fast, but it breaks the "no extra space" rule.

Way 2: the clever way

Fix the spots from left to right, like the dance teacher.

1. Spot i wants a negative if i is even, and a non-negative if i is odd.
2. If arr[i] is already the right kind, move on.
3. Otherwise find the first j > i holding the wanted kind. If there is none, stop: the rest is all one kind.
4. Rotate arr[i..j] one step to the right. arr[j] jumps to spot i, and everyone in between slides one step right. Nobody passes a number of its own kind, so order is kept.

class Solution {
    public void rearrange(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            boolean wantNeg = (i % 2 == 0);
            boolean ok = wantNeg ? arr[i] < 0 : arr[i] >= 0;
            if (ok) continue;
            int j = i + 1;                       // the next number of the wanted kind
            while (j < n && (wantNeg ? arr[j] >= 0 : arr[j] < 0)) j++;
            if (j == n) break;                   // none left: the rest is one kind
            rotateRight(arr, i, j);
        }
    }

    // arr[to] jumps to arr[from]; everything in between slides one step right.
    private void rotateRight(int[] arr, int from, int to) {
        int last = arr[to];
        for (int k = to; k > from; k--) arr[k] = arr[k - 1];
        arr[from] = last;
    }
}

How long it takes: each fix can slide up to n numbers, so O(n^2) in the worst case. Extra room: one saved number, O(1).

Another way: when order does not matter

If the interviewer says the order may change, there is an O(n) way with O(1) room.

1. Move all non-negatives to the front with one partition pass. Say they fill 0..p-1, and the negatives fill p..n-1.
2. Swap a negative onto every even spot: swap arr[0] with arr[p], arr[2] with arr[p+1], and so on, while the even spot is still before the negatives.

class Solution {
    public void rearrange(int[] arr) {
        int n = arr.length, p = 0;
        for (int i = 0; i < n; i++) {               // non-negatives to the front
            if (arr[i] >= 0) { int t = arr[i]; arr[i] = arr[p]; arr[p] = t; p++; }
        }
        for (int i = 0, neg = p; i < neg && neg < n; i += 2, neg++) {
            int t = arr[i]; arr[i] = arr[neg]; arr[neg] = t;   // a negative onto each even spot
        }
    }
}

On [1, 2, 3, -4, -1, 4] this gives [-1, 2, -4, 4, 1, 3]: it alternates, but -1 now comes before -4.

Watch out for

• Decide where zero goes before you code. Here zero is non-negative.
• Some versions start with a positive number. Swap the even and odd rule.
• When the wanted kind runs out, stop. The rest of the array is already all one kind and in order.

What interviewers ask next

• Can you keep the order in O(n) time and O(1) room? Not with simple tricks. A divide and conquer that rotates blocks gets O(n log n); true O(n) stable in-place methods exist in research but are not expected.
• What if the counts are equal and you may use extra space (LeetCode 2149)? Write negatives to the odd spots and positives to the even spots of a new array with two write pointers.
• How does the rotation compare to insertion sort? It is the same move: take one number and slide a block to make room.

Remember this

Grown-up words: keeping the order is a stable rearrangement, the slide is a right rotation of a subarray, no second line means O(1) auxiliary space, and the order-breaking version uses a partition.