Rearrange array in alternating positive and negative items

Hard

Problem

Rearrange the array so positive and negative numbers alternate, keeping their original relative order within each sign. Start with a positive number. If one sign runs out, append the leftovers at the end. Treat 0 as positive. The hard version asks for O(1) extra space.

Example 1

Input:  [1, 2, 3, -4, -1, 4]
Output: [1, -4, 2, -1, 3, 4]

Also asked as: Rearrange the array in alternating positive and negative items with O(1) extra space

Test cases

Case 1

Input:    [1,2,3,-4,-1,4]
Expected: [1,-4,2,-1,3,4]

Case 2

Input:    [-5,-2,5,2,4,7,1,8,0,-8]
Expected: [5,-5,2,-2,4,-8,7,1,8,0]

Case 3

Input:    [-1,2,-3,4]
Expected: [2,-1,4,-3]

Case 4

Input:    [1,2,3]
Expected: [1,2,3]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. In-place rotation (order preserved)

Time O(n²)Space O(1)

Scan for the first out-of-place pair; right-rotate the subarray from that index to the wrong element so it slots in. O(n²) worst but O(1) space and stable.

function rearrange(a) {
const rotateRight = (arr, lo, hi) => {
const t = arr[hi];
for (let k = hi; k > lo; k--) arr[k] = arr[k - 1];
arr[lo] = t;
};
let outOfPlace = -1;
for (let i = 0; i < a.length; i++) {
if (outOfPlace >= 0) {
const wrongSign = (a[i] >= 0 && a[outOfPlace] < 0) || (a[i] < 0 && a[outOfPlace] >= 0);
if (wrongSign) {
rotateRight(a, outOfPlace, i);
outOfPlace = i - outOfPlace >= 2 ? outOfPlace + 2 : -1;
}
}
if (outOfPlace === -1) {
const misplaced = (a[i] >= 0 && i % 2 === 1) || (a[i] < 0 && i % 2 === 0);
if (misplaced) outOfPlace = i;
}
}
return a;
}

If order need not be preserved: two-pointer partition into negatives/positives, then swap alternate elements — O(n), O(1).