Rearrange array in alternating positive and negative items
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]
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).