Rearrange the Array in Alternating Positive and Negative Items

In this article, we will solve the problem of rearranging an array such that positive and negative numbers alternate. If there are extra positive or negative numbers, they should appear at the end of the array.

Problem Statement: Given an array of integers, rearrange the array so that positive and negative numbers alternate. If there are extra positive or negative numbers, they should appear at the end of the array.

Example:

Input: arr = [1, 3,-8, -9, 5, -6]

Output: [1, -8, 3, -9, 5, -6]

Solution:

To rearrange the array such that positive and negative numbers alternate, we can use a two-step approach:

1.    Partition the array into positive and negative numbers.

2.    Merge the positive and negative numbers to form the required pattern.

Following will be the approach:

1.    Separate Positive and Negative Numbers:

o   Traverse the array and store positive numbers in one list and negative numbers in another list.

2.    Merge the Lists Alternately:

o   Merge the two lists such that the elements alternate between positive and negative numbers.

o   If one list is exhausted, append the remaining elements of the other list to the end of the result.

Time Complexity: O(N)

Space Complexity: O(N)