Rearrange Array Elements by Sign, thesarfo

Equal counts of positive/negative values, rearrange so they alternate [pos, neg, pos, neg, ...] while preserving relative order within each sign. [3,1,-2,-5,2,-4] → [3,-2,1,-5,2,-4]. (LeetCode 2149)

Brute force: split into separate pos[]/neg[] arrays, then interleave them back (arr[2i] = pos[i], arr[2i+1] = neg[i]). O(n) time, O(n) space.

Optimal — same idea, single pass into the answer array directly: track posIndex (starting at 0, stepping by 2) and negIndex (starting at 1, stepping by 2), placing each element directly where it belongs as you scan.

int[] answer = new int[n];
int posIndex = 0;
int negIndex = 1;

for(int i = 0; i < n; i++) {
    if(nums[i] > 0) {
        answer[posIndex] = nums[i];
        posIndex += 2;
    } else {
        answer[negIndex] = nums[i];
        negIndex += 2;
    }
}
return answer;

Variant: Unequal Counts

If the number of positive and negative elements isn’t equal, alternate as long as both signs have elements left, then append the surplus from whichever sign ran longer, in original order.

public static int[] alternateNumbers(int[] a) {
    int[] pos = new int[a.length];
    int[] neg = new int[a.length];
    int posIndex = 0, negIndex = 0;
    int n = a.length;

    for (int i = 0; i < n; i++) {
        if (a[i] > 0) pos[posIndex++] = a[i];
        else neg[negIndex++] = a[i];
    }

    int index = 0;
    int minLength = Math.min(posIndex, negIndex);
    for (int i = 0; i < minLength; i++) {
        a[index++] = pos[i];
        a[index++] = neg[i];
    }

    for (int i = minLength; i < posIndex; i++) a[index++] = pos[i];
    for (int i = minLength; i < negIndex; i++) a[index++] = neg[i];

    return a;
}