Given an array **arr[]** of length **n**, containing positive and negative numbers.

The task is to arrange the numbers in an alternate fashion such that every positive number is followed by a negative and vice-versa, **maintaining the order of appearance**.

The number of positive and negative numbers need not be equal.

If there are more positive numbers, they appear at the end of the array.

If there are more negative numbers, they too appear at the end of the array.

**Input:** arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}, n=10

**Output:** -5,5,-2,2,-8,4,7,1,8,0

**Input:** arr[] = {-4,1,-1,2,3,4}, n=6

**Output:** -4,1,-1,2,3,4

## Solutions

### Method 1: In O(n) time and O(n) space

In this approach, we use an auxiliary array, **tmp[]** and iterate the input array twice.

In the first iteration, store all **negatives at the start** of tmp[] and all **positives at the end** of tmp[].

In the second iteration, keep track of -ve and +ve elements in the tmp[] array and **fill alternatively** in the original array arr[].

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(n)**.

### Method 2: In O(n^2) time and O(1) space

In this approach, we iterate the array and **keep track of the wrongIndex (-ve in the odd index and +ve in the even index)**.

If the **wrongIndex** is greater than **-1**, we attempt to find the next opposite sign element to the one present on the incorrect index.

Once the opposite sign element is found, we **rotate the array from "wrongIndex" to "i"**.

Also, if the difference between "wrongIndex" and "i" is greater than two, we assign **wrongIndex = wrongIndex+2 (more than one wrongIndex is skipped)**, and if not, wrongIndex = -1.

##### Complexity

The time complexity of this solution is **O(n^2)** and space complexity is **O(1)**.