Rearrange Array Elements by Sign

How it works

We can build the result in a single pass using two pointers. One pointer tracks the next even index (for positive numbers), and the other tracks the next odd index (for negative numbers). As we scan through the input, we place each number at the appropriate position and advance the corresponding pointer by 2.

Steps

1. Initialize i = 0 (for positive numbers at even indices) and j = 1 (for negative numbers at odd indices).
2. Create a result array of the same size.
3. For each number in the input:
   • If positive, place it at res[i] and increment i by 2.
   • If negative, place it at res[j] and increment j by 2.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n) for the output array.

Things to watch for

Confusing Index Parity with Sign Requirements

A frequent mistake is mixing up which indices should hold positive versus negative numbers. Remember: even indices (0, 2, 4, ...) hold positive numbers, and odd indices (1, 3, 5, ...) hold negative numbers. Getting this reversed produces an invalid result.

Not Preserving Relative Order

The problem requires maintaining the relative order of positive numbers among themselves and negative numbers among themselves. Simply swapping elements in place without careful tracking can violate this constraint. Using separate lists or two-pointer placement ensures order is preserved.

Forgetting to Handle Zero

While the problem guarantees no zeros in the input, some implementations incorrectly treat zero as positive (since 0 > 0 is false) or fail to account for the sign check properly. Ensure your sign comparison logic matches the problem constraints exactly.

from typing import List

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        i, j = 0, 1
        res = [0] * len(nums)
        for k in range(len(nums)):
            if nums[k] > 0:
                res[i] = nums[k]
                i += 2
            else:
                res[j] = nums[k]
                j += 2
        return res

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int i = 0, j = 1;
        vector<int> res(nums.size());
        for (int k = 0; k < nums.size(); k++) {
            if (nums[k] > 0) {
                res[i] = nums[k];
                i += 2;
            } else {
                res[j] = nums[k];
                j += 2;
            }
        }
        return res;
    }
};