19. Rearrange array in alternating positive and negative items with O(1) extra space

19. Rearrange array in alternating positive and negative items with O(1) extra space

Problem link :- click here

package programs;

import java.util.*;

public class Array__19
{

	static void rearrange(int arr[], int n)
	{
		int wrong_index = -1;
		for(int i=0; i<n; i++)
		{
			if(wrong_index != -1)
			{
				if(  ( arr[wrong_index]>=0   &&   arr[i]<0 )   ||  ( arr[wrong_index]<0   &&   arr[i]>=0 )   )
				{
					rightRotate(arr, wrong_index, i);
					
					if( i - wrong_index >=2)
						wrong_index += 2;
					else
						wrong_index = -1;
				}
			}
			else if( ( i%2==0  &&  arr[i]>=0 )  ||  ( i%2==1   &&   arr[i]<0 ) )
			{
				wrong_index = i;
			}
		}
	}
	
	static void rightRotate(int arr[], int from, int to)
	{
		int temp = arr[to];
		for(int i=to; i>from; i--)
			arr[i] = arr[i-1];
		arr[from] = temp;
	}
	
	
	public static void main(String[] args)
	{
		int i, n;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given array : ");
		printArray(array);
		
		rearrange(array, n);
		System.out.println("\n\nArray after rearranging : ");
		printArray(array);
	}

	static void printArray(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)