Rearrange positive and negative numbers in an array — Java

Problem: Given an array of positive and negative numbers in random order, rearrange it so that all negative numbers appear on the left and all positive numbers on the right.

Constraint: No second array. Only one extra variable allowed.

Approach

Use two pointers — one starting from the left (i) and one from the right (posIdx):

1. If arr[i] is negative, move i forward
2. If arr[i] is positive and arr[posIdx] is negative, swap them
3. If arr[i] is positive and arr[posIdx] is also positive, decrement posIdx
4. Stop when posIdx <= i

Solution

public class RearrangeArray {

    public static void rearrange(int[] arr) {
        int posIdx = arr.length - 1;
        for (int i = 0; i < arr.length; ) {
            if (posIdx <= i) {
                break;
            }
            if (arr[i] < 0) {
                i++;
            } else if (arr[posIdx] < 0) {
                int temp = arr[posIdx];
                arr[posIdx--] = arr[i];
                arr[i] = temp;
            } else {
                posIdx--;
            }
        }
    }

    public static void main(String[] args) {
        int[][] testCases = {
            {1, -2, 3, -4, 5, -6},
            {-1, -2, -3, 4, 5, 6},
            {1, 2, 3, -1, -2, -3},
            {-5, 3, -2, 7, -1, 4},
            {1, 2, 3},
            {-1, -2, -3},
        };

        for (int[] arr : testCases) {
            System.out.print("original:  ");
            printArray(arr);

            rearrange(arr);

            System.out.print("result:    ");
            printArray(arr);
            System.out.println();
        }
    }

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

Output

original:  1, -2, 3, -4, 5, -6
result:    -6, -2, -4, 3, 5, 1

original:  -1, -2, -3, 4, 5, 6
result:    -1, -2, -3, 4, 5, 6

original:  1, 2, 3, -1, -2, -3
result:    -3, -2, -1, 3, 2, 1

original:  -5, 3, -2, 7, -1, 4
result:    -5, -1, -2, 7, 3, 4

original:  1, 2, 3
result:    1, 2, 3

original:  -1, -2, -3
result:    -1, -2, -3

How it works

The algorithm uses a two-pointer technique similar to the partition step in quicksort. The left pointer (i) scans forward looking for positive numbers, while the right pointer (posIdx) scans backward looking for negative numbers. When both find a mismatch, they swap.

Time complexity: O(n) — each element is visited at most once.

Space complexity: O(1) — only one extra variable (temp) is used for swapping.