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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

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

Time & Space Complexity

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

2. Group Numbers Into Two Arrays

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

Time & Space Complexity

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

3. Two Pointers

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

Time & Space Complexity

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