Move All the Negative Elements to One Side of the Array

Understanding the Problem

The goal is to move all negative elements to one side of the array using different methods.

Method 1: Using Two Pointers

This method uses two pointers to swap negative and positive elements efficiently.

public class MoveNegatives {
    public static void rearrange(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            if (arr[left] < 0) left++;
            else if (arr[right] >= 0) right--;
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }
    
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
        rearrange(arr);
        printArray(arr);
    }
}
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11

Method 2: Using Partition Process of QuickSort

This method places all negative elements before positive elements using partitioning.

public class MoveNegativesPartition {
    public static void partition(int[] arr) {
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                if (i != j) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                j++;
            }
        }
    }
    
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
        partition(arr);
        printArray(arr);
    }
}
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11

Method 3: Using Extra Space

This method creates a new array and stores negative and positive elements separately.

public class MoveNegativesExtraSpace {
    public static void rearrangeWithExtraSpace(int[] arr) {
        int[] temp = new int[arr.length];
        int index = 0;
        
        for (int num : arr) {
            if (num < 0) temp[index++] = num;
        }
        for (int num : arr) {
            if (num >= 0) temp[index++] = num;
        }
        System.arraycopy(temp, 0, arr, 0, arr.length);
    }
    
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
        rearrangeWithExtraSpace(arr);
        printArray(arr);
    }
}
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11