036.md

2149. Rearrange Array Elements by Sign

Difficulty: 🟡

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

You should rearrange the elements of nums such that the modified 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.

Examples:

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.

Solutions

O(n) solution in Python3

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        result = [0] * len(nums)

        i, j = 0, 1
        for num in nums:
            if num > 0:
                result[i] = num
                i += 2
            else:
                result[j] = num
                j += 2

        return result

The given solution rearranges the elements of the nums array to satisfy the conditions mentioned in the problem statement.

The algorithm works as follows:

1. Initialize a result array with the same length as the nums array, filled with zeros.
2. Initialize two pointers, i and j, to 0 and 1, respectively. These pointers will be used to track the positions where positive and negative integers should be placed in the result array.
3. Iterate through each element, num, in the nums array:
   • If num is positive, assign it to the ith position in the result array and increment i by 2 to maintain the gap between positive integers.
   • If num is negative, assign it to the jth position in the result array and increment j by 2 to maintain the gap between negative integers.
4. Return the result array, which represents the rearranged array satisfying the given conditions.

The algorithm assigns positive integers to even positions (i) and negative integers to odd positions (j) in the result array, preserving the order of integers with the same sign.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the nums array. The algorithm iterates through each element of the nums array once and performs constant-time operations at each iteration.

The space complexity of the algorithm is O(n) as it uses additional space to store the result array, which has the same length as the nums array.

Summary

The given solution rearranges the elements of the nums array to satisfy the conditions mentioned in the problem statement. It has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.