Alternate positive and negative numbers

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Rearrange array so positive and negative numbers alternate. Two-pointer or collect and interleave.

Algorithm

1Collect positives and negatives separately. Interleave: place at even/odd indices.
2If counts differ: append remaining at end.

Common Pitfalls

•Maintain relative order if required. If counts differ, extras go at end. O(n) with extra space.

Alternate positive and negative numbers.java

Java

// Approach: Two-pass: collect positives and negatives separately, then merge alternately in-place.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    void rearrange(ArrayList<Integer> arr) {
        Queue<Integer> p = new LinkedList<>();
        Queue<Integer> n = new LinkedList<>();

        for (int i = 0; i < arr.size(); i++) {
            if (arr.get(i) < 0)
                n.add(arr.get(i));
            else
                p.add(arr.get(i));
        }

        int i = 0;
        while (!p.isEmpty() && !n.isEmpty()) {
            arr.set(i++, p.poll());
            arr.set(i++, n.poll());
        }

        while (!p.isEmpty())
            arr.set(i++, p.poll());

        while (!n.isEmpty())
            arr.set(i++, n.poll());
    }
}

Was this solution helpful?