Rearranging an array such that positive and negative elements are at alternate positions We are given an array in which we have equal number of positive and negative elements. 

We have to rearrange this array such that all positive and negative elements are at alternate positions and also, respective order should be maintained. N i.e. the size of array can be: 1&lt;=N&lt;=\$10^6\$ .  No additional data structure can be used  

INPUT:  

1 2 3 -1 -2 -3  


OUTPUT:  

1 -1 2 -2 3 -3  


My code was accepted but it exceeded the time limit for a case. How can I make my code more efficient by reducing its time complexity?

My code:  

import java.util.*;
 class A{
 public static void main(String args[])
 {
     Scanner s=new Scanner(System.in);
     int n=s.nextInt();
     int a[]=new int[n];
     for(int i=0;i&lt;n;i++)
         a[i]=s.nextInt();
     rearrange(a);
     for(int i=0;i&lt;n;i++)
         System.out.print(a[i]+" ");
 }

public static void rotateright(int a[],int l,int r)
{
    int temp=a[r];
    for(int i=r;i&gt;l;i--)
    {
        a[i]=a[i-1];
    }
    a[l]=temp;
}
public static void rearrange(int a[])
{
    int n=a.length;
    int i=0,j=0;
    while(i&lt;n)
    {   
        if(i%2==0)    //even index should have positive element
        {
            if(a[i]&gt;0)     //already positive
                i++;
            else               //for negative
            {
                j=i+1;
                while(j&lt;n)      //finding next positive
                {
                    if(a[j]&gt;0)
                        break;
                    j++;
                }
                rotateright(a,i,j);    //making even index positive
                i++;
            }
        }
        else            //odd index should have negative element
        {
            if(a[i]&lt;0)   //already negative
                i++;
            else           //for positive
            {
                j=i+1;
                while(j&lt;n)          //finding next negative
                {
                    if(a[j]&lt;0)
                        break;
                    j++;
                }
                rotateright(a,i,j);     //making odd index negative
                i++;
            }
        }
    }
}
}
Worst case

Picturing the worst case helps understanding the problem.
The test failing probably uses an array of size n containing n/2 positive numbers followed by n/2 negative numbers (or vice-versa).

Current implementation

Note that when you find an element out of place, you are iterating twice through the indices, until you find the correct element: one time two found its position, another to move all elements in between.
You can combine both operations into one. Still this algorithm resembles the insertion sort. It will be quadratic in the worst case that I described (more specifically, (n/2)^2).

Using extra space

One efficient way to solve this is to build the correct array from the beginning. This requires O(1) of extra space.
You create 3 arrays: one to buffer positive numbers, other to buffer negative numbers, and a 3rd one with the final result.

When reading from stdin:


Place the number in the 3rd array if it matches the position, otherwise store it in the appropriate array;
If the number matches, try to use numbers stored in the positive/negative numbers arrays to keep filing the 3rd array (using FIFO).


What we are doing is essentially merging 3 sorted arrays: stdin, the array with positive numbers and the array with negative numbers.

This should run linearly, requiring 2 writes per number out of place.