Rearrange Array Elements by Sign

Rearrange Array Elements by Sign

What is this problem about?

The Rearrange Array Elements by Sign problem gives you an array of equal numbers of positive and negative integers. Rearrange it so positives and negatives alternate, starting with a positive, while maintaining relative order within each sign group. This coding problem uses a two-pointer approach to place elements at correct positions simultaneously. The array, two pointers, and simulation interview pattern is the core.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests in-place array rearrangement with ordering constraints. The key challenge is maintaining relative order for both positives and negatives while interleaving them — requiring two simultaneous read pointers and one write process.

Algorithmic pattern used

Two-pointer output construction. Maintain two pointers: pos (next positive output index, starts at 0, increments by 2) and neg (next negative output index, starts at 1, increments by 2). Scan through the array: positive elements go to result[pos], negative elements go to result[neg]. This preserves relative order within each sign group.

Example explanation

arr=[3,-1,-2,4,5,-3]. Positives: [3,4,5]. Negatives: [-1,-2,-3]. Result: [3,-1,4,-2,5,-3]. Position 0=3, 2=4, 4=5 (positives). Position 1=-1, 3=-2, 5=-3 (negatives). Result: [3,-1,4,-2,5,-3].

Common mistakes candidates make

• Trying in-place rearrangement (sorting-based approaches don't preserve relative order).
• Not understanding the problem guarantees equal positive/negative counts.
• Using sorting which doesn't preserve relative order.
• Off-by-one in output pointer increments.

Interview preparation tip

Rearrange Array Elements by Sign teaches the two-output-pointer pattern: two pointers writing into separate positions of the result array simultaneously. This pattern appears in "merge two sorted arrays" and "interleave streams." The key insight: since sizes are equal and structure is fixed (pos, neg, pos, neg...), compute target positions directly rather than simulating the rearrangement.