Rearrange Array in Alternating Positive and Negative Order

Title: Rearrange Array in Alternating Positive and Negative Order

Understanding the Problem

In this guide, you’ll learn how to rearrange an array of integers so that positive and negative numbers alternate with each other. Given an array that mixes positive and negative values in any order, the goal is to produce a new arrangement where a positive number is followed by a negative number, then a positive number again, and so on.

This problem shows up often in interviews because it tests whether you can split, track, and merge data using two separate pointers without losing the relative order of the original elements. Let’s explore the approach step by step, then build a complete Java program around it.

We treat 0 as a positive value for this problem, since it is neither strictly negative nor does it need special handling. If the count of positives and negatives is unequal, the leftover elements from the longer group are simply appended at the end in their original relative order.

Approach

The simplest way to solve this with clear, readable code is to separate the array into two lists, one for positives and one for negatives, and then merge them back together alternately. Here are the steps:

1. Create two empty lists, positives and negatives.
2. Walk through the input array once and append each element to positives if it is >= 0, otherwise append it to negatives.
3. Create a result array the same size as the input array, along with three index pointers: index for result, p for positives, and n for negatives.
4. While both p and n are within bounds, copy one element from positives then one from negatives into result, advancing all three pointers.
5. Once one list is exhausted, copy any remaining elements from the other list into result in order.
6. Return the completed result array.

This approach runs in O(n) time and uses O(n) extra space for the two helper lists. It also keeps the relative order of positives and negatives from the original array intact, which an in-place swap-based approach would not guarantee as easily.

Java Program

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RearrangePositiveNegative {

    public static int[] rearrange(int[] arr) {
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();

        for (int num : arr) {
            if (num >= 0) {
                positives.add(num);
            } else {
                negatives.add(num);
            }
        }

        int[] result = new int[arr.length];
        int index = 0;
        int p = 0;
        int n = 0;

        while (p < positives.size() && n < negatives.size()) {
            result[index++] = positives.get(p++);
            result[index++] = negatives.get(n++);
        }

        while (p < positives.size()) {
            result[index++] = positives.get(p++);
        }

        while (n < negatives.size()) {
            result[index++] = negatives.get(n++);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, -5, 2, -7, -1, 9, 6};
        int[] rearranged = rearrange(arr);
        System.out.println(Arrays.toString(rearranged));
    }
}

Explanation of the Program

• The rearrange method first walks through arr once, routing every element into either the positives list or the negatives list based on the num >= 0 check.
• A new result array is allocated with the same length as the input, since the output always contains exactly the same elements.
• Three pointers, index, p, and n, track the next slot to fill in result, the next unused element in positives, and the next unused element in negatives.
• The first while loop alternates copies from positives and negatives as long as both still have unused elements.
• The two trailing while loops drain whichever list still has leftover elements once the other one runs out, appending them in their original order.
• The main method demonstrates the method on a sample array and prints the rearranged result.

Step-by-Step Trace

Let’s trace rearrange on the input [4, -5, 2, -7, -1, 9, 6], which produces positives = [4, 2, 9, 6] and negatives = [-5, -7, -1], so the target output is [4, -5, 2, -7, 9, -1, 6].

At the end of each iteration, result holds every positive and negative processed so far in strict alternation, and once negatives is exhausted, the remaining elements of positives are simply appended in their original relative order.

Examples

Example 1: Equal Counts of Positives and Negatives

When the array has an equal number of positives and negatives, the merge loop alone produces the full result with no leftover elements.

int[] arr1 = {-1, 2, -3, 4, -5, 6};
int[] result1 = RearrangePositiveNegative.rearrange(arr1);
System.out.println(Arrays.toString(result1));
// Input:  [-1, 2, -3, 4, -5, 6]
// Output: [2, -1, 4, -3, 6, -5]

Example 2: No Negative Numbers

When negatives is empty, the merge loop never runs because n < negatives.size() is false from the start, and the array is returned unchanged by the leftover-positives loop.

int[] arr2 = {1, 2, 3, 4};
int[] result2 = RearrangePositiveNegative.rearrange(arr2);
System.out.println(Arrays.toString(result2));
// Input:  [1, 2, 3, 4]
// Output: [1, 2, 3, 4]

Example 3: More Negatives Than Positives

When positives runs out first, the final while loop drains the remaining negatives, so the output ends with a run of negative numbers instead of a perfect alternation.

int[] arr3 = {-1, -2, -3, 1};
int[] result3 = RearrangePositiveNegative.rearrange(arr3);
System.out.println(Arrays.toString(result3));
// Input:  [-1, -2, -3, 1]
// Output: [1, -1, -2, -3]

Common Mistakes to Avoid

A few mistakes come up again and again when solving this problem, especially under interview time pressure.

• Treating 0 as negative – routing 0 into the negatives list changes the output order for arrays containing zero. Check num >= 0, not num > 0, when deciding which list an element belongs to.
• Forgetting the leftover elements – stopping after the first merge loop silently drops every element past the shorter list, so the output array ends with trailing zeros. Always drain whichever list still has elements with the two trailing while loops.
• Starting the alternation with the wrong sign – some variations of this problem require the output to start with whichever sign appeared first in the input, not always positive. Check the problem statement before assuming positives always lead.
• Reusing the input array pointers incorrectly – mixing up p and n with index when copying into result causes an ArrayIndexOutOfBoundsException or silently overwrites values. Keep each pointer scoped to the exact collection it tracks.
• Assuming the counts are always equal – hardcoding arr.length / 2 as the loop bound breaks whenever positives and negatives are not evenly split. Use the actual sizes of positives and negatives as the loop conditions instead.

Additional Considerations

The algorithm makes a single pass to split the array and a second pass to merge it back, so the overall time complexity is O(n). Space complexity is also O(n) because of the two helper lists and the new result array; an in-place variant exists using rotations, but it trades this simplicity for O(n) time with a much higher constant factor.

Edge Cases to Test

Walk through these inputs before calling the solution complete.

• Empty array
• Single-element array
• All positive elements
• All negative elements
• Equal counts of positives and negatives
• More positives than negatives
• More negatives than positives
• Array containing 0

The all-positive and all-negative cases matter because they force one of the trailing while loops to do all the work, and the 0 case checks that the boundary condition in the split step is written correctly.

Interview Follow-up Questions

Once you can explain the base solution, expect the interviewer to push further with questions like these.

• Can you solve this in-place without extra arrays? – swap elements using two pointers that scan for a misplaced sign and rotate the subarray between them, trading the simplicity of the list-based approach for O(1) extra space.
• What if the relative order within positives and negatives does not need to be preserved? – use a single pass with two pointers scanning from both ends, swapping whenever the sign at the wrong position is found, which avoids any extra storage.
• What if you only have a singly linked list instead of an array? – maintain two dummy head nodes, one for positives and one for negatives, and splice each node into the matching list while traversing once, then merge the two lists alternately.
• What if the array is too large to fit in memory? – process it in chunks, writing each chunk’s positives and negatives to separate temporary files, then interleave the files during a final merge pass, similar to external merge sort.

Conclusion

Rearranging an array into alternating positive and negative order comes down to a clean split-then-merge pattern: separate the elements by sign, then weave them back together while any leftover run from the longer list is appended at the end. The same two-pointer merging idea reappears in problems like merging sorted arrays and partitioning by a pivot, so it is well worth practicing until it feels automatic.

Try adapting the RearrangePositiveNegative class to your own test cases, including the edge cases listed above, to make sure your understanding holds up under pressure. You can learn more about array-based problems like this one in our Arrays category.