Move Negative Numbers to the Left of an Array

Title: Move Negative Numbers to the Left of an Array

In this guide, you’ll learn how to rearrange an integer array so that every negative number sits on the left and every non-negative number sits on the right, all in a single pass and without any extra memory. We’ll build the two-pointer solution step by step, trace it on a concrete input, and walk through the common mistakes and interview follow-ups you should expect on this problem.

Understanding the Problem

You are given an array of integers that mixes negative and non-negative values in any order. Your job is to shuffle the elements so that every negative value appears before every non-negative value. Although you can solve this with a copy and two passes, the interesting version performs the rearrangement in place using a single traversal of the array.

The algorithm does not have to preserve the relative order of the negatives or of the non-negatives. If it did, you would need either O(n) extra memory or a stable O(n log n) sort. Dropping that stability requirement is exactly what unlocks the elegant two-pointer solution.

Approach: Two-Pointer Partition

We walk two pointers toward each other from the two ends of the array, swapping only when the left pointer sees a non-negative value and the right pointer sees a negative value. Any time one pointer already looks at a correctly placed element, we simply advance that pointer and skip the swap entirely.

1. If the array is null or has fewer than two elements, there is nothing to do, so return immediately.
2. Initialize left to 0 and right to arr.length - 1.
3. While left is less than or equal to right, inspect arr[left] and arr[right].
4. If arr[left] is negative, it is already in the correct region, so advance left.
5. Otherwise, if arr[right] is non-negative, it is already in the correct region, so decrement right.
6. If neither condition holds, arr[left] is non-negative and arr[right] is negative, so swap them and move both pointers inward.
7. Terminate when the pointers cross. At that point every negative sits to the left of every non-negative.

Java Program

Here is the complete program. It defines the moveNegativesLeft method and exercises it on a mixed array in main. You can paste it into a file named MoveNegatives.java and run it as is.

import java.util.Arrays;

