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.

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.

Notice

You are not necessary to keep the original order of positive integers or negative integers.

Code (Java):

public class Solution {
    /*
     * @param A: An integer array.
     * @return: nothing
     */
    public void rerange(int[] A) {
        if (A == null || A.length < 2) {
            return;
        }
        
        int pivot = partition(A);
        int numNegative = pivot + 1;
        int numPositive = A.length - pivot - 1;
        
        if (numNegative == numPositive - 1) {
            interleave(A, 0, A.length - 2);
        } else if (numNegative == numPositive + 1 ) {
            interleave(A, 1, A.length - 1);
        } else {
            interleave(A, 0, A.length - 1);
        }
    }
    
    private int partition(int[] A) {
        int start = 0;
        int end = A.length - 1;
        
        while (start <= end) {
            while (start <= end && A[start] < 0) {
                start++;
            }
            
            while (start <= end && A[end] >= 0) {
                end--;
            }
            
            if (start <= end) {
                swap(A, start, end);
                start++;
                end--;
            }
        }
        
        return end;
    }
    
    private void interleave(int[] A, int start, int end) {
        while (start < end) {
            swap(A, start, end);
            start += 2;
            end -= 2;
        }
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}