# 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