Rearranging Array Elements by Sign: A Comprehensive Guide to Both Varieties

This lecture covers the problem of rearranging array elements by sign. It explores two distinct varieties of the problem: one where positive and negative elements are guaranteed to be equal in number, and another where they can be unequal, requiring leftover elements to be appended at the end while maintaining their relative order.

1. Why Do We Need This? (Problem Statement & Constraints)

In data processing and array manipulation, we frequently need to reorder elements based on specific properties (such as sign, parity, or magnitude) while preserving their relative order (stability).

Variety 1: Equal Positives and Negatives

You are given a $0$-indexed integer array nums of even length $N$ containing:

• Exactly $\frac{N}{2}$ positive integers.
• Exactly $\frac{N}{2}$ negative integers.

Your task is to rearrange the elements of nums such that the modified array follows these rules:

1. Every consecutive pair of integers has opposite signs (i.e., alternating signs starting with a positive number).
2. The relative order of all positive integers and all negative integers must be preserved.
3. The rearranged array must begin with a positive integer.

Example Walkthrough

• Input Array: [3, 1, -2, -5, 2, -4]
• Positive Elements (in order): [3, 1, 2]
• Negative Elements (in order): [-2, -5, -4]
• Target Output: [3, -2, 1, -5, 2, -4]

2. Core Mental Model & Indexing Patterns

To solve Variety 1 efficiently, we must analyze the target indices of the output array.

Index:    0    1    2    3    4    5
Value:  [ 3, -2,   1, -5,   2, -4 ]
Sign:     +    -    +    -    +    -

Key Observations

• Even Indices ($0, 2, 4, \dots$): Reserved exclusively for positive numbers.
• Odd Indices ($1, 3, 5, \dots$): Reserved exclusively for negative numbers.

This mathematical pattern allows us to map any positive element to an even index $2 \times i$ and any negative element to an odd index $2 \times i + 1$.

3. Variety 1: The Brute Force Approach

The most intuitive way to solve this problem is to separate the positive and negative numbers into two auxiliary lists and then merge them back into the original array using the indexing pattern.

Step-by-Step Algorithm

1. Create two empty lists/arrays: positives and negatives.
2. Iterate through the input array nums. If an element is positive, append it to positives; otherwise, append it to negatives.
3. Iterate from $0$ to $\frac{N}{2} - 1$.
4. Place the $i$-th positive element at index $2 \times i$ of the result array.
5. Place the $i$-th negative element at index $2 \times i + 1$ of the result array.

Code Implementation

=== "C++" ```cpp vector<int> rearrangeArrayBrute(vector<int>& nums) { vector<int> positives; vector<int> negatives; int n = nums.size();

    // Step 1: Separate elements by sign
    for (int num : nums) {
        if (num > 0) {
            positives.push_back(num);
        } else {
            negatives.push_back(num);
        }
    }
    
    // Step 2: Reconstruct the array alternatingly
    for (int i = 0; i < n / 2; i++) {
        nums[2 * i] = positives[i];
        nums[2 * i + 1] = negatives[i];
    }
    
    return nums;
}
```

=== "Java" ```java import java.util.ArrayList;

public class Solution {
    public int[] rearrangeArrayBrute(int[] nums) {
        ArrayList<Integer> positives = new ArrayList<>();
        ArrayList<Integer> negatives = new ArrayList<>();
        int n = nums.length;
        
        // Step 1: Separate elements by sign
        for (int num : nums) {
            if (num > 0) {
                positives.add(num);
            } else {
                negatives.add(num);
            }
        }
        
        // Step 2: Reconstruct the array alternatingly
        for (int i = 0; i < n / 2; i++) {
            nums[2 * i] = positives.get(i);
            nums[2 * i + 1] = negatives.get(i);
        }
        
        return nums;
    }
}
```

=== "Python" ```python def rearrangeArrayBrute(nums: list[int]) -> list[int]: positives = [] negatives = []

    # Step 1: Separate elements by sign
    for num in nums:
        if num > 0:
            positives.append(num)
        else:
            negatives.append(num)
    
    # Step 2: Reconstruct the array alternatingly
    n = len(nums)
    for i in range(n // 2):
        nums[2 * i] = positives[i]
        nums[2 * i + 1] = negatives[i]
        
    return nums
```

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  We make one pass of size $N$ to separate elements, and another pass of size $\frac{N}{2}$ to merge them. Total operations $\approx \mathcal{O}(1.5N)$, which simplifies to $\mathcal{O}(N)$.
• Space Complexity: $\mathcal{O}(N)$
  We use auxiliary space of size $\frac{N}{2}$ for positives and $\frac{N}{2}$ for negatives.

4. Variety 1: The Optimal Single-Pass Approach

