write a program in java to Rearrange positive and negative numbers in O(n) time and O(1) extra space.

Problem statement:

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. 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 in the end of the array.

import java.util.Arrays;

class RearrangePosNeg

{

          public static void main(String[] args)

          {

                   int arr[]=new int[]{1,2,-3,-4,5,-6,-7,8,-9};

                   //sort number in ascending order

                   Arrays.sort(arr);

                    int  temp = 0,i=0;

                   while(arr[i]<0 span="">

                   {

                             ++i;

                   }

                   //pos=starting position of positive number after sorting

                   //neg=starting position of negative number after sorting

                   int pos = i ,neg = 0;

                   //swap negative value with positive till negative obtained and  //remaining be as well as

                  //Increment the negative index by 2 and positive index by 1

                   while (pos < arr.length && neg < pos && arr[neg] < 0)

                   {

                             temp = arr[neg];

                             arr[neg] = arr[pos];

                             arr[pos] = temp;

                             pos++;

                             neg += 2;

                   }

                   //print array

                   for(int j:arr)

                   {

                             System.out.println(j+" ");

                   }

          }

}

Output