Move all the negative elements to one side of the array

The problem, simply

You get an array of whole numbers, some negative and some not. Rearrange it so that every negative number comes before every other number. The order inside each side does not matter.

Zero is not negative, so it goes with the positive numbers. Do it inside the same array if you can.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use two bags. Walk the array, put negatives in one bag and the rest in the other. Then pour the negative bag back into the array, followed by the other bag. This even keeps the original order on both sides.

class Solution {
    public void moveNegatives(int[] arr) {
        List<Integer> neg = new ArrayList<>();
        List<Integer> rest = new ArrayList<>();
        for (int x : arr) {
            if (x < 0) neg.add(x); else rest.add(x);
        }
        int k = 0;
        for (int x : neg) arr[k++] = x;     // negatives first
        for (int x : rest) arr[k++] = x;    // then everyone else
    }
}

How long it takes: two walks, O(n). Extra room: the two bags hold all n numbers, O(n).

Way 2: the clever way

Keep a wall j. Everything left of j is negative. Walk i from left to right.

1. Start with j = 0: nothing is behind the wall yet.
2. If arr[i] is negative, swap arr[i] with arr[j] and move the wall: j++.
3. If arr[i] is not negative, do nothing.

Between the wall and i there are only non-negative numbers, so the swap sends one of them to where i is, which is fine.

class Solution {
    public void moveNegatives(int[] arr) {
        int j = 0;                          // the wall: arr[0..j-1] are negative
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;   // send it behind the wall
                j++;
            }
        }
    }
}

How long it takes: one walk, O(n). Extra room: one wall and one temp, O(1).

Watch out for

• Decide where zero goes. Usually zero counts as positive, so test x < 0, not x <= 0.
• An empty array or an array of one number needs no special code; the loop does nothing.
• If the problem wants negatives on the right instead, walk from the right end, or swap the test.

What interviewers ask next

• Can you do it with fewer swaps? Use two fingers from both ends: move the left finger past negatives, the right finger past non-negatives, then swap. Each swap fixes two numbers at once.
• Keep the order and use O(1) room. Shifting like insertion sort is O(n^2). A merge sort style split that rotates blocks gets O(n log n).
• Three groups: negative, zero, positive. That is the Dutch national flag problem with three pointers: low, mid, high.
• Where have you seen this loop before? It is the partition step of quicksort, with the pivot set to 0.

Remember this

Grown-up words: the wall is a boundary index, this loop is the Lomuto partition from quicksort, keeping the order would make it a stable partition, and using no extra array means in place.