# Rearrange Array Elements by Sign
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rearrange-array-elements-by-sign)
Canonical: https://scaleengineer.com/dsa/problems/rearrange-array-elements-by-sign
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
You are given a **0-indexed** integer array `nums` of **even** length consisting of an **equal** number of positive and negative integers.

You should return the array of nums such that the the array follows the given conditions:

1. Every **consecutive pair** of integers have **opposite signs**.
2. For all integers with the same sign, the **order** in which they were present in `nums` is **preserved**.
3. The rearranged array begins with a positive integer.

Return _the modified array after rearranging the elements to satisfy the aforementioned conditions_.

**Example 1:**

**Input:** nums = [3,1,-2,-5,2,-4]
**Output:** [3,-2,1,-5,2,-4]
**Explanation:**
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.  

**Example 2:**

**Input:** nums = [-1,1]
**Output:** [1,-1]
**Explanation:**
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

**Constraints:**

* `2 <= nums.length <= 2 * 105`
* `nums.length` is **even**
* `1 <= |nums[i]| <= 105`
* `nums` consists of **equal** number of positive and negative integers.

It is not required to do the modifications in-place.

# Approaches
## Segregation and Merging
This approach involves two main steps. First, we iterate through the input array and segregate the positive and negative numbers into two separate lists, while preserving their original relative order. Second, we create a new result array and merge the numbers from the two lists by interleaving them, starting with a positive number.
**Time:** O(N), where N is the length of the `nums` array. The first loop to segregate numbers takes O(N) time. The second loop to construct the result array takes O(N/2) = O(N) time. Thus, the total time complexity is O(N). · **Space:** O(N), where N is the length of the `nums` array. We use two lists, `positives` and `negatives`, which together will store all N elements. The space required for these lists is O(N/2) + O(N/2) = O(N). This is considered auxiliary space.
**Pros:** The logic is straightforward and easy to understand.; It correctly preserves the relative order of elements with the same sign.
**Cons:** Requires O(N) auxiliary space for the two lists, which is less space-efficient than the single-pass approach.; Involves two conceptual passes over the data: one to segregate and one to merge.
### Explanation
The core idea is to first separate the positive and negative numbers into their own collections. This makes it easy to pick the next positive or negative number in their original relative order.

1.  **Segregation:** We initialize two dynamic arrays (or lists), one for positive numbers (`positives`) and one for negative numbers (`negatives`). We then iterate through the input `nums` array. Each positive number is appended to the `positives` list, and each negative number is appended to the `negatives` list. This pass ensures that the relative ordering within same-signed numbers is maintained.

2.  **Merging:** After segregation, we have two lists: `[3, 1, 2]` and `[-2, -5, -4]` for the first example. We create a new result array of size `n`. We then loop `n/2` times. In each iteration `i`, we take the `i`-th element from the `positives` list and place it at the even index `2*i` in the result array. Then, we take the `i`-th element from the `negatives` list and place it at the odd index `2*i + 1`. This interleaving process builds the final array according to the problem's conditions.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();

        // Segregate positive and negative numbers
        for (int num : nums) {
            if (num > 0) {
                positives.add(num);
            } else {
                negatives.add(num);
            }
        }

        int[] result = new int[n];
        // Merge the two lists into the result array
        for (int i = 0; i < n / 2; i++) {
            result[2 * i] = positives.get(i);
            result[2 * i + 1] = negatives.get(i);
        }

        return result;
    }
}
```
### Algorithm
- Create two empty lists, `positives` and `negatives`.
- Iterate through the input array `nums`.
- If a number is positive, add it to the `positives` list.
- If a number is negative, add it to the `negatives` list.
- Create a new result array `result` of the same size as `nums`.
- Iterate from `i = 0` to `n/2 - 1` (where `n` is the length of `nums`).
- In each iteration, place the `i`-th element from `positives` at `result[2 * i]`.
- Place the `i`-th element from `negatives` at `result[2 * i + 1]`.
- Return the `result` array.

## Two-Pointer Single-Pass Approach
This is a more optimized approach that constructs the result array in a single pass through the input array. It uses two pointers to keep track of the next available positions for positive and negative numbers in the result array, eliminating the need for intermediate storage.
**Time:** O(N), where N is the length of the `nums` array. We iterate through the input array only once to place all elements in their correct positions. · **Space:** O(N) for the output array. The auxiliary space complexity (space used besides the input and output) is O(1), as we only use a few variables as pointers. This is more space-efficient than the segregation approach.
**Pros:** Highly efficient, completing the task in a single pass over the input array.; Minimal auxiliary space usage (O(1)), making it very space-efficient.; Combines segregation and placement into one loop, simplifying the overall process.
**Cons:** May be slightly less intuitive at first glance compared to the segregation approach, but is still straightforward.
### Explanation
This approach avoids creating intermediate lists by directly placing numbers into their correct positions in the final array in a single pass.

We start by creating a result array `ans` of the same size as the input. We then use two pointers: `posIndex` to track the next available even index (starting at 0) for a positive number, and `negIndex` to track the next available odd index (starting at 1) for a negative number.

We iterate through the input `nums` array from beginning to end. When we encounter a positive number, we place it in `ans[posIndex]` and then update `posIndex` by adding 2 to it, so it points to the next even index. Similarly, when we encounter a negative number, we place it in `ans[negIndex]` and update `negIndex` by adding 2. 

Because we iterate through `nums` in its original order, the relative ordering of positive numbers and negative numbers is naturally preserved. Since the problem guarantees an equal number of positive and negative integers, the pointers will fill the `ans` array completely without going out of bounds.

```java
class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int posIndex = 0; // Pointer for the next positive number position (even indices)
        int negIndex = 1; // Pointer for the next negative number position (odd indices)

        for (int num : nums) {
            if (num > 0) {
                ans[posIndex] = num;
                posIndex += 2;
            } else {
                ans[negIndex] = num;
                negIndex += 2;
            }
        }
        return ans;
    }
}
```
### Algorithm
- Create a new result array `ans` of size `n`.
- Initialize a pointer for positive numbers, `posIndex = 0`.
- Initialize a pointer for negative numbers, `negIndex = 1`.
- Iterate through each number `num` in the input array `nums`.
- If `num` is positive:
  - Place it at `ans[posIndex]`.
  - Increment `posIndex` by 2.
- If `num` is negative:
  - Place it at `ans[negIndex]`.
  - Increment `negIndex` by 2.
- Return the final `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] rearrangeArray(int[] nums) {
    int[] ans = new int[nums.length];
    int i = 0, j = 1;
    for (int num : nums) {
      if (num > 0) {
        ans[i] = num;
        i += 2;
      } else {
        ans[j] = num;
        j += 2;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> rearrangeArray(vector<int> &nums) {
    vector<int> ans(nums.size());
    int i = 0, j = 1;
    for (int num : nums) {
      if (num > 0) {
        ans[i] = num;
        i += 2;
      } else {
        ans[j] = num;
        j += 2;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]: ans = [0] * len(nums) i, j = 0, 1 for num in nums: if num > 0: ans[i] = num i += 2 else: ans[j] = num j += 2 return ans

```