Stable Alternation of Positive and Negative Entries
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The array `nums` has even length, equal numbers of positive and negative entries, and no zeros. Rearrange its entries so signs alternate and the first entry is positive. Preserve the original relative order of all positive entries and, separately, of all negative entries. Return the resulting array. The source does not require an in-place rearrangement.
```cpp
class Solution {
public:
vector<int> rearrangeArray(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [-2,5,-4,7]
Output: [5,-2,7,-4]
Explanation: Positive order 5,7 and negative order -2,-4 are both retained.
```
**Example 2:**
```text
nums = [1,2,-3,-4]
Output: [1,-3,2,-4]
Explanation: The two sign subsequences are interleaved starting positive.
```
### Constraints
- The length is even and in `[2,2*10^5]`.
- `1 <= abs(nums[i]) <= 10^5`; sign counts are equal.
### Clarifying Questions
Relative order within each sign must be preserved. A separate output array is allowed.
```hint Inspect the structure
Which parity of output positions belongs to each sign?
```
### Reasoning checkpoints
- Begin with a positive entry and alternate signs throughout the result.
- Keep every input entry and preserve relative order within each sign.
- Meet the equal-sign-count domain without imposing an unnecessary in-place requirement.
### Optional extensions
What extra considerations would an in-place stable rearrangement introduce?
Overview: Stable Alternation of Positive and Negative Entries. The even-length nums contains equally many positive and negative integers and no zeros. Return an alternating-sign array beginning positive, while preserving the original relative order among positives and separately among negatives. In-place modification is not required.
