2149. Rearrange Array Elements by Sign - Explanation

Description

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should return the array of nums such that the the array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4]

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

Example 2:

Input: nums = [-1,1]

Output: [1,-1]

Constraints:

2 <= nums.length <= 200,000
nums.length is even.
1 <= |nums[i]| <= 100,000
nums consists of equal number of positive and negative integers.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Understanding array indexing, traversal, and in-place modifications
Two Pointers Technique - Using multiple pointers to track different positions in an array simultaneously

1. Brute Force

Intuition

We process the array position by position. At each index, we check if the current element has the correct sign (positive at even indices, negative at odd indices). If not, we search forward for an element with the correct sign and shift all elements in between to make room for it.

Algorithm

Iterate through each index i:
- If index is even and nums[i] > 0, or index is odd and nums[i] < 0, continue.
- Otherwise, find the next element with the opposite sign at position j.
- Save nums[j], then shift all elements from i to j-1 one position right.
- Place the saved element at position i.
Return the modified array.

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            if ((i % 2 == 0 and nums[i] > 0) or
                (i % 2 == 1 and nums[i] < 0)):
                continue

            j = i + 1
            while j < n and ((nums[j] > 0) == (nums[i] > 0)):
                j += 1

            tmp = nums[j]
            while j > i:
                nums[j] = nums[j - 1]
                j -= 1
            nums[i] = tmp
        return nums

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    rearrangeArray(nums) {
        let n = nums.length;
        for (let i = 0; i < n; i++) {
            if ((i % 2 === 0 && nums[i] > 0) || (i % 2 === 1 && nums[i] < 0)) {
                continue;
            }

            let j = i + 1;
            while (j < n && nums[j] > 0 === nums[i] > 0) {
                j++;
            }

            let temp = nums[j];
            while (j > i) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[i] = temp;
        }
        return nums;
    }
}

class Solution {
    func rearrangeArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        let n = nums.count
        for i in 0..<n {
            if (i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0) {
                continue
            }

            var j = i + 1
            while j < n && (nums[j] > 0) == (nums[i] > 0) {
                j += 1
            }

            let tmp = nums[j]
            while j > i {
                nums[j] = nums[j - 1]
                j -= 1
            }
            nums[i] = tmp
        }
        return nums
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Group Numbers Into Two Arrays

Intuition

Since we need to alternate positive and negative numbers while preserving their relative order, we can first separate them into two lists. Then we interleave them back into the original array: positive numbers go to even indices, negative numbers go to odd indices.

Algorithm

Create two separate lists: pos for positive numbers and neg for negative numbers.
Iterate through the input array and add each number to the appropriate list.
Rebuild the array by interleaving:
- Place pos[i] at index 2 * i.
- Place neg[i] at index 2 * i + 1.
Return the result.

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos, neg = [], []
        for num in nums:
            if num > 0:
                pos.append(num)
            else:
                neg.append(num)

        i = 0
        while 2 * i < len(nums):
            nums[2 * i] = pos[i]
            nums[2 * i + 1] = neg[i]
            i += 1
        return nums

public class Solution {
    public int[] rearrangeArray(int[] nums) {
        List<Integer> pos = new ArrayList<>();
        List<Integer> neg = new ArrayList<>();
        for (int num : nums) {
            if (num > 0) {
                pos.add(num);
            } else {
                neg.add(num);
            }
        }

        int i = 0;
        while (2 * i < nums.length) {
            nums[2 * i] = pos.get(i);
            nums[2 * i + 1] = neg.get(i);
            i++;
        }
        return nums;
    }
}

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> pos, neg;
        for (int num : nums) {
            if (num > 0) {
                pos.push_back(num);
            } else {
                neg.push_back(num);
            }
        }

