@@ -0,0 +1,1852 @@
+package com.coderevisited.arrays;%0A%0Aimport java.io.BufferedWriter;%0Aimport java.io.OutputStreamWriter;%0Aimport java.io.PrintWriter;%0A%0A/**%0A * 1. start from 0 to array.length -1;%0A * 2. find first out of place element, i.e either positive at even index or negative at odd index%0A * 3. find position of correct element, replace out of place element with correct element and shift array%0A * 4. now out of place element will be 2 positions head%0A */%0Apublic class RearrangePositivesAndNegative%0A%7B%0A    public static void main(String%5B%5D args)%0A    %7B%0A%0A        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));%0A        int%5B%5D array = new int%5B%5D%7B-5, -2, 5, 2, 4, 7, 1, 8, 0, -8%7D;%0A        rearrange(array);%0A        printArray(array, pw);%0A        pw.close();%0A%0A    %7D%0A%0A    private static void rearrange(int%5B%5D array)%0A    %7B%0A        int outOfPlace = -1;%0A        for (int i = 0; i %3C array.length; i++) %7B%0A%0A            if (outOfPlace %3E= 0) %7B%0A                if (array%5Bi%5D %3E= 0 && array%5BoutOfPlace%5D %3C 0 %7C%7C array%5Bi%5D %3C 0 && array%5BoutOfPlace%5D %3E= 0) %7B%0A                    rightRotate(array, outOfPlace, i);%0A                    if (i - outOfPlace %3E 2)%0A                        outOfPlace = outOfPlace + 2;%0A                    else%0A                        outOfPlace = -1;%0A                %7D%0A            %7D%0A%0A            if (outOfPlace == -1) %7B%0A                if (array%5Bi%5D %3E= 0 && ((i & 1) != 1) %7C%7C array%5Bi%5D %3C 0 && ((i & 1) == 1))%0A                    outOfPlace = i;%0A            %7D%0A        %7D%0A%0A    %7D%0A%0A    private static void rightRotate(int%5B%5D array, int i, int j)%0A    %7B%0A        int temp = array%5Bj%5D;%0A        System.arraycopy(array, i, array, i + 1, j - i);%0A        array%5Bi%5D = temp;%0A    %7D%0A%0A    private static void printArray(int%5B%5D array, PrintWriter pw)%0A    %7B%0A        for (int i : array) %7B%0A            pw.print(i + %22 %22);%0A        %7D%0A        pw.println();%0A    %7D%0A%7D%0A

Rearrange array in alternating positive & negative items with O(1) extra space