Rearrange Positive and Negative Numbers in an Array

Title: Rearrange Positive and Negative Numbers in an Array

Rearranging positive and negative numbers in an array is a classic interview exercise that tests how comfortably you can partition data in place using two pointers. In this guide, we will explore how to move every negative value to the left side of the array and every non-negative value to the right side using Java. You will learn the algorithm, see a complete program, walk through a trace, and review the common mistakes and interview follow-ups that come up with this problem.

Understanding the Problem

Given an array that mixes positive and negative integers in any order, our goal is to rearrange the elements so that every negative number appears before every non-negative number. The relative order inside each group does not need to be preserved, which lets us finish in a single pass and keep extra memory to O(1).

For example, consider the following input:

int[] arr = {4, -1, 7, -3, 2, -5};

After rearranging, a valid output is:

int[] arranged = {-5, -1, -3, 7, 2, 4};

Both halves are grouped correctly, even though the relative order inside each half has changed. That trade-off is what lets us use an in-place two-pointer swap and avoid allocating a second array.

Approach to Rearrange Positive and Negative Numbers

The idea is to walk one pointer from the left and another from the right. The left pointer skips values that are already negative, the right pointer skips values that are already non-negative, and whenever both pointers land on misplaced values we swap them.

Here are the steps:

1. Initialize left to 0 and right to arr.length - 1.
2. If arr[left] is negative, increment left because it is already in the correct half.
3. Otherwise, if arr[right] is non-negative, decrement right because it is also in the correct half.
4. Otherwise both pointers are on misplaced values, so swap arr[left] and arr[right], then increment left and decrement right.
5. Repeat the process while left < right.
6. When the loop ends, every negative number sits to the left of every non-negative number and the method returns.

Java Program to Rearrange Positive and Negative Numbers

Let us put the approach into a complete, compilable Java program:

import java.util.Arrays;

public class RearrangePositiveNegative {

    public static void rearrange(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[] arr = {1, -2, 3, -4, 5, -6};
        rearrange(arr);
        System.out.println("Rearranged Array: " + Arrays.toString(arr));
    }
}

Explanation of the Program

• The method rearrange partitions arr in place, so no new array is allocated and the caller sees the mutation directly.
• We first guard against a null reference or an array that is too small to need any work. A zero-sized or single-element array is already partitioned.
• left and right frame the unprocessed region. Everything to the left of left is already negative, and everything to the right of right is already non-negative.
• Inside the loop we choose between three branches: advance left, retreat right, or swap. Exactly one branch runs per iteration, which is what keeps the total work linear in arr.length.
• The swap uses a single int temp variable, so the extra memory used by the method is constant.
• When left meets or passes right, the entire array is partitioned and the method returns. The main method shows one quick run and prints the result with Arrays.toString.

Step-by-Step Trace

Let us trace the algorithm on the input {4, -1, 7, -3, 2, -5}, which has six elements and exercises every branch of the loop at least once.

After iteration 4, left is 3 and right is 2, so the loop condition fails and the method returns. At the end of each iteration, every element at an index below left is negative and every element at an index above right is non-negative. That invariant is the pedagogical heart of the two-pointer partition.

Examples

Here are three example runs that cover a few different starting arrangements of positive and negative values.

Example 1: Alternating signs

int[] arr = {1, -2, 3, -4, 5, -6};
rearrange(arr);

System.out.println("Rearranged Array: " + Arrays.toString(arr));
// Output: Rearranged Array: [-6, -2, -4, 3, 5, 1]

Example 2: Negative first, then clustered positives

int[] arr = {-7, 8, -9, 10, -11, 12};
rearrange(arr);

System.out.println("Rearranged Array: " + Arrays.toString(arr));
// Output: Rearranged Array: [-7, -11, -9, 10, 8, 12]

Example 3: Array containing a zero

int[] arr = {5, -3, 0, -8, 2, -1};
rearrange(arr);

System.out.println("Rearranged Array: " + Arrays.toString(arr));
// Output: Rearranged Array: [-1, -3, -8, 0, 2, 5]

Common Mistakes to Avoid

These are the slips a learner typically makes while implementing this partition:

• Treating zero inconsistently: zero may land in either half depending on whether you check < 0 or <= 0. Pick a convention upfront and apply the matching comparison on both pointer checks.
• Forgetting to advance both pointers after a swap: without the left++ and right--, the two misplaced values are swapped forever and the loop never terminates. Advance both indices as soon as the swap completes.
• Using left <= right as the loop condition: lets the pointers cross and processes the midpoint element twice, which can swap an already partitioned pair back. Use left < right so the midpoint is visited only once.
• Assuming the output preserves relative order: this partition is not stable, so {1, -2, 3, -4} becomes {-4, -2, 3, 1}, not {-2, -4, 1, 3}. If stability matters, choose a different algorithm.
• Skipping the null and tiny-array guard: calling rearrange with null throws a NullPointerException, and arrays of length zero or one are already partitioned. A single short guard covers both cases.

Edge Cases to Test

Before shipping the implementation, run it against this short checklist of boundary inputs:

• Empty array
• Single-element array
• Array of all positive numbers
• Array of all negative numbers
• Array containing one or more zeros
• Array already in partitioned order
• Null array reference
• Two-element array with the positive and negative in reversed order

Additional Considerations

The in-place two-pointer design keeps the implementation efficient on both axes. The time complexity is O(n) because each pointer moves monotonically from one end of the array toward the middle, so every index is visited at most once. The space complexity is O(1) because the swap uses a single int temp variable and no auxiliary data structure is allocated.

Keep in mind that this partition is not stable: elements inside each half may appear in a different relative order than in the input. When the problem requires preserving the original order of negatives among themselves and positives among themselves, consider an insertion-sort-style shift that costs O(n squared) time or a copy-based approach that uses an extra O(n) array.

The treatment of zero deserves a conscious decision. The sample program places zero on the non-negative side via the >= 0 check. If zero should sit with the negatives instead, flip the right-pointer test to > 0 and the left-pointer test to <= 0 so both halves agree on where zero belongs.

Interview Follow-up Questions

Once the base solution is working, interviewers often extend the problem in these directions:

• Can you preserve the original relative order inside each partition? Copy negatives in order into an auxiliary array, then append positives in order, which runs in O(n) time with O(n) extra space.
• How would you rearrange the array so that positives and negatives alternate? Partition first with the current algorithm, then walk the array swapping every pair of mismatched positions until one group is exhausted.
• What if the input arrives as a stream of unknown length? Buffer negatives in one queue and positives in another, then concatenate the queues at end of stream for an O(n) time and O(n) space pass.
• How would you partition an array that does not fit in memory? Split the input into chunks, partition each chunk on disk, and merge the chunk level results with an external two-way pass.
• Can you solve the problem with a single left-to-right scan? Yes, use a Lomuto-style index that tracks the next slot for a negative element and swap in each negative as it is seen, giving O(n) time and O(1) space.

Conclusion

Rearranging positive and negative numbers teaches a surprisingly deep lesson about in-place partitioning. The two-pointer walk runs in linear time and constant extra memory, and the invariant it maintains, that everything to the left of left is negative and everything to the right of right is non-negative, generalizes to many related interview problems.

Try the program on your own inputs, change the zero convention, and extend it to the stable or alternating variants when you are ready for a stiffer challenge. Happy coding!

You can learn more about array interview problems: Arrays