        int i = 0;
        while (2 * i < nums.size()) {
            nums[2 * i] = pos[i];
            nums[2 * i + 1] = neg[i];
            i++;
        }
        return nums;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    rearrangeArray(nums) {
        const pos = [],
            neg = [];
        for (const num of nums) {
            if (num > 0) {
                pos.push(num);
            } else {
                neg.push(num);
            }
        }

        let i = 0;
        while (2 * i < nums.length) {
            nums[2 * i] = pos[i];
            nums[2 * i + 1] = neg[i];
            i++;
        }
        return nums;
    }
}

public class Solution {
    public int[] RearrangeArray(int[] nums) {
        List<int> pos = new List<int>();
        List<int> neg = new List<int>();

        foreach (int num in nums) {
            if (num > 0) pos.Add(num);
            else neg.Add(num);
        }

        int i = 0;
        while (2 * i < nums.Length) {
            nums[2 * i] = pos[i];
            nums[2 * i + 1] = neg[i];
            i++;
        }

        return nums;
    }
}

func rearrangeArray(nums []int) []int {
    var pos, neg []int
    for _, num := range nums {
        if num > 0 {
            pos = append(pos, num)
        } else {
            neg = append(neg, num)
        }
    }

    i := 0
    for 2*i < len(nums) {
        nums[2*i] = pos[i]
        nums[2*i+1] = neg[i]
        i++
    }
    return nums
}

class Solution {
    fun rearrangeArray(nums: IntArray): IntArray {
        val pos = mutableListOf<Int>()
        val neg = mutableListOf<Int>()

        for (num in nums) {
            if (num > 0) pos.add(num)
            else neg.add(num)
        }

        var i = 0
        while (2 * i < nums.size) {
            nums[2 * i] = pos[i]
            nums[2 * i + 1] = neg[i]
            i++
        }
        return nums
    }
}

class Solution {
    func rearrangeArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        var pos = [Int]()
        var neg = [Int]()

        for num in nums {
            if num > 0 {
                pos.append(num)
            } else {
                neg.append(num)
            }
        }

        var i = 0
        while 2 * i < nums.count {
            nums[2 * i] = pos[i]
            nums[2 * i + 1] = neg[i]
            i += 1
        }
        return nums
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Two Pointers

Intuition

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.

Algorithm

Initialize i = 0 (for positive numbers at even indices) and j = 1 (for negative numbers at odd indices).
Create a result array of the same size.
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.
Return res.

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

public class Solution {
    public int[] rearrangeArray(int[] nums) {
        int i = 0, j = 1;
        int[] res = new int[nums.length];
        for (int k = 0; k < nums.length; k++) {
            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;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    rearrangeArray(nums) {
        let i = 0,
            j = 1;
        const res = new Array(nums.length);
        for (let k = 0; k < nums.length; k++) {
            if (nums[k] > 0) {
                res[i] = nums[k];
                i += 2;
            } else {
                res[j] = nums[k];
                j += 2;
            }
        }
        return res;
    }
}

public class Solution {
    public int[] RearrangeArray(int[] nums) {
        int i = 0, j = 1;
        int[] res = new int[nums.Length];

        for (int k = 0; k < nums.Length; k++) {
            if (nums[k] > 0) {
                res[i] = nums[k];
                i += 2;
            } else {
                res[j] = nums[k];
                j += 2;
            }
        }

        return res;
    }
}

class Solution {
    fun rearrangeArray(nums: IntArray): IntArray {
        var i = 0
        var j = 1
        val res = IntArray(nums.size)
        for (k in nums.indices) {
            if (nums[k] > 0) {
                res[i] = nums[k]
                i += 2
            } else {
                res[j] = nums[k]
                j += 2
            }
        }
        return res
    }
}

class Solution {
    func rearrangeArray(_ nums: [Int]) -> [Int] {
        var i = 0, j = 1
        var res = [Int](repeating: 0, count: nums.count)
        for k in 0..<nums.count {
            if nums[k] > 0 {
                res[i] = nums[k]
                i += 2
            } else {
                res[j] = nums[k]
                j += 2
            }
        }
        return res
    }
}

Time & Space Complexity

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

Common Pitfalls

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.