Introduction

The Rearrange Array by Positive and Negative Numbers problem involves arranging positive and negative elements alternately in the array.

Given an array arr[] containing both positive and negative integers, the task is to rearrange the array such that positive and negative numbers appear alternately while maintaining their relative order whenever possible.

This is an important array manipulation problem that helps in understanding Two Pointer Technique, array rearrangement, and in-place transformations.

Example

Input: arr[] = [1, -2, 3, -4, 5, -6]Output: [1, -2, 3, -4, 5, -6]
Explanation:
Positive and negative numbers already appear alternately.

Input: arr[] = [3, 1, -2, -5, 2, -4]
Output: [3, -2, 1, -5, 2, -4]
Explanation:
Positive and negative elements are rearranged alternately.
Relative order is maintained.

Constraints

  1 <= n <= 10^5
-10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force (Using Extra Arrays)

Explanation

The simplest way to solve this problem is:

  1. Store all positive numbers separately
  2. Store all negative numbers separately
  3. Place them alternately into the original array

This approach is easy to understand but requires extra space.

Steps

  1. Create:
    • positive array
    • negative array
  2. Traverse the original array.
  3. Store elements based on sign.
  4. Insert positive and negative elements alternately.
  5. Add remaining elements if any exist.

Dry Run

Input Array: [3, 1, -2, -5, 2, -4]Positive Elements:
[3, 1, 2]
Negative Elements:
[-2, -5, -4]
Place alternately:
3 → -2 → 1 → -5 → 2 → -4
Final Result:
[3, -2, 1, -5, 2, -4]

Brute Force Code 

Complexity Analysis

Time Complexity: O(n)
Explanation:
The array is traversed once.

Space Complexity: O(n)
Explanation:
Extra arrays are used to store positive and negative elements.

Approach 2 : Optimized Solution (Two Pointer Placement)

Explanation

Instead of storing elements separately and then merging, we can directly place elements into correct positions.

The idea is:

  1. Positive numbers go to even indices
  2. Negative numbers go to odd indices

This maintains alternating order efficiently.

Steps

  1. Create result array of size n.
  2. Initialize:
    • positiveIndex = 0
    • negativeIndex = 1
  3. Traverse the array.
  4. Place:
    • positive elements at even positions
    • negative elements at odd positions
  5. Return rearranged array.

Dry Run

Input Array: [3, 1, -2, -5, 2, -4]Initially:
positiveIndex = 0
negativeIndex = 1
Traverse 3:
Positive element
Place at index 0
Traverse 1:
Positive element
Place at index 2
Traverse -2:
Negative element
Place at index 1
Traverse -5:
Negative element
Place at index 3
Traverse 2:
Place at index 4
Traverse -4:
Place at index 5
Final Result:
[3, -2, 1, -5, 2, -4]

Optimized Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is processed once.

Space Complexity: O(n)
Explanation:
An extra result array is used for rearrangement.

Edge Cases

  1. All elements are positive
  2. All elements are negative
  3. Unequal number of positives and negatives
  4. Array contains zero
  5. Array contains only one element

Why This Problem is Important

This problem helps in understanding:

  1. Array rearrangement
  2. Two Pointer Technique
  3. Placement strategies
  4. Traversal optimization
  5. Sign-based partitioning

It is one of the most important array manipulation interview problems.

Real-World Applications

Rearrangement techniques are used in:

  1. Signal processing
  2. Data partitioning
  3. Task scheduling
  4. Memory organization
  5. Load balancing systems

Common Mistakes

  1. Incorrect index increments
  2. Overwriting elements
  3. Handling unequal positives and negatives incorrectly
  4. Forgetting relative ordering

Interview Tips

Interviewers often expect:

  1. Efficient traversal logic
  2. Proper index placement
  3. O(n) solution

Always explain why even and odd indices help maintain alternating arrangement.

Related Questions

  1. Move Zeroes
  2. Sort Colors
  3. Partition Array
  4. Rearrange Array Alternately
  5. Positive Negative Segregation

Final Takeaway

The Rearrange Array by Positive and Negative Numbers problem is a fundamental array manipulation problem that teaches rearrangement strategies, index placement, and traversal optimization techniques. Understanding this problem builds a strong foundation for advanced partitioning and in-place transformation problems.