Problem Description

You are given an integer array nums with an even length. The array contains an equal number of positive and negative integers.

Your task is to rearrange the array so that it satisfies these three conditions:

1. Alternating signs: Every consecutive pair of integers must have opposite signs (positive followed by negative, or negative followed by positive)

2. Preserve relative order: Among all positive integers, they should appear in the same order as they were in the original array. The same rule applies to negative integers - their relative order must be maintained

3. Start with positive: The rearranged array must begin with a positive integer

For example, if nums = [3, 1, -2, -5, 2, -4]:

• The positive integers in order are: [3, 1, 2]
• The negative integers in order are: [-2, -5, -4]
• The result would be: [3, -2, 1, -5, 2, -4]

The solution uses a two-pointer approach where even indices (0, 2, 4, ...) are filled with positive numbers and odd indices (1, 3, 5, ...) are filled with negative numbers. This ensures the alternating pattern while maintaining the relative order of elements with the same sign.

Intuition

Since we need to create an alternating pattern of positive and negative numbers while preserving their relative order, we can think about where each type of number should go in the final array.

Given that the array must start with a positive number and alternate signs, we can deduce a pattern:

• Position 0: positive
• Position 1: negative
• Position 2: positive
• Position 3: negative
• And so on...

This means all even indices (0, 2, 4, ...) should contain positive numbers, and all odd indices (1, 3, 5, ...) should contain negative numbers.

The key insight is that we don't need to sort or compare elements - we just need to place them in the correct positions. Since we want to preserve the relative order within each sign group, we can simply iterate through the original array once and place each element in the next available position of its type.

We can use two pointers to track the next available position for each sign:

• Pointer i starts at 0 and moves by 2 each time (0, 2, 4, ...) for positive numbers
• Pointer j starts at 1 and moves by 2 each time (1, 3, 5, ...) for negative numbers

As we encounter each number in the original array, we check its sign and place it at the corresponding pointer's position, then advance that pointer by 2. This ensures both the alternating pattern and the preservation of relative order within each sign group.

Learn more about Two Pointers patterns.

Solution Approach

The solution implements a two-pointer technique to efficiently rearrange the array in a single pass.

Step-by-step implementation:

1. Initialize the result array: Create an array ans of the same length as nums to store the rearranged elements.

   ans = [0] * len(nums)

2. Set up two pointers:

   • Initialize i = 0 to track positions for positive numbers (even indices)
   • Initialize j = 1 to track positions for negative numbers (odd indices)

   i, j = 0, 1

3. Single-pass placement: Iterate through each element x in the original array nums:

   • If x > 0 (positive number):
     • Place it at ans[i]
     • Move i forward by 2 to the next even index (i += 2)
   • If x < 0 (negative number):
     • Place it at ans[j]
     • Move j forward by 2 to the next odd index (j += 2)

   for x in nums:
       if x > 0:
           ans[i] = x
           i += 2
       else:
           ans[j] = x
           j += 2

4. Return the result: After processing all elements, ans contains the properly rearranged array.

Why this works:

• By incrementing pointers by 2, we ensure positive numbers only go to even indices (0, 2, 4, ...) and negative numbers only go to odd indices (1, 3, 5, ...)
• Processing elements in their original order naturally preserves the relative order within each sign group
• The alternating pattern is guaranteed by the index assignment strategy

Time Complexity: O(n) - single pass through the array
Space Complexity: O(n) - for the result array (not counting it as extra space since it's required for the output)

Example Walkthrough

Let's walk through the solution with nums = [3, 1, -2, -5, 2, -4]:

Initial Setup:

• Create result array: ans = [_, _, _, _, _, _] (length 6)
• Set pointers: i = 0 (for positive numbers), j = 1 (for negative numbers)

Processing each element:

1. Element: 3 (positive)

   • Place at ans[i] → ans[0] = 3
   • Result: ans = [3, _, _, _, _, _]
   • Update: i = 0 + 2 = 2

2. Element: 1 (positive)

   • Place at ans[i] → ans[2] = 1
   • Result: ans = [3, _, 1, _, _, _]
   • Update: i = 2 + 2 = 4

3. Element: -2 (negative)

   • Place at ans[j] → ans[1] = -2
   • Result: ans = [3, -2, 1, _, _, _]
   • Update: j = 1 + 2 = 3

4. Element: -5 (negative)

   • Place at ans[j] → ans[3] = -5
   • Result: ans = [3, -2, 1, -5, _, _]
   • Update: j = 3 + 2 = 5

5. Element: 2 (positive)

   • Place at ans[i] → ans[4] = 2
   • Result: ans = [3, -2, 1, -5, 2, _]
   • Update: i = 4 + 2 = 6

6. Element: -4 (negative)

   • Place at ans[j] → ans[5] = -4
   • Result: ans = [3, -2, 1, -5, 2, -4]
   • Update: j = 5 + 2 = 7

Final Result: [3, -2, 1, -5, 2, -4]

Notice how:

• Positive numbers [3, 1, 2] maintained their original order and occupy even indices [0, 2, 4]
• Negative numbers [-2, -5, -4] maintained their original order and occupy odd indices [1, 3, 5]
• The array alternates between positive and negative values throughout

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the input array exactly once using a single for loop, performing constant-time operations (comparison and assignment) for each element.

The space complexity is O(n), where n is the length of the array nums. The algorithm creates a new array ans of the same size as the input array to store the rearranged elements. The additional variables i and j use only O(1) extra space, so the overall space complexity is dominated by the ans array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming the array can start with either sign

A common mistake is not carefully reading that the output must start with a positive integer. Some might implement a solution that starts with whichever sign appears first in the input.

Incorrect approach:

# Wrong: This might start with negative if first element is negative
def rearrangeArray(self, nums):
    result = []
    pos = [x for x in nums if x > 0]
    neg = [x for x in nums if x < 0]
    for i in range(len(pos)):
        result.append(pos[i])
        result.append(neg[i])
    return result

Solution: Always place positive numbers at even indices starting from 0, ensuring the first element is positive.

2. Using separate arrays and multiple passes

While technically correct, using separate arrays for positive and negative numbers requires multiple passes and extra space, making it less efficient.

Inefficient approach:

def rearrangeArray(self, nums):
    positives = []
    negatives = []
    # First pass: separate numbers
    for num in nums:
        if num > 0:
            positives.append(num)
        else:
            negatives.append(num)
  
    # Second pass: merge alternately
    result = []
    for i in range(len(positives)):
        result.append(positives[i])
        result.append(negatives[i])
    return result

Solution: Use the two-pointer approach with direct placement to achieve O(n) time with a single pass.

3. Forgetting to handle the equal count constraint

The problem guarantees equal numbers of positive and negative integers. However, if you're adapting this solution for a different problem, not verifying this constraint could lead to index out of bounds errors.

Potential issue if constraint wasn't guaranteed:

# This would fail if positive and negative counts differ
positive_index = 0
negative_index = 1
# If we have more positives than negatives, negative_index would go out of bounds

Solution: For this specific problem, the constraint is guaranteed. For general cases, add validation or handle unequal counts appropriately.

4. Incrementing pointers by 1 instead of 2

A subtle but critical error is incrementing the pointers by 1 instead of 2, which would cause elements to overwrite each other.

Wrong increment:

if number > 0:
    result[positive_index] = number
    positive_index += 1  # Wrong! Should be += 2

Solution: Always increment by 2 to skip to the next appropriate position (next even index for positives, next odd index for negatives).