{x}
blog image

Rearrange Array Elements by Sign

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:

  1. Every consecutive pair of integers have opposite signs.
  2. For all integers with the same sign, the order in which they were present in nums is preserved.
  3. 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]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

 

Constraints:

  • 2 <= nums.length <= 2 * 105
  • nums.length is even
  • 1 <= |nums[i]| <= 105
  • nums consists of equal number of positive and negative integers.

 

It is not required to do the modifications in-place.

Solution Explanation for Rearrange Array Elements by Sign

This problem requires rearranging an array of integers such that consecutive elements have opposite signs, while maintaining the original order of positive and negative numbers separately. The solution uses a two-pointer approach for efficiency.

Approach: Two Pointers

The core idea is to utilize two pointers, one for even indices (i) and one for odd indices (j), to place positive and negative numbers alternately in the result array.

  1. Initialization:

    • Create a result array (ans) of the same size as the input array (nums).
    • Initialize i to 0 (even index) and j to 1 (odd index).

  2. Iteration:

    • Iterate through the input array nums.
    • For each element x:
      • If x is positive, place it at ans[i] and increment i by 2 (to maintain the alternating pattern).
      • If x is negative, place it at ans[j] and increment j by 2.

  3. Return:

    • Return the ans array.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. This is because we iterate through the input array once.
  • Space Complexity: O(n), as we create a new array ans of the same size as the input array to store the result. This is not in-place, but the problem doesn't require an in-place solution.

Code Implementation in Multiple Languages

The following code implementations demonstrate the two-pointer approach in various programming languages:

Python

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        pos_ptr, neg_ptr = 0, 1
        for num in nums:
            if num > 0:
                ans[pos_ptr] = num
                pos_ptr += 2
            else:
                ans[neg_ptr] = num
                neg_ptr += 2
        return ans

Java

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int posPtr = 0, negPtr = 1;
        for (int num : nums) {
            if (num > 0) {
                ans[posPtr] = num;
                posPtr += 2;
            } else {
                ans[negPtr] = num;
                negPtr += 2;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int posPtr = 0, negPtr = 1;
        for (int num : nums) {
            if (num > 0) {
                ans[posPtr] = num;
                posPtr += 2;
            } else {
                ans[negPtr] = num;
                negPtr += 2;
            }
        }
        return ans;
    }
};

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var rearrangeArray = function(nums) {
    const n = nums.length;
    const ans = new Array(n).fill(0);
    let posPtr = 0, negPtr = 1;
    for (let num of nums) {
        if (num > 0) {
            ans[posPtr] = num;
            posPtr += 2;
        } else {
            ans[negPtr] = num;
            negPtr += 2;
        }
    }
    return ans;
};

These code snippets all follow the same logic described above, achieving the desired rearrangement efficiently. The choice of language depends on personal preference and project requirements.