Rearrange Array Elements by Sign
Medium· two pointers
Problem
An even-length array contains the same number of positive and negative integers. Rearrange it so that signs alternate starting with a positive value, while keeping the positives in their original order and the negatives in theirs.
Examples
Input: nums = [3,-2,-5,1,4,-7]
Output: [3,-2,1,-5,4,-7]
Positives 3, 1, 4 go to even indices and negatives -2, -5, -7 to odd indices.
Input: nums = [-4,9]
Output: [9,-4]
Constraints
- • 2 <= nums.length <= 2 * 10^5
- • nums.length is even
- • No element is zero
Hints & approach
Hint 1
Where does the k-th positive number end up in the result?
Hint 2
Use two write indices: one stepping through even positions, one through odd positions.
Approachtry the hints first
Allocate a result array and two pointers, pos = 0 and neg = 1. Scan the input once; place each positive value at pos and advance it by 2, and place each negative value at neg and advance it by 2. Because both groups are written in scan order, relative order is preserved, and the alternating pattern follows from the even/odd indices.
Time O(n) · Space O(n)