Rearrange Array Elements by Sign

Problem 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 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.

Key Insights

• The array contains an equal number of positive and negative integers, which ensures that a valid arrangement is always possible.
• The solution requires maintaining the original order of positive and negative integers while rearranging them.
• A two-pointer technique can be effectively used to build the result array by alternating between positive and negative integers.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use two separate lists to store positive and negative integers. We will iterate through the input array and populate these lists. Then, we will construct the result array by alternating between elements from the positive and negative lists, starting with a positive integer. This approach maintains the original order of integers while fulfilling the conditions of the problem.

Code Solutions