public class MoveNegatives {
    public static void moveNegativesLeft(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int left = 0;
        int 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 main(String[] args) {
        int[] numbers = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
        System.out.println("Before: " + Arrays.toString(numbers));
        moveNegativesLeft(numbers);
        System.out.println("After:  " + Arrays.toString(numbers));
    }
}

Explanation of the Program

The moveNegativesLeft method begins with a guard that returns early for arrays that are null or too small to rearrange. From there, the main while loop advances whichever pointer is cheaper at each step. If arr[left] is already negative we only move left, which skips over a correctly placed element without a swap. Likewise, if arr[right] is already non-negative we only move right.

The expensive branch, the swap, only fires when both pointers point at misplaced elements. That guarantees every element is written at most once across the entire run, which is what keeps the method linear in time and constant in space. The main method constructs a sample array and prints it before and after the call so you can confirm the partitioning visually; Arrays.toString keeps the output compact and readable.

Step-by-Step Trace

To see the pointers in action, consider the input {4, -2, 7, -1, -3} with the goal of placing every negative before every non-negative. The table below records one row per iteration of the while loop.

At the end of each iteration, every element in arr[0..left-1] is negative and every element in arr[right+1..n-1] is non-negative, and the window arr[left..right] is the still-to-be-partitioned region. That invariant is the pedagogical payoff: once left passes right, the two regions meet and the whole array is partitioned.

Examples

Example 1: Mixed negatives and positives

When the input mixes both signs, the method rearranges them so that every negative lands before every non-negative. The exact ordering within each group is not preserved, which is the price of running in place without extra memory.

int[] input = {-1, 2, -3, 4, 5, -6};
moveNegativesLeft(input);
// After: [-1, -6, -3, 4, 5, 2]
// All negatives sit before all non-negatives; order within each group is not preserved.

Example 2: Array with no negatives

If every element is already non-negative, the right pointer walks all the way to the left pointer without triggering a single swap. The loop still runs O(n) comparisons, but it performs zero writes, so the array leaves memory exactly as it entered.

int[] input = {1, 2, 3, 4, 5};
moveNegativesLeft(input);
// After: [1, 2, 3, 4, 5]
// No negatives to move, so the array is unchanged.

Common Mistakes to Avoid

These are the mistakes a learner typically makes on this partitioning problem. Each one is specific to the two-pointer sign check, not generic programming advice.

• Treating zero as negative – using arr[left] <= 0 as the predicate groups zeros with the negatives, which contradicts the usual “negative to the left, non-negative to the right” statement. Keep the strict < 0 and >= 0 checks so zero stays on the non-negative side.
• Using left < right instead of left <= right – leaves the middle element unprocessed when the array length is odd, so an input like {1, -2, 3} returns with arr[1] never inspected. Use left <= right so every index is covered before the loop exits.
• Forgetting to advance pointers after a swap – creates an infinite loop because the same two indices are compared forever. Always run left++ and right-- immediately after swapping.
• Expecting stable order – this partition is unstable, so a test that asserts the exact post-order of negatives (or positives) will fail even on correct code. If stability matters, switch to an auxiliary array or a stable algorithm.
• Returning a new array from an in-place method – callers expect moveNegativesLeft to mutate the array they passed in, so returning a new one silently drops the mutation. Keep the return type void and operate on arr directly.

Edge Cases to Test

Walking through the following boundary inputs flushes out most off-by-one and null-handling bugs before they reach production or an interview whiteboard.

• Empty array
• Single-element array
• All negative elements
• All non-negative elements
• Array containing only zeros
• Odd-length array where the middle element is the pivot of interest
• Null array reference
• Array containing Integer.MIN_VALUE

Additional Considerations

Time complexity is O(n) because each of the two pointers takes at most n/2 steps and together they visit every index exactly once. Space complexity is O(1) since the swap uses one temporary integer and no auxiliary data structure grows with the input size.

If you need to preserve the relative order of negatives and non-negatives, this algorithm will not work. A stable in-place partition requires either O(n log n) time (via merge-sort-style partitioning) or O(n) extra space (via a copy pass). The two-pointer version trades stability for a single linear pass with no extra memory.

The algorithm is also friendly to the CPU cache: the two pointers scan sequentially from opposite ends of the array, which prefetches well, and the swap happens at most once for every two inspected elements. On modern hardware this is close to as fast as a linear scan can be. Note that Integer.MIN_VALUE is still negative, so the predicate arr[i] < 0 classifies it correctly without any special case, which is why that boundary matters in the edge-case list above.

Interview Follow-up Questions

A real interviewer rarely stops at the base problem. Here are the “what if” variants you should be ready for, ordered from easiest to hardest.

• What if you must preserve the relative order of negatives and non-negatives? – allocate an auxiliary array of size n, make one pass copying negatives first and one pass copying non-negatives, then write the result back for O(n) time with O(n) extra space.
• How would you partition into three regions – negatives, zeros, then positives – in a single pass? – adapt the Dutch National Flag algorithm with three pointers (low, mid, high) and three branches on sign.
• What if the array is immutable and you can only return the indices in partitioned order? – return an int[] of indices sorted by sign; the original array stays untouched and the extra space is O(n).
• How would you partition a file of integers that does not fit in memory? – stream the input, write negatives to one output file and non-negatives to another, then concatenate the two files. The pattern generalises to external partitioning.
• How would you parallelise this across multiple cores? – split the array into chunks, partition each chunk independently, then merge the partitioned chunks by swapping across chunk boundaries wherever a non-negative on the left meets a negative on the right.

Conclusion

The two-pointer partition is a small, powerful idiom that solves the “move negatives to the left” problem in a single pass with constant extra memory. The core insight is that each pointer advances only when it already sees a correctly placed element, which keeps the number of writes bounded by the number of truly misplaced pairs.

Try adapting the code to the three-way Dutch National Flag variant above, or generalise it to partition by any predicate (even vs odd, less than k vs greater than k, and so on). Once that pattern feels natural, most sign-based and category-based array questions in an interview will fall out of the same template. You can learn more Array problems and solutions here: Arrays category.