While the brute-force approach is $\mathcal{O}(N)$ in terms of time, we can optimize the process to run in a single pass over the input array. This avoids storing elements in separate intermediate lists before merging them.

The Two-Pointer Strategy

Instead of separating elements first, we can initialize an output array of size $N$ and maintain two write-pointers:

• posIndex = 0: Points to the next available even index for positive numbers.
• negIndex = 1: Points to the next available odd index for negative numbers.

As we iterate through the input array, we immediately place each element into its correct final position in the output array and advance the corresponding pointer by $2$.

Code Implementation

=== "C++" ```cpp vector<int> rearrangeArray(vector<int>& nums) { int n = nums.size(); vector<int> ans(n); int posIndex = 0; int negIndex = 1;

    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) {
            ans[posIndex] = nums[i];
            posIndex += 2;
        } else {
            ans[negIndex] = nums[i];
            negIndex += 2;
        }
    }
    return ans;
}
```

=== "Java" ```java public class Solution { public int[] rearrangeArray(int[] nums) { int n = nums.length; int[] ans = new int[n]; int posIndex = 0; int negIndex = 1;

        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                ans[posIndex] = nums[i];
                posIndex += 2;
            } else {
                ans[negIndex] = nums[i];
                negIndex += 2;
            }
        }
        return ans;
    }
}
```

=== "Python" ```python def rearrangeArray(nums: list[int]) -> list[int]: n = len(nums) ans = [0] * n pos_index = 0 neg_index = 1

    for num in nums:
        if num > 0:
            ans[pos_index] = num
            pos_index += 2
        else:
            ans[neg_index] = num
            neg_index += 2
            
    return ans
```

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  We perform exactly one pass over the input array.
• Space Complexity: $\mathcal{O}(N)$
  We use an auxiliary array ans of size $N$ to store and return the rearranged elements.

Note: We cannot perform this rearrangement in-place with $\mathcal{O}(1)$ auxiliary space without violating the $\mathcal{O}(N)$ time complexity constraint or destroying the relative order of elements. Thus, $\mathcal{O}(N)$ space is optimal for this problem.

5. Visualizing the Single-Pass Flow

The following diagram illustrates how the single-pass optimal algorithm processes the input array [3, 1, -2, -5, 2, -4]:

6. Variety 2: The Challenge of Unequal Signs

In real-world scenarios, datasets are rarely perfectly balanced. In Variety 2, the number of positive and negative elements is not guaranteed to be equal.

Problem Rules for Variety 2

1. Alternate positive and negative elements as long as both are available.
2. If one sign runs out of elements, append all remaining elements of the other sign to the end of the array.
3. Maintain the relative order of all elements.

Example Walkthrough

• Input Array: [2, -1, 3, -3, 5, 6]
• Positives: [2, 3, 5, 6] (Count = 4)
• Negatives: [-1, -3] (Count = 2)
• Alternating Phase: We can only pair up to 2 positives and 2 negatives.
  • Alternating portion: [2, -1, 3, -3]
• Leftover Phase: Append remaining positives [5, 6] to the end.
• Target Output: [2, -1, 3, -3, 5, 6]

7. Variety 2: Fallback to Brute Force & Leftover Management

The single-pass optimal pointer approach from Variety 1 cannot be used directly here. Because we do not know the counts of positives and negatives beforehand, we cannot pre-calculate where the leftover elements should start.

Therefore, we must fall back to a modified brute-force approach. This is a common pattern in technical interviews: when constraints change, a previously "sub-optimal" mental model often becomes the foundation for the correct solution.

Algorithmic Strategy

1. Separate the array into positives and negatives lists.
2. Determine which list is smaller. Let limit = min(positives.size(), negatives.size()).
3. Fill the first $2 \times \text{limit}$ positions of the array alternatingly:
   • A[2 * i] = positives[i]
   • A[2 * i + 1] = negatives[i]
4. Identify the leftover elements from the larger list.
5. Append these leftovers sequentially to the remaining indices of the array.

8. Variety 2: Step-by-Step Implementation

Here is the complete implementation for Variety 2 across C++, Java, and Python.

=== "C++" ```cpp #include <vector> #include <algorithm> using namespace std;

vector<int> rearrangeArrayVariety2(vector<int>& A) {
    vector<int> pos, neg;
    int n = A.size();
    
    // Step 1: Separate elements by sign
    for (int i = 0; i < n; i++) {
        if (A[i] > 0) pos.push_back(A[i]);
        else neg.push_back(A[i]);
    }

    // Step 2: Handle cases based on which list is larger
    if (pos.size() > neg.size()) {
        // Fill alternating elements up to the size of the smaller list (neg)
        for (int i = 0; i < neg.size(); i++) {
            A[2 * i] = pos[i];
            A[2 * i + 1] = neg[i];
        }
        // Fill the remaining positive elements
        int index = neg.size() * 2;
        for (int i = neg.size(); i < pos.size(); i++) {
            A[index] = pos[i];
            index++;
        }
    } else {
        // Fill alternating elements up to the size of the smaller list (pos)
        for (int i = 0; i < pos.size(); i++) {
            A[2 * i] = pos[i];
            A[2 * i + 1] = neg[i];
        }
        // Fill the remaining negative elements
        int index = pos.size() * 2;
        for (int i = pos.size(); i < neg.size(); i++) {
            A[index] = neg[i];
            index++;
        }
    }
    return A;
}
```

