Interleaving Positive and Negative Numbers

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers. You are not necessary to keep the original order of positive integers or negative integers.

Example:

Given [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other reasonable answer.

Challenge:

Do it in-place and without extra memory.

Solution:

We first need to calculate the number of positives and number of negatives. Then we perform a partition to move all negative numbers on one side and positive numbers on the other side. During partition:

• if there are more positives, positives should sit on left ;
• if there are more negatives, negatives should sit on right.

Then, we could swap the elements by using two pointers (one from front and one from the back), where these two pointers are increased or decreased by 2 at a time. There are two scenarios for this stage:

1. if there are same numbers of positives and negatives, we simply start with left = 1 and right = A.length - 2
2. if there is one more positive or negative, we still start with left = 1 but the right will be A.length -3. We left that extra number in the end to simplify the problem to first case. After the swapping, we insert the last element into the beginning of the array.

Code:

class Solution {
    /**
     * @param A: An integer array.
     * @return: void
     */
    public void rerange(int[] A) {
        if (A == null || A.length == 0) {
           return;
        }
        int n = A.length;
        int negCount = 0;
        int posCount = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] > 0) {
                posCount++;
            } else {
                negCount++;
            }
        }
        partition(A, posCount, negCount);
        interleave(A, posCount, negCount);
    }
    private void interleave(int[] A, int posCount, int negCount) {
        int n = A.length;
        int left = 1;
        int right = n - 3;
        if (posCount == negCount) {
            right = n - 2;
        }
        while (left < right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left += 2;
            right -= 2;
        }
        if (posCount != negCount) {
            int temp = A[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                A[i + 1] = A[i];
            }
            A[0] = temp;
        }
    }
    private void partition(int[] A, int posCount, int negCount) {
        int left = 0;
        int right = n - 1;
        while (left < right) {
            while (left < right && compare(A[left], 0, posCount, negCount)) {
                left++;
            }
            while (left < right && compare(0, A[right], posCount, negCount)) {
                right--;
            }
            if (left < right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left++;
                right--;
            }
        }
    }
    private boolean compare(int a, int b, int posCount, int negCount) {
        if (posCount > negCount) {
            return a < b;
        } else {
            return b < a;
        }
    }
}