in LintCode Array Two Pointers ~ read.

Interleaving Positive and Negative Numbers

LintCode-144.Interleaving Positive and Negative Numbers

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.

Notice: 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.

class Solution {  
    /**
     * @param A: An integer array.
     * @return: void
     */
    public void rerange(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }

        int positiveCount = 0, negativeCount = 0;

        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                positiveCount++;
            } else {
                negativeCount++;
            }
        }

        int negativeIndex = 0, positiveIndex = 1;
        if (positiveCount > negativeCount) {
            negativeIndex = 1;
            positiveIndex = 0;
        }

        while (negativeIndex < A.length && positiveIndex < A.length) {
            while (negativeIndex < A.length && A[negativeIndex] < 0) {
                negativeIndex += 2;
            }

            while (positiveIndex < A.length && A[positiveIndex] > 0) {
                positiveIndex += 2;
            }

            if (negativeIndex < A.length && positiveIndex < A.length) {
                int temp = A[negativeIndex];
                A[negativeIndex] = A[positiveIndex];
                A[positiveIndex] = temp;

                negativeIndex += 2;
                positiveIndex += 2;
            }
        }
   }
}

Hope this helps,
Michael