=== "Java" ```java import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> rearrangeArrayVariety2(ArrayList<Integer> A) {
        ArrayList<Integer> pos = new ArrayList<>();
        ArrayList<Integer> neg = new ArrayList<>();

        // Step 1: Separate elements by sign
        for (int num : A) {
            if (num > 0) pos.add(num);
            else neg.add(num);
        }

        // Step 2: Handle cases based on which list is larger
        if (pos.size() > neg.size()) {
            // Fill alternating elements
            for (int i = 0; i < neg.size(); i++) {
                A.set(2 * i, pos.get(i));
                A.set(2 * i + 1, neg.get(i));
            }
            // Fill remaining positives
            int index = neg.size() * 2;
            for (int i = neg.size(); i < pos.size(); i++) {
                A.set(index, pos.get(i));
                index++;
            }
        } else {
            // Fill alternating elements
            for (int i = 0; i < pos.size(); i++) {
                A.set(2 * i, pos.get(i));
                A.set(2 * i + 1, neg.get(i));
            }
            // Fill remaining negatives
            int index = pos.size() * 2;
            for (int i = pos.size(); i < neg.size(); i++) {
                A.set(index, neg.get(i));
                index++;
            }
        }
        return A;
    }
}
```

=== "Python" ```python def rearrangeArrayVariety2(A: list[int]) -> list[int]: pos = [] neg = []

    # Step 1: Separate elements by sign
    for num in A:
        if num > 0:
            pos.append(num)
        else:
            neg.append(num)
    
    # Step 2: Handle cases based on which list is larger
    if len(pos) > len(neg):
        # Fill alternating elements
        for i in range(len(neg)):
            A[2 * i] = pos[i]
            A[2 * i + 1] = neg[i]
        # Fill remaining positives
        index = len(neg) * 2
        for i in range(len(neg), len(pos)):
            A[index] = pos[i]
            index += 1
    else:
        # Fill alternating elements
        for i in range(len(pos)):
            A[2 * i] = pos[i]
            A[2 * i + 1] = neg[i]
        # Fill remaining negatives
        index = len(pos) * 2
        for i in range(len(pos), len(neg)):
            A[index] = neg[i]
            index += 1
            
    return A
```

9. Performance & Complexity Synthesis

The table below compares the performance characteristics of all discussed approaches:

Mathematical Breakdown of Variety 2 Time Complexity

Let's analyze the exact operations performed in Variety 2:

1. Separation Phase: We iterate through the array of size $N$ once to populate pos and neg. This takes $\mathcal{O}(N)$ time.
2. Alternating Phase: We run a loop up to $\min(\text{pos}, \text{neg})$ times.
3. Leftover Phase: We run a loop for the remaining elements, which is of size $\vert \text{pos} - \text{neg} \vert$.

Since $\min(\text{pos}, \text{neg}) + \max(\text{pos}, \text{neg}) = N$, the total operations simplify to:

Thus, even in the worst-case scenario (e.g., all elements are positive or all are negative), the time complexity remains strictly linear at $\mathcal{O}(N)$.

Summary and Key Takeaways

• Relative Order Preservation: Maintaining the relative order of elements of the same sign is a core constraint of this problem. This prevents us from using simple in-place partitioning algorithms (like QuickSelect or Dutch National Flag partitioning).
• Even/Odd Index Mapping: For balanced arrays, positive elements always map to even indices ($2 \times i$) and negative elements map to odd indices ($2 \times i + 1$).
• The Power of Two Pointers: In Variety 1, maintaining separate write-pointers (posIndex and negIndex) allows us to construct the final array in a single pass.
• Value of Brute Force: Variety 2 demonstrates why brute-force solutions are valuable. When constraints are relaxed (unequal counts), the optimal single-pass pointer approach fails, and we must fall back on the brute-force strategy of separating elements first.
• Leftover Management: In Variety 2, the starting index for appending leftover elements is always $2 \times \min(\text{pos.size()}, \text{neg.size()})$.
• Space Complexity Trade-off: An auxiliary space complexity of $\mathcal{O}(N)$ is required for both varieties to maintain stable relative ordering while keeping the time complexity at $\mathcal{O}(N)$.