20. Rearrange Array in Alternating Positive and Negative Items

Given an array of positive and negative integers, rearrange it so positives and negatives alternate, starting with a positive number, while preserving each group's original relative order. If one group runs out, place the remaining elements of the other group (in their original relative order) at the end. Print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, a mix of positive and negative values. Output: Print the rearranged array with positives and negatives alternating, starting with a positive, space-separated on one line.

1 <= n <= 10^5

This problem is a direct sibling of 'Move All Negatives to One Side' - both rely on the same 'separate into two order-preserving groups, then recombine' pattern, just combined differently (concatenation versus interleaving).

Rearrange a mix of positive and negative numbers so they alternate: positive, negative, positive, negative, and so on - keeping each group's original relative order, and tacking on any leftovers at the end. Brute force: Manually scan for the next positive and next negative element repeatedly, swapping them into alternating positions - this can work but risks disturbing relative order within each group unless done very carefully. Optimised: Separating into two clean lists first (each preserving relative order), then interleaving them directly, sidesteps any risk of accidentally breaking each group's internal order - a clean, predictable two-step process instead of a fiddly single-pass swap.

Make one left-to-right pass over the array and copy every positive value, in original order, into one temporary list, and every negative value, in original order, into another temporary list. Merge the two lists into the answer by alternating one positive then one negative, starting with positive, until one list runs out. Append whatever remains of the other, longer list unchanged, since it is already in its original relative order. This is a simple two-pass technique that is easy to verify correct. Time: O(n) Space: O(n)

Walk the original array with two independent scanning pointers, one that only advances over positive values and one that only advances over negative values, and interleave directly into the result array by writing the next unconsumed positive, then the next unconsumed negative, repeating. When one pointer's group is exhausted, flush the remaining elements of the other pointer's group, already in their original relative order, straight into the tail of the result. This avoids building two separate auxiliary lists before merging, doing everything in one coordinated pass over the source array. Time: O(n) Space: O(n) for the output array; O(1) extra auxiliary

Scan the array left to right expecting the alternating sign pattern to hold, starting with positive. Whenever the sign at the current position violates that pattern, find the nearest later index holding the correct sign and right-rotate the subarray between the current position and that index by one step so the correctly-signed element slides into place; a rotation only shifts elements without reordering either group internally. Repeat this fix-up scan over the array until the whole sequence satisfies the alternating pattern. Because a single fix can require shifting up to O(n) elements and up to O(n) fixes may be needed, the overall work is quadratic. Time: O(n^2) Space: O(1)

1. Separate the array into a positives list and a negatives list, each preserving its own original relative order. 2. Interleave them one at a time, starting with a positive, then a negative, then a positive, and so on. 3. Once one list runs out, append whatever remains of the OTHER list, in its original order, to the end.

Time: O(n) - one pass to separate, one pass to interleave. Space: O(n), for the two temporary lists.

unequal counts of positives and negatives, leaving leftover elements appended at the end, as in the example; an array of all positives or all negatives; and n = 10^5 (largest, confirming the separate-then-interleave approach is O(n)).

Be ready to handle the leftover case explicitly (one group being longer than the other) - many candidates get the alternating logic right but forget this edge case entirely.