Rearrange Positive and Negative numbers alternatively in array where order of appearance does not matter

Problem: Given an integer array, rearrange it such that it contains positive and negative numbers at alternate positions. If the array contains more positive or negative numbers, move them to the end of the array.

Example: arr={-7,2,1,-4,5,10,11,-15,8}

Output = {8,-7,2,-4,1,-15,10,11,5}

Here output varies because order of appearance does not matter, but numbers appear alternatively as positive and negative.

Let us see how to get an efficient solution:

Solution: Use two pointers to keep track of last positive number in the array, and the last negative number in array. As it is rearranging as positive and negative numbers alternatively, the indexes 0,2,4,… have positive numbers and the indices 1,3,5,… have negative numbers. Traverse the array fully, and check if every even index of array has positive numbers, and if every odd index has negative numbers. If this is not correctly placed, check if current index is less than odd pointer or even pointer, if Yes, then swap the elements at current index with the odd or even pointer. Then decrement the odd or even pointer accordingly. In this way, the whole array is traversed in single traversal and the numbers are rearranged as positive and negative alternatively without extra memory space. This way does not maintain the order of appearance of the elements as in original array.

Below is Java code…

Algorithmic complexity:

Time complexity: O(N) where N is the length of given array.

Space complexity: O(1)

Hope this helped to understand the problem better…There is another solution which maintains the order of appearance of elements inspite of rearranging them as positive and negative number alternatively.

Thanks for reading this article…